Deciding whether the frontier of a regular tree is scattered
Stephen L. Bloom, Zoltán Ésik · Fundamenta Informaticae · 2002
While thinking of how to generalize some facts about ordinal words (labelings of ordinals) in [BlCho01] to linearly ordered words (labelings of linear orders), the authors rediscovered the natural classes of the “regular words” and the “scattered regular words”, described here. It turns out that these words are isomorphic to the frontiers of regular trees, considered earlier by Courcelle [Cour78], Heilbrunner [Heil80], and Thomas [Thom86]. The current paper contains some new descriptions of this class related to properties of regular sets of binary strings, and uses finite automata to decide various natural questions concerning these words. In particular, we show that there is a polynomial time algorithm to decide, given a DFA which determines a regular word, whether this word is scattered.