On the structure of compacted subword graphs of ThueMorse words and their applications ? ??
We investigate how syntactic properties of ThueMorse words are related to special type of automata/graphs. The directed acyclic subword graph (dawg, in short) is a useful deterministic automaton accepting all suffixes of the word. Its compacted version (resulted by compressing chains of states) is denoted by cdawg. The cdawgs of ThueMorse words have regular and very simple structure, in particular they offer a powerful (exponential) compression of the set of all subwords in case of finite ThueMorse words. Using the special structure of cdawgs we present several unknown properties of ThueMorse words as well as new (graph-based) proofs of some well-known properties. In particular we show a simple algorithm that checks, for a given string w, if w is a subword of a ThueMorse word and computes its number of occurrences in n -th ThueMorse word in O ( | w | + log n ) time and O(1) O ( 1 ) space. Additionally, a slight modification of the compact dawg of the infinite ThueMorse word yields an infinite graph with 2-counting property.
compacted subword graph thuemorse word graph counting property