Tree Automata and Automata on Linear Orderings
Université de Mons-Hainaut, France; Veronique.Bruyere@umh.ac.be
2 LIAFA, Université Paris 7, France; Olivier.Carton@liafa.jussieu.fr
3 LaBRI, Université de Bordeaux I, France; firstname.lastname@example.org
Accepted: 5 November 2008
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 .
Mathematics Subject Classification: 68Q45 / 03D05.
Key words: Finite automata / words over linear orderings-trees / monadic second order logics.
© EDP Sciences, 2008