Bloom, Stephen L.; Ésik, Zoltán Deciding whether the frontier of a regular tree is scattered. (English) Zbl 1066.68060 Fundam. Inform. 55, No. 1, 1-21 (2003). Summary: While thinking of how to generalize some facts about ordinal words (labelings of ordinals) in [S. L. Boom and C. Choffrut, Theor. Comput. Sci. 259, 533–548 (2001; Zbl 0972.68106)] 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. 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. Cited in 7 Documents MSC: 68Q45 Formal languages and automata Keywords:ordinal words; regular sets of binary strings; finite automata Citations:Zbl 0972.68106 PDFBibTeX XMLCite \textit{S. L. Bloom} and \textit{Z. Ésik}, Fundam. Inform. 55, No. 1, 1--21 (2003; Zbl 1066.68060)