Accessibility in Automata on Scattered Linear Orderings
In a preceding paper, automata have been introduced for words indexed by linear orderings. These automata are a generalization of automata on transfinite words introduced by Buchi. In this paper, we show that if only words indexed by scattered linear orderings are considered, the accessibility and the emptiness in these automata can be checked in time nm2 where n and m are the number of states and the number of transitions. This solves the problem for automata on transfinite words.