Schützenberger and Eilenberg Theorems for Words on Linear Orderings

This paper is the journal version of a work presented at DLT'05.

Abstract

This paper contains extensions to words on countable scattered linear orderings of two well-known results of characterization of languages of finite words. We first extend a theorem of Schützenberger establishing that the star-free sets of finite words are exactly the languages recognized by finite aperiodic semigroups. This gives an algebraic characterization of star-free sets of words over countable scattered linear orderings. Contrarily to the case of finite words, first-order definable languages are strictly included into the star-free languages when countable scattered linear orderings are considered. Second, we extend the variety theorem of Eilenberg for finite words: there is a one-to-one correspondence between varieties of languages of words on countable scattered linear orderings and pseudo-varieties of algebras. The star-free sets are an example of such a variety of languages.

Keywords

Regular languages, rational languages, recognizable languages, infinite words, tranfinite words, linear orderings, star-free sets, first-order logic, varieties.

References

Jorge Almeida, Finite semigroups and universal algebra, vol. 3 of Series in algebra. World Scientific, 1994.
Nicolas Bedon and Olivier Carton, "An Eilenberg theorem for words on countable ordinals", in Latin'98: Theoretical Informatics (Claudio L. Lucchesi and Arnaldo V. Moura, eds.), vol. 1380 of Lect. Notes in Comput. Sci., pp. 53-64, Springer-Verlag, 1998.
Véronique Bruyère and Olivier Carton, "Automata on linear orderings", J. Comput. System Sci., vol. 73, no. 1, pp. 1-24, 2007.
Nicolas Bedon, "Automata, semigroups and recognizability of words on ordinals", Int. J. Alg. Comput., vol. 8, no. 1, pp. 1-21, 1998.
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, vol. 63, pp. 394-431, Nov. 2001.
Nicolas Bedon, "Star-free sets of words on ordinals", Inform. Comput., vol. 166, pp. 93-111, 2001.
Nicolas Bedon and Chloé Rispal, "Schützenberger and Eilenberg theorems for words on linear orderings", No. 3572 in Lect. Notes in Comp. Science, (Palermo, Italy), pp. 134-145, Springer, July 2005.
J. Richard Büchi, "Weak second-order arithmetic and finite automata", Zeit. Math. Logik. Grund. Math., vol. 6, pp. 66-92, 1960.
J. Richard Büchi, "On a decision method in the restricted second-order arithmetic", in Proc. Int. Congress Logic, Methodology and Philosophy of Science, Berkeley 1960, pp. 1-11, Stanford University Press, 1962.
J. Richard Büchi, "Transfinite automata recursions and weak second order theory of ordinals", in Proc. Int. Congress Logic, Methodology, and Philosophy of Science, Jerusalem 1964, pp. 2-23, North Holland, 1964.
J. Richard Büchi, "Decision methods in the theory of ordinals", Bull. Am. Math. Soc., vol. 71, pp. 767-770, 1965.
Olivier Carton and Max Michel, "Unambiguous Büchi automata", Theoret. Comput. Sci., vol. 297, pp. 37-81, 2003.
Samuel Eilenberg, Automata, languages and machines, vol. B. Academic Press, 1976.
Felix Hausdorff, Set Theory. New York: Chelsea, 1957.
Richard E. Ladner, "Application of model theoretic games to discrete linear orders and finite automata", Inform. Control, vol. 33, pp. 281-303, 1977.
Robert McNaughton and Seymour Papert, Counter free automata. Cambridge, MA: MIT Press, 1971.
Jean Pierre Pécuchet, "Variétés de semigroupes et mots infinis", in STACS '86 (B. Monien and G. Vidal-Naquet, eds.), vol. 210 of Lect. Notes in Comput. Sci., pp. 180-191, 1986.
Dominique Perrin, "Recent results on automata and infinite words", in Mathematical foundations of computer science (M. P. Chytil and V. Koubek, eds.), vol. 176 of Lect. Notes in Comput. Sci., (Berlin), pp. 134-148, Springer, 1984.
Dominique Perrin, Handbook of theoretical computer science, vol. B, ch. Finite automata, pp. 1-53. Elsevier, 1990.
Jean Eric Pin, Variétés de langages formels. Paris, France: Masson, 1984. English version: Varieties of formal languages, Plenum Press, New-York, 1986.
Jean Eric Pin, Handbook of formal languages, vol. 1, ch. Syntactic semigroups, pp. 679-746. Springer, 1997.
Dominique Perrin and Jean Eric Pin, "First order logic and star-free sets", J. Comput. System Sci., vol. 32, pp. 393-406, 1986.
Dominique Perrin and Jean Eric Pin, Infinite Words: Automata, Semigroups, Logic and Games, vol. 141 of Pure and Applied Mathematics. Elsevier, 2004.
Chloé Rispal and Olivier Carton, "Complementation of rational sets on countable scattered linear orderings", International Journal of Foundations of Computer Science, vol. 16, pp. 767-786, Aug. 2005.
Chloé Rispal, Automates sur les ordres linéaires: complémentation.. PhD thesis, University of Marne-la-Vallée, France, 2004.
Joseph G. Rosenstein, Linear Orderings. Academic Press, 1982.
Marcel Paul Schützenberger, "On finite monoids having only trivial subgroups", Inform. Control, vol. 8, pp. 190-194, 1965.
Wolfgang Thomas, "Star free regular sets of $\omega$-sequences", Inform. Control, vol. 42, pp. 148-156, 1979.
Thomas Wilke, "An Eilenberg theorem for $\infty$-languages", in Automata, Languages and Programming: Proc. of 18th ICALP Conference, pp. 588-599, Springer, 1991.
Jerzy Wojciechowski, "Finite automata on transfinite sequences and regular expressions", Fundamenta informaticae, vol. 8, no. 3-4, pp. 379-396, 1985.

Download

For copyright reasons I can not publish the final version of the paper here. Please send me an e-mail to get it.

24 January 2015 22:07:32