×

Deciding whether the frontier of a regular tree is scattered. (English) Zbl 1066.68060

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.

MSC:

68Q45 Formal languages and automata

Citations:

Zbl 0972.68106
PDFBibTeX XMLCite