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 $\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.

Theorem 22 Shallit and Wang [ 19 , Theorem 9 ]

Suppose $w\in \Sigma ^*$ is $k$th-power-free for some integer $k\ge 2$, i.e., $w$ contains no subword of the form $x^k$ with $x\ne \varepsilon $. Then $A(w)\ge \frac{\lvert w\rvert +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) \le b(n):={\lfloor } n/2 {\rfloor } + 1\text{.} \]

Proof ▶

Let $n=2m+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 ${\lt}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,2m+1}=1$ and $W_{m,2s+1}=0$ whenever $s{\lt}m$.

If $m=0$, the NFA $K_m$ is simply

\[ \xymatrix{ \text{start}\ar[r]& *+[Foo]{q_0}\ar @(ul,ur)_{x_1} } \]

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:

\[ \xymatrix{ \text{start}\ar[r] & *+[Foo]{q_0}\ar @/_/[r]_{x_1} & *+[Fo]{K_{m-1}}\ar @/_/[l]_{x_n} } \]

An accepting walk of length $2m+1$ consists of the edge labeled $x_1$, followed by a walk of length $2m-1$, followed by the edge labeled $x_n$. The walk of length $2m-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{\lt}t\le 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 $\ell _0,\dots ,\ell _t$ where if $t{\gt}0$ and $W_{m-1,\ell _i}{\gt}0$ then $\ell _i$ is even. So if $t{\gt}0$, they have lengths that must add up to an odd number

\[ \sum _{i=0}^{t} \ell _i = 2m-1 - 2t \]

which is impossible.

If $n{\gt}0$ is even then $x=ya$ where $\lvert y\rvert $ is odd; by the second subword inequality ?? ??, $A_N(x)\le A_N(y)+1$, as desired. Finally, if $n=0$ then the result follows from $A_N(\varepsilon )=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_1x_2x_3x_4 \cdots x_n$ of length $n = 2m + 1$.