05551440

j

05551440 Bruy\`ere, V\'eronique Carton, Olivier S\'enizergues, G\'eraud Tree automata and automata on linear orderings. Theor. Inform. Appl. 43, No. 2, 321-338 (2009). 2009 EDP Sciences, Les Ulis EN finite automata words over linear orderings trees monadic second-order logic

doi:10.1051/ita/2009009

Summary: 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.