Nondeterministic automatic complexity of overlap-free and almost square-free words (Q490407)

Summary: \textit{J. Shallit} and \textit{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 \textit{A. S. Fraenkel} and \textit{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}\).