Geodesic
Tree automata and automata on linear orderings
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009) no. 2, pp. 321-338.

Voir la notice de l'article provenant de la source Numdam

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].

DOI : 10.1051/ita/2009009
Classification : 68Q45, 03D05
Keywords: finite automata, words over linear orderings-trees, monadic second order logics 
@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},
     pages = {321--338},
     publisher = {EDP-Sciences},
     volume = {43},
     number = {2},
     year = {2009},
     doi = {10.1051/ita/2009009},
     mrnumber = {2512262},
     zbl = {1166.68022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2009009/}
}
TY  - JOUR
AU  - Bruyère, Véronique
AU  - Carton, Olivier
AU  - Sénizergues, Géraud
TI  - Tree automata and automata on linear orderings
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2009
SP  - 321
EP  - 338
VL  - 43
IS  - 2
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ita/2009009/
DO  - 10.1051/ita/2009009
LA  - en
ID  - ITA_2009__43_2_321_0
ER  - 
%0 Journal Article
%A Bruyère, Véronique
%A Carton, Olivier
%A Sénizergues, Géraud
%T Tree automata and automata on linear orderings
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2009
%P 321-338
%V 43
%N 2
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ita/2009009/
%R 10.1051/ita/2009009
%G en
%F 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) no. 2, pp. 321-338. doi : 10.1051/ita/2009009. http://geodesic.mathdoc.fr/articles/10.1051/ita/2009009/

[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. | Zbl | MR

[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. | Zbl | MR

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

[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. | Zbl | MR

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

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

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

[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

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

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

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

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

Cité par Sources :