TREE AUTOMATA AND AUTOMATA ON LINEAR ORDERINGS

摘要

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 [M.O. Rabin, Trans. Amer. Math. Soc. 141 (1969) 1-35].