[Up]

Logic and Rational Languages of Words Indexed by Linear Orderings

Copyright informations

This paper has been published in Theory of Computing Systems (special issue of CSR'08). Volume 46, Issue 4 (2010), and the copyright is owned by Springer. The final publication is available at www.springerlink.com.

This paper is the journal version of a work presented at CSR'08.

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," J. Comput. System Sci., vol. 63, no. 3, pp. 394-431, 2001.
  2. N. Bedon and C. Rispal, "Schützenberger and Eilenberg theorems for words on linear orderings", in DLT'2005 (C. De Felice and A. Restivo, eds.), vol. 3572 of Lect. Notes in Comput. Sci., pp. 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., vol. 17, no. 3, pp. 519-542, 2006.
  4. V. Bruyère and O. Carton, "Automata on linear orderings", in MFCS'2001 (J. Sgall, A. Pultr, and P. Kolman, eds.), vol. 2136 of Lect. Notes in Comput. Sci., pp. 236-247, 2001.
  5. V. Bruyère and O. Carton, "Hierarchy among automata on linear orderings", in Foundation of Information technology in the era of network and mobile computing (R. Baeza-Yate, U. Montanari, and N. Santoro, eds.), pp. 107-118, Kluwer Academic Publishers, 2002.
  6. V. Bruyère and O. Carton, "Automata on linear orderings", J. Comput. System Sci., vol. 73, no. 1, pp. 1-24, 2007.
  7. V. Bruyère, O. Carton, and G. Sénizergues, "Tree automata and automata on linear orderings", in WORDS'2003 (T. Harju and J. Karhumäki, eds.), pp. 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., vol. 6, pp. 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, pp. 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, pp. 2-23, North Holland, 1965.
  11. O. Carton, "Accessibility in automata on scattered linear orderings", in MFCS'2002 (K.Diks and W.Rytter, eds.), vol. 2420 of Lect. Notes in Comput. Sci., pp. 155-164, 2002.
  12. Y. Gurevich, "Monadic second-order theories", in Model-Theoretic Logics (J. Barwise and S. Feferman, eds.), pp. 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, vol. 33, 1977.
  14. R. McNaughton and S. Papert, Counter free automata. Cambridge, MA: MIT Press, 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, vol. S\'er. I, no. 303, pp. 939-942, 1986.
  16. D. Perrin, "An introduction to automata on infinite words", in Automata on infinite words (M. Nivat, ed.), vol. 192 of Lect. Notes in Comput. Sci., pp. 2-17, Springer, 1984.
  17. D. 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.
  18. D. Perrin and J. E. Pin, "First order logic and star-free sets", J. Comput. System Sci., vol. 32, pp. 393-406, 1986.
  19. M.O. Rabin, "Decidability of second-order theories and automata on infinite trees", Transactions of the American Mathematical Society, vol. 141, pp. 1-35, 1969.
  20. C. Rispal and O. Carton, "Complementation of rational sets on countable scattered linear orderings", in DLT'2004 (C. S. Calude, E. Calude, and M. J. Dinneen, eds.), vol. 3340 of Lect. Notes in Comput. Sci., pp. 381-392, 2004.
  21. C. Rispal, Automates sur les ordres linéaires: complémentation.. PhD thesis, University of Marne-la-Vallée, France, 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, vol. 8, pp. 190-194, 1965.
  24. S. Shelah, "The monadic theory of order", Annals of Mathematics, vol. 102, pp. 379-419, 1975.
  25. H. Straubing, Finite automata, formal logic and circuit complexity. Birkhäuser, 1994.
  26. W. Thomas, "Star free regular sets of $\omega$-sequences", Inform. Control, vol. 42, pp. 148-156, 1979.
  27. 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, no. 1261 in Lect. Notes in Comput. Sci., pp. 118-143, Springer-Verlag, 1997.
  28. W. Thomas, "Languages, automata, and logic", in Handbook of Formal Languages (G. Rozenberg and A. Salomaa, eds.), vol. III, pp. 389-455, Springer-Verlag, 1997.
  29. J. Wojciechowski, "Finite automata on transfinite sequences and regular expressions", Fundamenta informaticae, vol. 8, no. 3-4, pp. 379-396, 1985.

Download

PDF file (267 Ko)

Valid HTML 4.01!


My email address 24 January 2015 22:06:46