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
Cet article a éte moissonné depuis la source Numdam

Voir la notice de l'article

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},
     year = {2009},
     publisher = {EDP-Sciences},
     volume = {43},
     number = {2},
     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

Cité par Sources :