Automatic Complexity

2 Nondeterminism and overlap-free words

In this chapter we develop some properties of nondeterministic automatic complexity. As a corollary we get a strengthening of a result of Shallit and Wang [69] on the complexity of the infinite Thue–Morse word t. Moreover, viewed through an NFA lens we can, in a sense, characterize the complexity of t exactly. A main technical idea is to extend the following result, which says not only that squares, cubes, and higher powers of a word have low complexity, but also that a word completely free of such powers must conversely have high complexity.

Theorem 2.1 (Shallit and Wang [69, Theorem 9]). Suppose $\mathit{w}\in {\mathrm{\Sigma }}^{\ast }$ is kth-power-free for some integer $\mathit{k}\ge 2$, i. e., w contains no subword of the form ${\mathit{x}}^{\mathit{k}}$ with $\mathit{x}\ne \mathit{\epsilon }$. Then ...