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].
@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
Cité par Sources :