[Up]

Star-free sets of words on ordinals

Copyright informations

This material has been published in Information and Computation, number 166, 2001, pp 93-111, the only definitive repository of the content that has been certified and accepted after peer review. Copyright and all rights therein are retained by Academic Press. This material may not be copied or reposted without explicit permission. IDEAL

Abstract

Let n be a fixed integer; we extend the theorem of Schützenberger, McNaughton and Papert on star-free sets of finite words to languages of sequences of length less than ω^n.

References

Nicolas Bedon, "Finite automata and ordinals," Theoretical Computer Science, vol. 156, pp. 119-144, March 1996.
Nicolas Bedon, "Automata, semigroups and recognizability of words on ordinals," International Journal of Algebra and Computation, vol. 8, pp. 1-21, February 1998.
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, "Transfinite automata recursions and weak second order theory of ordinals", in Proc. Int. Congress Logic, Methodology, and Philosophy of Science, (Jerusalem), pp. 2-23, North-Holland Publ. Co., 1964. Invited address.
Yacoov Choueka, "Finite automata, definable sets, and regular expressions over ω^n-tapes", Journal of Computer and System Sciences, vol. 17, pp. 81-97, 1978.
A. Ehrenfeucht, "An application of games to the completeness problem for formalized theories", Fund. Math., vol. 49, pp. 129-141, 1961. [MR 23, \#3666].
Stephen C. Kleene, "Representation of events in nerve nets and finite automata", in Automata studies (Shannon and McCarthy, eds.), (Princeton, New Jersey), pp. 3-42, Princeton University Press, 1956.
Richard E. Ladner, "Application of model theoretic games to discrete linear orders and finite automata", Information and Control, vol. 33, pp. 281-303, 1977.
Robert McNaughton and Seymour Papert, Counter free automata. Cambridge, MA: MIT Press, 1971.
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, "Recent results on automata and infinite words", in Mathematical foundations of computer science (M. P. Chytil and V. Koubek, eds.), vol. 176 of Lecture Notes in Computer Science, (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, "Logic, semigroups and automata on words", in Mathematics and Artificial Intelligence, 1994.
Dominique Perrin and Jean-Eric Pin, "First order logic and star-free sets", Journal of Computer and System Sciences, vol. 32, pp. 393-406, 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.
Marcel Paul Schützenberger, "On finite monoids having only trivial subgroups", Information and Control, vol. 8, pp. 190-194, 1965.
Waclaw Sierpinski, Cardinal and ordinal numbers. Varsovie: Polish Scientific Publishers, 1965.
Howard Straubing, Finite automata, formal logic and circuit complexity. Birkhäuser, 1994.
Wolfgang Thomas, "Star free regular sets of ω-sequences", Information and 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.

Download

Gzipped postscript file (136 Ko)

24 January 2015 22:08:05