Logic over words on countable ordinals

Copyright informations

This material has been published in Journal of Computer and System Science, vol. 63, n. 3, pp 394-431, Nov. 2001, 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

The main result of this paper is the extension of the theorem of Schützenberger, McNaughton and Papert on star-free sets of finite words to languages of words of countable length. We also give an other proof of the theorem of Büchi which establishes the equivalence between automata and monadic second-order sentences for defining sets of words of denumerable length.

References

André Arnold, "A syntactic congruence for rational ω-languages", Theoretical Computer Science, vol. 39, pp. 333-335, 1985.
Nicolas Bedon and Olivier Carton, "An Eilenberg theorem for words on countable ordinals", in Latin'98: Theoretical Informatics (Cláudio L. Lucchesi and Arnaldo V. Moura, eds.), vol. 1380 of Lecture Notes in Computer Science, (Campinas, Brazil), pp. 53-64, Springer, Apr. 1998.
Nicolas Bedon, "Star-free sets of words on ordinals," IGM report 97-8, to appear Information and Computation.
Nicolas Bedon, "Automata, semigroups and recognizability of words on ordinals," International Journal of Algebra and Computation, vol. 8, pp. 1-21, Feb. 1998.
Nicolas Bedon, Langages reconnaissables de mots indexés par des ordinaux. PhD thesis, Université de Marne-la-Vallée, Cité Descartes, 5, boulevard Descartes, Champs-sur-Marne, 77454 Marne-la-Vallée Cedex 2, France, Jan. 1998.
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 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.
J. Richard Büchi, "Decision methods in the theory of ordinals", Bull. Am. Math. Soc., vol. 71, pp. 767-770, 1965.
Joëlle Cohen-Chesnot, "On the expressive power of temporal logic for infinite words", Theoretical Computer Science, vol. 83, pp. 301-312, 28~june 1991. Note.
Joëlle Cohen, Dominique Perrin, and Jean-Eric Pin, "On the expressive power of temporal logic", Journal of Computer and System Sciences, vol. 46, pp. 271-294, June 1993.
A. Ehrenfeucht, "An application of games to the completeness problem for formalized theories", Fund. Math., vol. 49, pp. 129-141, 1961. [MR 23, \#3666].
Dov M. Gabbay, Amir Pnueli, Saharon Shelah, and Jonathan Stavi, "On the temporal basis of fairness", in Conference Record of the Seventh Annual ACM Symposium on Principles of Programming Languages, (Las Vegas, Nevada), pp. 163-173, january 1980.
J. Kamp, Tense logic and the theory of linear order. PhD thesis, University of California, Los Angeles, 1968.
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.
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, "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, Variétés de langages formels. Paris, France: Masson, 1984. English version: Varieties of formal languages, Plenum Press, New-York, 1986.
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), English version: "Infinite words".
Scott Rohde, Alternating automata and the temporal logic of ordinals. PhD thesis, University of Illinois, Urbana-Champaign, USA, 1997.
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.
Jerzy Wojciechowski, "Classes of transfinite sequences accepted by finite automata", Fundamenta informaticæ, vol. 7, no. 2, pp. 191-223, 1984.
Jerzy Wojciechowski, "Finite automata on transfinite sequences and regular expressions", Fundamenta informatic\ae, vol. 8, no. 3-4, pp. 379-396, 1985.

Download

Gzipped postscript file (160 Ko)

24 January 2015 22:08:22