Tree Automata and Automata on Linear Orderings
Véronique Bruyère, Olivier Carton, Géraud Sénizergues · RAIRO - Theoretical Informatics and Applications · 2009
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].