Automata, semigroups and recognizability of words on ordinals

Abstract

For a given integer n, we define ω^n semigroups as a generalization of ω-semigroups for languages of words of length less than ω^n. When they are finite, those algebraic structures define the same sets as those recognized by Choueka automata. These sets are also equivalent to regular expressions in which an unary operator standing for the infinite repetition of a language is free as the Kleene closure operator is. Naturally, the notion of syntactic congruence still works on ω^n-semigroups. Thus, given a recognizable language X, there exists an ω^n-semigroup smaller than the others recognizing X.

References

J. Richard Büchi, "On a decision method in the restricted second-order arithmetic", in Logic, Methodology and Philosophy of science: Proc. Intern. Congr., (Stanford, California), pp. 1-11, Stanford University Press, 1962.
J. Richard Büchi, "Decision methods in the theory of ordinals", Bull. Am. Math. Soc., vol. 71, pp. 767-770, 1965.
Yacoov Choueka, "Finite automata, definable sets, and regular expressions over ω^n-tapes", Journal of Computer and System Sciences, vol. 17, pp. 81-97, 1978.
J. E. Hopcroft and J. D. Ullman, Introduction to automata theory, languages, and computation. Addison-Wesley, Reading, 1979.
Robert McNaughton, "Testing and generating infinite sequences by a finite automaton", Information and Control, vol. 9, pp. 521-530, 1966.
D. Muller, "Infinite sequences and finite machines", in Switching circuit theory and logical design: Proc. Fourth Annual Symp. IEEE, pp. 3-16, 1963.
Jean Pierre Pécuchet, "Etude syntaxique des parties reconnaissables de mots infinis", Lecture Notes in Computer Science, vol. 226, pp. 294-303, 1986.
Jean Pierre Pécuchet, "Variétés de semigroupes et mots infinis", Lecture Notes in Computer Science, vol. 210, pp. 180-191, 1986.
Dominique Perrin and Jean-Eric Pin, Mots infinis. 1997. To appear (LITP report 97-04).
J. G. Rosenstein, Linear ordering. Academic Press, New York, 1982.
Waclaw Sierpinski, Leçons sur les nombres transfinis. Paris: Gauthier-Villars, 1950.
Waclaw Sierpinski, Cardinal and ordinal numbers. Varsovie: Polish Scientific Publishers, 1965.
Wolfgang Thomas, Handbook of theoretical computer science, vol. B, ch. Automata on infinite objects, pp. 135-191. Elsevier, 1990.
Thomas Wilke, "An algebraic theory for regular languages of finite and infinite words", International Journal of Algebra and Computation, vol. 3, no. 4, pp. 447-489, 1993.

Download

Gzipped Postscript file (82Ko)

24 January 2015 22:04:40