Tree automata and automata on linear orderings
Bruyère, Véronique ; Carton, Olivier ; Sénizergues, Géraud
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009), p. 321-338 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

We show that the inclusion problem is decidable for rational languages of words indexed by scattered countable linear orderings. The method leans on a reduction to the decidability of the monadic second order theory of the infinite binary tree [9].

Publié le : 2009-01-01
DOI : https://doi.org/10.1051/ita/2009009
Classification:  68Q45,  03D05 
@article{ITA_2009__43_2_321_0,
     author = {Bruy\`ere, V\'eronique and Carton, Olivier and S\'enizergues, G\'eraud},
     title = {Tree automata and automata on linear orderings},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {43},
     year = {2009},
     pages = {321-338},
     doi = {10.1051/ita/2009009},
     mrnumber = {2512262},
     zbl = {1166.68022},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2009__43_2_321_0}
}

Bruyère, Véronique; Carton, Olivier; Sénizergues, Géraud. Tree automata and automata on linear orderings. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009) pp. 321-338. doi : 10.1051/ita/2009009. http://gdmltest.u-ga.fr/item/ITA_2009__43_2_321_0/

[1] V. Bruyère and O. Carton, Automata on linear orderings, edited by J. Sgall, A. Pultr and P. Kolman, MFCS'2001. Lect. Notes Comput. Sci. 2136 (2001) 236-247. | MR 1907015 | Zbl 0999.68100

[2] V. Bruyère, O. Carton and G. Sénizergues, Tree automata and automata on linear orderings, in Proceedings WORDS'03. Lect. Notes Comput. Sci. 27 (2003) 222-231. TUCS General Publication. | MR 2081356 | Zbl 1040.68072

[3] V. Bruyère and O. Carton, Automata on linear orderings. J. Comput. System Sci. 73 (2007) 1-24. | MR 2279028 | Zbl 1178.68307

[4] O. Carton, Accessibility in automata on scattered linear orderings, edited by K. Diks and W. Rytter, MFCS'2002. Lect. Notes Comput. Sci. 2420 (2002) 155-164. | MR 2064454 | Zbl 1014.68081

[5] B. Courcelle, Frontiers of infinite trees. RAIRO Theoretical Informatics 12 (1978) 319-337. | Numdam | MR 517634 | Zbl 0411.68065

[6] F. Hausdorff, Grundzüge einer Theorie der geordneten Mengen. Math. Ann. 65 (1908) 435-505. | JFM 39.0099.01 | MR 1511478

[7] S. Heilbrunner, An algorithm for the solution of fixed-point equations for infinite words. RAIRO Theoretical Informatics 14 (1980) 131-141. | Numdam | MR 581673 | Zbl 0433.68062

[8] S.C. Kleene, Representation of events in nerve nets and finite automata, edited by C.E. Shannon, Automata studies, 3-41. Princeton University Press, Princeton (1956). | MR 77478

[9] M.O. Rabin, Decidability of second-order theories and automata on infinite trees. Trans. Amer. Math. Soc. 141 (1969) 1-35. | MR 246760 | Zbl 0221.02031

[10] C. Rispal and O. Carton, Complementation of rational sets on countable scattered linear orderings. J. Found. Comput. Sci. 16 (2005) 767-786. | MR 2159389 | Zbl 1161.68551

[11] J.G. Rosenstein, Linear Orderings. Academic Press, New York (1982). | MR 662564 | Zbl 0488.04002

[12] W. Thomas, On frontiers of regular sets. RAIRO Theoretical Informatics 20 (1986) 371-381. | Numdam | MR 880841 | Zbl 0639.68071