Logic and Rational Languages of Words Indexed by Linear Orderings

Copyright informations

This paper has been published in Lecture Notes in Computer Sciences, Vol. 5010, 2008, and the copyright is owned by Springer.

A journal version of this work has also been published in Theory of Computing Systems

Abstract

We prove that every rational language of words indexed by linear orderings is definable in monadic second-order logic. We also show that the converse is true for the class of languages indexed by countable scattered linear orderings, but false in the general case. As a corollary we prove that the inclusion problem for rational languages of words indexed by countable linear orderings is decidable.

References

[1]	N. Bedon. Logic over words on denumerable ordinals. Journal of Computer and System Science, 63(3):394-431, 2001.
[2]	N. Bedon and C. Rispal. Schützenberger and Eilenberg theorems for words on linear orderings. In C. De Felice and A. Restivo, editors, DLT'2005, volume 3572 of Lect. Notes in Comput. Sci., pages 134-145. Springer-Verlag, 2005.
[3]	A. Bès and O. Carton. A Kleene theorem for languages of words indexed by linear orderings. Int. J. Found. Comput. Sci., 17(3):519-542, 2006.
[4]	V. Bruyère and O. 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.
[5]	V. Bruyère and O. Carton. Hierarchy among automata on linear orderings. In R. Baeza-Yate, U. Montanari, and N. Santoro, editors, Foundation of Information technology in the era of network and mobile computing, pages 107-118. Kluwer Academic Publishers, 2002.
[6]	V. Bruyère and O. Carton. Automata on linear orderings. J. Comput. System Sci., 73(1):1-24, 2007.
[7]	V. Bruyère, O. Carton, and G. Sénizergues. Tree automata and automata on linear orderings. In T. Harju and J. Karhumäki, editors, WORDS'2003, pages 222-231. Turku Center for Computer Science, 2003.
[8]	J. R. Büchi. Weak second-order arithmetic and finite automata. Z. Math. Logik und grundl. Math., 6:66-92, 1960.
[9]	J. R. Büchi. On a decision method in the restricted second-order arithmetic. In Proc. Int. Congress Logic, Methodology and Philosophy of science, Berkeley 1960, pages 1-11. Stanford University Press, 1962.
[10]	J. R. Büchi. Transfinite automata recursions and weak second order theory of ordinals. In Proc. Int. Congress Logic, Methodology, and Philosophy of Science, Jerusalem 1964, pages 2-23. North Holland, 1965.
[11]	O. Carton. Accessibility in automata on scattered linear orderings. In K.Diks and W.Rytter, editors, MFCS'2002, volume 2420 of Lect. Notes in Comput. Sci., pages 155-164, 2002.
[12]	Y. Gurevich. Monadic second-order theories. In J. Barwise and S. Feferman, editors, Model-Theoretic Logics, pages 479-506. Springer-Verlag, Perspectives in Mathematical Logic, 1985.
[13]	R. E. Ladner. Application of model theoretic games to discrete linear orders and finite automata. Inform. Control, 33, 1977.
[14]	R. McNaughton and S. Papert. Counter free automata. MIT Press, Cambridge, MA, 1971.
[15]	C. Michaux and F. Point. Les ensembles k-reconnaissables sont définissables dans <N,+,V_k>. (the k-recognizable sets are definable in <N,+,V_k>). C. R. Acad. Sci. Paris, Sér. I(303):939-942, 1986.
[16]	D. Perrin. An introduction to automata on infinite words. In M. Nivat, editor, Automata on infinite words, volume 192 of Lect. Notes in Comput. Sci., pages 2-17. Springer, 1984.
[17]	D. 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.
[18]	D. Perrin and J. E. Pin. First order logic and star-free sets. J. Comput. System Sci., 32:393-406, 1986.
[19]	M.O. Rabin. Decidability of second-order theories and automata on infinite trees. Transactions of the American Mathematical Society, 141:1-35, 1969.
[20]	C. Rispal. Automates sur les ordres linéaires: complémentation. PhD thesis, University of Marne-la-Vallée, France, 2004.
[21]	C. Rispal and O. 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.
[22]	J. G. Rosenstein. Linear orderings. Academic Press, New York, 1982.
[23]	M. P. Schützenberger. On finite monoids having only trivial subgroups. Inform. Control, 8:190-194, 1965.
[24]	S. Shelah. The monadic theory of order. Annals of Mathematics, 102:379-419, 1975.
[25]	W. Thomas. Star free regular sets of ω-sequences. Inform. Control, 42:148-156, 1979.
[26]	W. Thomas. Ehrenfeucht games, the composition method, and the monadic theory of ordinal words. In Structures in Logic and Computer Science, A Selection of Essays in Honor of A. Ehrenfeucht, number 1261 in Lect. Notes in Comput. Sci., pages 118-143. Springer-Verlag, 1997.
[27]	W. Thomas. Languages, automata, and logic. In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, volume III, pages 389-455. Springer-Verlag, 1997.
[28]	J. Wojciechowski. Finite automata on transfinite sequences and regular expressions. Fundamenta informaticæ, 8(3-4):379-396, 1985.

Download

PDF file (145 Ko)

24 January 2015 22:06:24