CLR cover

Problem 80: Building Long Square-Free Words

\( \def\sa#1{\tt{#1}} \def\dd{\dot{}\dot{}} \)

A word is square free if it does not contain any factor of the form $uu$ for a non-empty word $u$. Generating long square-free words is meaningful only for alphabets of size at least three because the longest square-free words on a two-letter alphabet like $\{\sa{a},\sa{b}\}$ are $\sa{aba}$ and $\sa{bab}$.

The goal of the problem is to design an algorithm generating long square-free words in an almost real-time way. Algorithm SquareFreeWord does it using the function $\mbox{bin-parity}(n)$ that denotes the parity (0 if even, 1 if odd) of the number of $\sa{1}$'s in the binary representation of the natural number $n$. The delay between computing two outputs is proportional to the evaluation of that function.

SquareFreeWord$()$ 
    \begin{algorithmic}
  \STATE $\mathit{prev}\leftarrow 0$
  \FOR{$n\leftarrow 1$ \TO $\infty$}
    \COMMENT{$\mathit{prev} = \max\{i \mid i\lt n \mbox{ and } \mbox{bin-parity}(i)=0\}$}
    \IF{$\mbox{bin-parity}(n)=0$}
      \STATE output $(n-\mathit{prev})$
      \STATE $\mathit{prev}\leftarrow n$
    \ENDIF
  \ENDFOR
    \end{algorithmic}

The generated word $\alpha$ starts with: $\sa{3}\,\sa{2}\,\sa{1}\,\sa{3}\,\sa{1}\,\sa{2}\,\sa{3}\,\sa{2}\,\sa{1} \,\sa{2}\,\sa{3}\,\sa{1} \cdots$.

Show Algorithm SquareFreeWord constructs arbitrarily long square-free words over the ternary alphabet $\{\sa{1},\sa{2},\sa{3}\}$.
The condition at line 4 holds only when $n$ is the position of an occurrence of $\sa{a}$ in the Thue-Morse word $\mathbf{t}$.

References

  • F. Brandenburg. Uniformly growing $k$-th power-free homomorphisms. Theor. Comput. Sci., 23:69-82, 1983.
  • M. Lothaire. Combinatorics on Words. Addison-Wesley, 1983. Reprinted in 1997.
  • A. Restivo and S. Salemi. Overlap-free words on two symbols. In M. Nivat and D. Perrin, editors, Automata on Infinite Words, École de Printemps d'Informatique Théorique, Le Mont Dore, May 14-18, 1984, volume 192 of Lecture Notes in Computer Science, pages 198-206. Springer, 1985.