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)|
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
|Through your library|
References found in this work BETA
No references found.
Citations of this work BETA
No citations found.
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.
Added to index2009-01-28
Total downloads7 ( #292,425 of 1,725,863 )
Recent downloads (6 months)3 ( #210,647 of 1,725,863 )
How can I increase my downloads?