CLR cover

Problem 57: Avoidability of Binary Words

Some patterns occur in all long enough words. They are said to be unavoidable. The notion obviously depends on the alphabet size and in the problem we consider binary patterns.

A word $w$ is said to avoid a set $X$ of words if no factor of $w$ belongs to $X$. The set $X$ is said to be avoidable if there is an infinite word avoiding it, or equivalently on a finite alphabet, if there are infinitely any words avoiding it. The goal is to test if a set of words drawn from the binary alphabet $\Bi=\{\sa{a},\sa{b}\}$ is avoidable.

To design the test we define two reductions on a set $X\subseteq\Bi^+$.

reduce1 (remove super-word):
If $x,y\in X$ and $x$ is a factor of $y$ remove $y$ from $X$.
reduce2 (chop last letter):
If $x$ is a suffix of $y\neq\varepsilon$ and $x\bar{a},ya\in X$ substitute $y$ for $ya$ in $X$ (the bar morphism exchanges $\sa{a}$ and $\sa{b}$).
Avoidable$(X \textrm{ non-empty set of binary words})$ 
    \begin{algorithmic}
  \WHILE{$\mbox{reduce1 or reduce2 are applicable to } X$}
    \STATE $X\leftarrow \mbox{reduce1}(X)$ \OR $\mbox{reduce2}(X)$
  \ENDWHILE
  \IF{$X\ne \{\tt{a},\tt{b}\}$}
    \RETURN{True}
  \ELSE
    \RETURN{False}
  \ENDIF
    \end{algorithmic}

Show that a set $X$ of binary words is avoidable if and only if Avoidable$(X)$=True.

Show that a set $X\subseteq\Bi^{\leq n}$ is avoidable if and only if it is avoided by a word of length larger than $2^{n-1}+n-2$ and that the bound is optimal.

References

  • M. Crochemore, M. Lerest, and P. Wender. An optimal test on finite unavoidable sets of words. Inf. Process. Lett., 16(4):179-180, 1983.
  • M. Lothaire. Combinatorics on Words. Addison-Wesley, 1983. Reprinted in 1997.