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 [ 19 ] 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 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.

Theorem 22 Shallit and Wang [ 19 , Theorem 9 ]

Suppose $w \in Σ^{*}$ is $k$ th-power-free for some integer $k \geq 2$ , i.e., $w$ contains no subword of the form $x^{k}$ with $x \neq ε$ . Then $A (w) \geq \frac{| w | + 1}{k}$ .

The way we strengthen their results is by considering a variation on squarefreeness and cube-freeness, overlap-freeness. This notion also goes by the names of irreducibility and strong cube-freeness in the combinatorial literature. We also take up an idea from [ 19 , Theorem 8 ] and use it to show that the natural decision problem associated with nondeterministic automatic complexity is in the complexity class E = DTIME( $2^{O (n)}$ ). This result is a theoretical complement to the practical fact that the nondeterministic automatic complexity can be computed reasonably quickly, a fact that enabled the creation of the lookup service at [ 10 ] .

2.1 Introduction

Theorem 23 Hyde [ 6 ]

✓

The nondeterministic automatic complexity $A_{N} (x)$ of a string $x$ of length $n$ satisfies

A_{N} (x) \leq b (n) := ⌊ n / 2 ⌋ + 1 .

Proof ▶

Let $n = 2 m + 1$ be odd and let $K_{m}$ be a Kayleigh graph, Figure 2.1. For a proof by induction it is convenient to label the states in the opposite order of the usual:

$\begin{tikzpicture} [shorten >=1pt,node distance=1.5cm,on grid,auto] \tikzstyle{every state}=[fill={rgb:black,1;white,10}] \node[state,initial, accepting] (q_0) {$q_m$}; \node[state] (q_1) [right=of q_0 ] {$q_{m-1}$}; \node[state] (q_2) [right=of q_1 ] {$q_{m-2}$}; \node[state] (q_3) [right=of q_2 ] {$q_{m-3}$}; \node (q_dots) [right=of q_3 ] {$\dots$}; \node[state] (q_{m-1}) [right=of q_dots] {$q_{1}$}; \node[state] (q_m) [right=of q_{m-1} ] {$q_0$}; \path[->] (q_0) edge [bend left] node {$x_1$} (q_1) (q_1) edge [bend left] node {$x_2$} (q_2) (q_2) edge [bend left] node {$x_3$} (q_3) (q_3) edge [bend left] node [pos=.45] {$x_4$} (q_dots) (q_dots) edge [bend left] node [pos=.6] {$x_{m-1}$} (q_{m-1}) (q_{m-1}) edge [bend left] node [pos=.56] {$x_m$} (q_m) (q_m) edge [loop above] node {$x_{m+1}$} () (q_m) edge [bend left] node [pos=.45] {$x_{m+2}$} (q_{m-1}) (q_{m-1}) edge [bend left] node [pos=.4] {$x_{m+3}$} (q_dots) (q_dots) edge [bend left] node [pos=.6] {$x_{n-3}$} (q_3) (q_3) edge [bend left] node {$x_{n-2}$} (q_2) (q_2) edge [bend left] node {$x_{n-1}$} (q_1) (q_1) edge [bend left] node {$x_n$} (q_0); \end{tikzpicture}$

Then we just observe that there are no walks of odd length $< n$ accepted, and there is exactly one walk of odd length $n$ accepted, and these two observations persist inductively.

For a number perspective, let $W_{m, k}$ be the number of accepting walks in $K_{M}$ of length $k$ . We show by induction on $m$ that $W_{m, 2 m + 1} = 1$ and $W_{m, 2 s + 1} = 0$ whenever $s < m$ .

If $m = 0$ , the NFA $K_{m}$ is simply

Misplaced &

which accepts one word of length 1 and, of course, no word of shorter odd lengths.

For the inductive step, note that $K_{m}$ is schematically:

Misplaced &

An accepting walk of length $2 m + 1$ consists of the edge labeled $x_{1}$ , followed by a walk of length $2 m - 1$ , followed by the edge labeled $x_{n}$ . The walk of length $2 m - 1$ can stay within $K_{m - 1}$ in which case by induction there is exactly one possible walk. Or it can venture out of $K_{m - 1}$ to visit $q_{0}$ a certain number $0 < t \leq m - 1$ of times; each such time contributes a walk of length 2. Between these times, an accepting walk in $K_{m - 1}$ must be performed.

By the induction hypothesis, these walks have lengths $ℓ_{0}, \dots, ℓ_{t}$ where if $t > 0$ and $W_{m - 1, ℓ_{i}} > 0$ then $ℓ_{i}$ is even. So if $t > 0$ , they have lengths that must add up to an odd number

\sum_{i = 0}^{t} ℓ_{i} = 2 m - 1 - 2 t

which is impossible.

If $n > 0$ is even then $x = y a$ where $| y |$ is odd; by the second subword inequality ?? ??, $A_{N} (x) \leq A_{N} (y) + 1$ , as desired. Finally, if $n = 0$ then the result follows from $A_{N} (ε) = 1$ . □

\begin{tikzpicture} [shorten >=1pt,node distance=1.5cm,on grid,auto]
\tikzstyle{every state}=[fill={rgb:black,1;white,10}]
\node[state,initial, accepting] (q_0) {$q_0$};
\node[state] (q_1) [right=of q_0 ] {$q_1$};
\node[state] (q_2) [right=of q_1 ] {$q_2$};
\node[state] (q_3) [right=of q_2 ] {$q_3$};
\node (q_dots) [right=of q_3 ] {$\dots$};
\node[state] (q_{m-1}) [right=of q_dots] {$q_{m-1}$};
\node[state] (q_m) [right=of q_{m-1} ] {$q_m$};
\path[->]
(q_0) edge [bend left] node {$x_1$} (q_1)
(q_1) edge [bend left] node {$x_2$} (q_2)
(q_2) edge [bend left] node {$x_3$} (q_3)
(q_3) edge [bend left] node [pos=.45] {$x_4$} (q_dots)
(q_dots) edge [bend left] node [pos=.6] {$x_{m-1}$} (q_{m-1})
(q_{m-1}) edge [bend left] node [pos=.56] {$x_m$} (q_m)
(q_m) edge [loop above] node {$x_{m+1}$} ()
(q_m) edge [bend left] node [pos=.45] {$x_{m+2}$} (q_{m-1})
(q_{m-1}) edge [bend left] node [pos=.4] {$x_{m+3}$} (q_dots)
(q_dots) edge [bend left] node [pos=.6] {$x_{n-3}$} (q_3)
(q_3) edge [bend left] node {$x_{n-2}$} (q_2)
(q_2) edge [bend left] node {$x_{n-1}$} (q_1)
(q_1) edge [bend left] node {$x_n$} (q_0);
\end{tikzpicture} — Figure 2.1 A nondeterministic finite automaton, a *Kayleigh graph*, that only accepts one string $x = x_{1} x_{2} x_{3} x_{4} \dots x_{n}$ of length $n = 2 m + 1$ .