On Locally Finite Languages

Olivier Finkel

A language of finite words or an α-language ( language of words of length α, where α is a countable ordinal) over a finite alphabet is accepted by a Büchi automaton iff it is defined by a monadic second order sentence. In order to apply ideas and machinery of model theory to the study of formal languages, J-P. Ressayre introduced locally finite sentences and locally finite languages in [Res88]. Locally finite sentences are first order, but they define locally finite languages, via existential quantifications over relations and functions which appear in the locally finite sentence. These second order quantifications are much more general than the monadic ones: each rational language of finite words is locally finite, [Res88], and many context free as well as non context free languages are locally finite [Fin99a]. We show that an α-language ( α < ω^{ω}) accepted by a Büchi automaton is defined by a locally finite sentence [Fin99a]. But syntaxic and semantic restrictions (a locally finite sentence is equivalent to a universal one and its models satisfy simple structural properties) make locally finite α-languages keep important properties of rational α-languages. The pumping lemmas of [Res88] [FR96] are analogues for each locally finite α-language (α < ω^{ω}) of the property: ” A regular ω-language is non empty if and only if it contains an ultimately periodic word ”. And these lemmas imply the decidability of the emptiness problem for locally finite α-languages, [FR96]. But we show that locally finite (α)-languages extend far beyond rational (α)-languages, by considering their topological complexity.

[LT94] H. Lescow and W. Thomas, Logical specifications of infinite computations, In:”A Decade of Concurrency” (J. W. de Bakker et al., eds), Springer LNCS 803 (1994), 583-621.

[Fin99a] O. Finkel, Locally Finite Languages, To appear in T.C.S .

[Fin99b] O. Finkel, Locally Finite Omega Languages, submitted to T.C.S .

[FR96] O. Finkel and J-P. Ressayre, Stretchings, Journal of Symbolic Logic, Volume 61, number 2, June 1996, p. 563-585.

[Res88] J-P. Ressayre, Formal Languages Defined by the Underlying Structure of their Words, Journal of Symbolic Logic, 53, number 4, December 1988, p. 1009-1026.

[Tho96] W. Thomas, Languages, Automata and Logic, in Handbook of Formal Languages Theory, Vol 3, Edited by G. Rozenberg and A. Salomaa, Springer Verlag, 1996.

Address: Equipe de Logique Mathématique CNRS (UPRESA 7056), Université Paris 7, U.F.R. de Mathématiques, 2 Place Jussieu, 75251 Paris Cedex 05, France

E-mail: finkel@logique.jussieu.fr