Minimal forbidden factors of circular words (Q5915743)

Let \(w\) be a finite word. A word \(v\) is a \textit{minimal forbidden factor} of \(w\) if \(v\) does not appear as a factor in \(w\) but all the proper factors of \(v\) do. This notion can be extended to circular words (or, necklaces). The authors consider the set of factors of a circular word \(w\) as the infinite set of factors \(w^\omega=www\cdots\). They show that its set of minimal forbidden factors is always finite. They investigate combinatorial properties of minimal forbidden factors of circular words. They prove that the automaton built by the so-called ``L-automaton algorithm'' on the input trie recognizing the set of minimal forbidden factors of a circular word is minimal. In the second part of the paper, the results are illustrated on the special case of the circular Fibonacci words.