Formal Languages Defined by the Underlying Structure of their Words
Ressayre, J. P.
J. Symbolic Logic, Tome 53 (1988) no. 1, p. 1009-1026 / Harvested from Project Euclid
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_\infty$ 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_\infty$ to the existence of infinite "progressions" of words included in $L$, and they imply the decidability of various questions about $L$ or $L_\infty$. 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.
Publié le : 1988-12-14
Classification: 
@article{1183742778,
     author = {Ressayre, J. P.},
     title = {Formal Languages Defined by the Underlying Structure of their Words},
     journal = {J. Symbolic Logic},
     volume = {53},
     number = {1},
     year = {1988},
     pages = { 1009-1026},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183742778}
}
Ressayre, J. P. Formal Languages Defined by the Underlying Structure of their Words. J. Symbolic Logic, Tome 53 (1988) no. 1, pp.  1009-1026. http://gdmltest.u-ga.fr/item/1183742778/