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  [ 15 ] on the complexity of the infinite Thue–Morse word \(\mathbf t\). Moreover, viewed through an NFA lens we can, in a sense, characterize the complexity of \(\mathbf t\) exactly. A main technical idea is to extend the following result, which says that not only do squares, cubes and higher powers of a word have low complexity, but a word completely free of such powers must conversely have high complexity.