Logic and bounded-width rational languages of posets over countable scattered linear orderings

Copyright informations

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

Abstract

In this paper we consider languages of labelled N-free posets over countable and scattered linear orderings. We prove that a language of such posets is series-rational if and only if it is recognizable by a finite depth-nilpotent algebra if and only if it is bounded-width and monadic second-order definable. This extends previous results on languages of labelled N-free finite and ω-posets and on languages of labelled countable and scattered linear orderings.

References

[1]	Jorge Almeida. Finite semigroups and universal algebra, volume 3 of Series in algebra. World Scientific, 1994.
[2]	Nicolas Bedon, Alexis Bès, Olivier Carton, and Chloé Rispal. Logic and rational languages of words indexed by linear orderings. In Edward A. Hirsch, Alexander A. Razborov, Alexei Semenov, and Anatol Slissenko, editors, Computer Science in Russia 2008, 3rd International Symposium, Moscow, volume 5010 of Lect. Notes in Comput. Sci., pages 76-85. Springer-Verlag, June 2008.
[3]	Nicolas Bedon and Chloé Rispal. Series-parallel languages on scattered and countable posets. In Ludek Kucera and Antonín Kucera, editors, MFCS'07, volume 4708 of Lect. Notes in Comput. Sci., pages 477-488. Springer-Verlag, August 2007.
[4]	Alexis Bès and Olivier Carton. A Kleene theorem for languages of words indexed by linear orderings. Int. J. Found. Comput. Sci., 17(3):519-542, 2006.
[5]	Véronique Bruyère and Olivier Carton. Automata on linear orderings. In M. Ito and M. Toyama, editors, DLT'2002, volume 2450 of Lect. Notes in Comput. Sci., pages 103-115. Springer-Verlag, 2002.
[6]	J. Richard Büchi. On a decision method in the restricted second-order arithmetic. In Proc. Intern. Congr. on Logic, Methodology and Philosophy of Science, Berkeley 1960, pages 1-11, Stanford, California, 1962. Stanford University Press.
[7]	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 1964, pages 2-23. North Holland, 1964.
[8]	Olivier Carton and Chloé Rispal. Complementation of rational sets on countable scattered linear orderings. Int. J. Found. Comput. Sci., 16(4):767-786, August 2005.
[9]	Heinz-Dieter Ebbinghaus and Jörg Flum. Finite model theory. Springer monographs in mathematics. Springer, 2nd edition, 1999.
[10]	Zoltán Ésik and Z.L. Németh. Automata on series-parallel biposets. In W. Kuich, G. Rozenberg, and A. Salomaa, editors, DLT'2001, volume 2295 of Lect. Notes in Comput. Sci., pages 217-227. Springer-Verlag, 2002.
[11]	Dietrich Kuske. Infinite series-parallel posets: logic and languages. In ICALP 2000, volume 1853 of Lect. Notes in Comput. Sci., pages 648-662. Springer-Verlag, 2000.
[12]	Dietrich Kuske. Towards a language theory for infinite N-free pomsets. Theoret. Comput. Sci., 299:347-386, 2003.
[13]	H. Laüchli and J. Leonard. On the elementary theory of linear order. Fund. Math., 59:109-116, 1966.
[14]	Kamal Lodaya and Pascal Weil. Series-parallel posets: algebra, automata and languages. In M. Morvan, Ch. Meinel, and D. Krob, editors, STACS'98, volume 1373 of Lect. Notes in Comput. Sci., pages 555-565. Springer-Verlag, 1998.
[15]	Kamal Lodaya and Pascal Weil. Series-parallel languages and the bounded-width property. Theoret. Comput. Sci., 237(1-2):347-380, 2000.
[16]	Kamal Lodaya and Pascal Weil. Rationality in algebras with a series operation. Inform. Comput., pages 269-293, 2001.
[17]	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.
[18]	Michael Ozer Rabin. Decidability of second-order theories and automata on infinite trees. Trans. Amer. Math. Soc., 141:1-35, 1969.
[19]	Joseph G. Rosenstein. Linear Orderings. Academic Press, 1982.
[20]	Saharon Shelah. The monadic theory of order. Annals of Mathematics, 102(3):379-419, November 1975.
[21]	Wolfgang Thomas. Languages, automata, and logic. In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, volume III, pages 389-455. Springer-Verlag, 1997.
[22]	Jacobo Valdes. Parsing flowcharts and series-parallel graphs. Technical Report STAN-CS-78-682, Computer science departement of the Stanford University, Standford, Ca., 1978.
[23]	Jacobo Valdes, Robert E. Tarjan, and Eugene L. Lawler. The recognition of series parallel digraphs. SIAM J. Comput., 11:298-313, 1982.
[24]	Thomas Wilke. An Eilenberg theorem for $\infty$-languages. In Automata, Languages and Programming: Proc. of 18th ICALP Conference, pages 588-599. Springer-Verlag, 1991.

Download

PDF file

24 January 2015 22:06:04