Schützenberger and Eilenberg Theorems for Words on Linear Orderings

A journal version of this paper, with full proofs, has been published in JCSS.

Abstract

In the case of finite words, a Schützenberger theorem proves that the star-free sets are exactly the languages recognized by finite aperiodic semigroups. This gives an algebraic characterization of star-free sets. The variety theorem of Eilenberg offers a general framework for the algebraic characterization of recognizable sets: it establishes a one-to-one correspondence between varieties of languages of finite words and pseudo-varieties of algebras. This paper contains extensions of those two well-known results to words on countable scattered linear orderings.

References

Jorge Almeida. Finite semigroups and universal algebra, volume 3 of Series in algebra. World Scientific, 1994.
Nicolas Bedon. Langages reconnaissables de mots indexés par des ordinaux. PhD thesis, University of Marne-la-Vallée, France, 1998.
Nicolas Bedon. Logic over words on denumerable ordinals. Journal of Computer and System Science, 63(3):394-431, November 2001.
Nicolas Bedon. Star-free sets of words on ordinals. Inform. Comput., 166:93-111, 2001.
Nicolas Bedon and Olivier Carton. An Eilenberg theorem for words on countable ordinals. In Claudio L. Lucchesi and Arnaldo V. Moura, editors, Latin'98: Theoretical Informatics, volume 1380 of Lect. Notes in Comput. Sci., pages 53-64. Springer-Verlag, 1998.
Véronique Bruyère and Olivier Carton. Automata on linear orderings. In J. Sgall, A. Pultr, and P. Kolman, editors, MFCS'2001, volume 2136 of Lect. Notes in Comput. Sci., pages 236-247, 2001.
J. Richard Büchi. Weak second-order arithmetic and finite automata. Zeit. Math. Logik. Grund. Math., 6:66-92, 1960.
Samuel Eilenberg. Automata, languages and machines, volume B. Academic Press, 1976.
Felix Hausdorff. Set Theory. Chelsea, New York, 1957.
Robert McNaughton and Seymour Papert. Counter free automata. MIT Press, Cambridge, MA, 1971.
Jean-Pierre Pécuchet. Variétés de semigroupes et mots infinis. In B. Monien and G. Vidal-Naquet, editors, STACS '86, volume 210 of Lect. Notes in Comput. Sci., pages 180-191, 1986.
Dominique Perrin. Recent results on automata and infinite words. In M.~P. Chytil and V.~Koubek, editors, Mathematical foundations of computer science, volume 176 of Lect. Notes in Comput. Sci., pages 134-148, Berlin, 1984. Springer.
Dominique Perrin. Handbook of theoretical computer science, volume B, chapter Finite automata, pages 1-53. Elsevier, 1990.
Dominique Perrin and Jean-Eric Pin. First order logic and star-free sets. J. Comput. System Sci., 32:393-406, 1986.
Dominique Perrin and Jean-Eric Pin. Infinite Words: Automata, Semigroups, Logic and Games, volume 141 of Pure and Applied Mathematics. Elsevier, 2004.
Jean-Eric Pin. Variétés de langages formels. Masson, Paris, France, 1984. English version: Varieties of formal languages, Plenum Press, New-York, 1986.
Jean-Eric Pin. Handbook of formal languages, volume 1, chapter Syntactic semigroups, pages 679-746. Springer, 1997.
Chloé Rispal. Automates sur les ordres linéaires: complémentation. PhD thesis, University of Marne-la-Vallée, France, 2004.
Chloé Rispal and Olivier Carton. Complementation of rational sets on countable scattered linear orderings. In C. S. Calude, E. Calude, and M. J. Dinneen, editors, DLT'2004, volume 3340 of Lect. Notes in Comput. Sci., pages 381-392, 2004.
Joseph G. Rosenstein. Linear Orderings. Academic Press, 1982.
Marcel-Paul Schützenberger. On finite monoids having only trivial subgroups. Inform. Control, 8:190-194, 1965.
Thomas Wilke. An Eilenberg theorem for $\infty$-languages. In Automata, Languages and Programming: Proc. of 18th ICALP Conference, pages 588-599. Springer, 1991.

Download

For copyright reasons I can not publish the final version of the paper here. Please send me an e-mail to get it. You may also find it here if your institution has access to the electronic ressources of Springer.