Summary: J. Shallit and M.-W. Wang [J. Autom. Lang. Comb. 6, No. 4, 537–554 (2001; Zbl 1004.68077)] studied deterministic automatic complexity of words. They showed that the automatic Hausdorff dimension \(I(\mathbf t)\) of the infinite Thue word satisfies \(1/3\leq I(\mathbf t)\leq 1/2\). We improve that result by showing that \(I(\mathbf t)= 1/2\). We prove that the nondeterministic automatic complexity \(A_N(x)\) of a word \(x\) of length \(n\) is bounded by \(b(n):=\lfloor n/2\rfloor + 1\). This enables us to define the complexity deficiency \(D(x)=b(n)-A_N(x)\). If \(x\) is square-free then \(D(x)=0\). If \(x\) is almost square-free in the sense of A. S. Fraenkel and R. J. Simpson [Electron. J. Comb. 2, Research paper R2, 9 p. (1995; Zbl 0816.11007)], or if \(x\) is a overlap-free binary word such as the infinite Thue-Morse word, then \(D(x)\leq 1\). On the other hand, there is no constant upper bound on \(D\) for overlap-free words over a ternary alphabet, nor for cube-free words over a binary alphabet.
The decision problem whether \(D(x)\geq d\) for given \(x\), \(d\) belongs to \(\mathrm{NP}\cap \mathrm{E}\).