Formal languages defined by the underlying structure of their words

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.