David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Jack Alan Reynolds
Learn more about PhilPapers
Journal of Symbolic Logic 53 (4):1009-1026 (1988)
i) We show for each context-free language L that by considering each word of L as a structure in a natural way, one turns L into a finite union of classes which satisfy a finitary analog of the characteristic properties of complete universal first order classes of structures equipped with elementary embeddings. We show this to hold for a much larger class of languages which we call free local languages. ii) We define local languages, a class of languages between free local and context-sensitive languages. Each local language L has a natural extension L ∞ to infinite words, and we prove a series of "pumping lemmas", analogs for each local language L of the "uvxyz theorem" of context free languages: they relate the existence of large words in L or L ∞ to the existence of infinite "progressions" of words included in L, and they imply the decidability of various questions about L or L ∞ . iii) We show that the pumping lemmas of ii) are independent from strong axioms, ranging from Peano arithmetic to ZF + Mahlo cardinals. We hope that these results are useful for a model-theoretic approach to the theory of formal languages
|Keywords||No keywords specified (fix it)|
|Categories||categorize this paper)|
|Through your library||Configure|
Similar books and articles
Makoto Kanazawa (1992). The Lambek Calculus Enriched with Additional Connectives. Journal of Logic, Language and Information 1 (2):141-171.
Patrick Blackburn & Jerry Seligman (1995). Hybrid Languages. Journal of Logic, Language and Information 4 (3):251-272.
Fee-Alexandra Haase, The Meanings of Beauty: Studies of a Cultural Concept and its Variations in Multi-Lingual Societies of Africa Illustrating the Diversity in Esthetics and Ethnic Terminology.
Swarup Mohalik & R. Ramanujam (2010). Automata for Epistemic Temporal Logic with Synchronous Communication. Journal of Logic, Language and Information 19 (4):451-484.
William H. Hanson & James Hawthorne (1985). Validity in Intensional Languages: A New Approach. Notre Dame Journal of Formal Logic 26 (1):9-35.
Daniel Feinstein & Shuly Wintner (2008). Highly Constrained Unification Grammars. Journal of Logic, Language and Information 17 (3):345-381.
Tore Langholm (2006). A Descriptive Characterisation of Linear Languages. Journal of Logic, Language and Information 15 (3):233-250.
Sorry, there are not enough data points to plot this chart.
Added to index2009-01-28
Recent downloads (6 months)0
How can I increase my downloads?