Nondeterministic automatic complexity of overlap-free and almost square-free words

Kayleigh K. Hyde¹ ; Bjørn Kjos-Hanssen²

¹Chapman University
²University of Hawaii at Manoa

The electronic journal of combinatorics, Tome 22 (2015) no. 3

Résumé

Shallit and Wang studied deterministic automatic complexity of words. They showed that the automatic Hausdorff dimension $I(\mathbf t)$ of the infinite Thue word satisfies $1/3\le I(\mathbf t)\le 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 Fraenkel and Simpson, or if $x$ is a overlap-free binary word such as the infinite Thue--Morse word, then $D(x)\le 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)\ge d$ for given $x$, $d$ belongs to $\mathrm{NP}\cap \mathrm{E}$.

Détail

DOI : 10.37236/4851

Classification : 68R15, 68Q30, 68Q45
Mots-clés : automatic complexity, nondeterministic finite automata, almost square-free words, strongly cube-free words, combinatorics on words