Formal languages defined by the underlying structure of their words

Journal of Symbolic Logic 53 (4):1009-1026 (1988)
  Copy   BIBTEX

Abstract

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

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,221

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Analytics

Added to PP
2009-01-28

Downloads
33 (#416,963)

6 months
1 (#1,028,709)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Topological complexity of locally finite ω-languages.Olivier Finkel - 2008 - Archive for Mathematical Logic 47 (6):625-651.

Add more citations

References found in this work

No references found.

Add more references