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)|
References found in this work BETA
No references found.
Citations of this work BETA
No citations found.
Similar books and articles
The Lambek Calculus Enriched with Additional Connectives.Makoto Kanazawa - 1992 - Journal of Logic, Language and Information 1 (2):141-171.
Hybrid Languages.Patrick Blackburn & Jerry Seligman - 1995 - Journal of Logic, Language and Information 4 (3):251-272.
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.Fee-Alexandra Haase - manuscript
Automata for Epistemic Temporal Logic with Synchronous Communication.Swarup Mohalik & R. Ramanujam - 2010 - Journal of Logic, Language and Information 19 (4):451-484.
Validity in Intensional Languages: A New Approach.William H. Hanson & James Hawthorne - 1985 - Notre Dame Journal of Formal Logic 26 (1):9-35.
Highly Constrained Unification Grammars.Daniel Feinstein & Shuly Wintner - 2008 - Journal of Logic, Language and Information 17 (3):345-381.
A Descriptive Characterisation of Linear Languages.Tore Langholm - 2006 - Journal of Logic, Language and Information 15 (3):233-250.
Added to index2009-01-28
Total downloads9 ( #466,205 of 2,177,827 )
Recent downloads (6 months)1 ( #317,251 of 2,177,827 )
How can I increase my downloads?