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