Dependencies

The critical exponent $\mathrm{ce}(w)$ of an infinite word $\mathbf{w}$ is defined by

Let $x$ be a word in a finite alphabet $\mathrm{\Sigma }$. We have $A^{-}(x)\le A(x)$. If $|x|=1$ and $|\mathrm{\Sigma }|>1$ then $A^{-}(x)=1<2=A(x)$.

Let $\mathrm{\Sigma }$ be a finite alphabet and let $Q$ be a finite set whose elements are called states. A nondeterministic finite automaton (NFA) is a 5-tuple $M=(Q,\mathrm{\Sigma },\delta ,q_0,F).$ The transition function $\delta :Q\times \mathrm{\Sigma }\to \mathcal{P}(Q)$ maps each $(q,b)\in Q\times \mathrm{\Sigma }$ to a subset of $Q$. Within $Q$ we find the initial state $q_0\in Q$ and the set of final states $F\subseteq Q$. The function $\delta$ is extended to a function ${\delta }^{\ast }:Q\times {\mathrm{\Sigma }}^{\ast }\to \mathcal{P}(Q)$ by structural induction:

Overloading notation, we may also write $\delta ={\delta }^{\ast }$. The language accepted by $M$ is

A deterministic finite automaton (DFA) is also a 5-tuple $M=(Q,\mathrm{\Sigma },\delta ,q_0,F).$ In this case, $\delta :Q\times \mathrm{\Sigma }\to Q$ is a total function and is extended to ${\delta }^{\ast }:Q\times {\mathrm{\Sigma }}^{\ast }\to Q$ by

If the domain of $\delta$ is a subset of $Q\times \mathrm{\Sigma }$, $M$ is an incomplete DFA. In this case, $M$ coincides with an NFA with a special property which we can check for effectively. We denote a partial function $f$ from $A$ to $B$ by $f:(\subseteq A)\to B$ or $f⋮A\to B$.

Finally, the set of words accepted by $M$ is

Let $\mathrm{\Sigma }$ be an alphabet. Let DFA${}_{\mathrm{\Sigma }}$ denote the class of all DFAs over $\mathrm{\Sigma }$ and let partDFA${}_{\mathrm{\Sigma }}$ denote the class of all partial DFAs over $\mathrm{\Sigma }$. If a DFA $M$ over $\mathrm{\Sigma }$ has the property that it accepts a string $x$, but no other strings of length $|x|$, i.e.,

then we say that $M$ accepts $x$ uniquely. Let $x\in {\mathrm{\Sigma }}^{\ast }$ with $|x|=n$. Define $A(x,\mathrm{\Sigma })$, the automatic complexity of $x$ (with respect to $\mathrm{\Sigma }$) to be the least number of states in any $M\in {\mathrm{DFA}}_{\mathrm{\Sigma }}$ such that $M$ accepts $x$ uniquely.

If we consider $x$ to be a function $x:[n]\to \mathrm{\Sigma }$, then $x\in {\mathrm{\Sigma }}^{\ast }$ where $\mathrm{\Sigma }=\mathrm{range}(x)$. We define $\tilde{A}(x)=A(x,\mathrm{range}(x))$.

Similarly, we define $A^{-}(x,\mathrm{\Sigma })$, the partial automatic complexity of $x$, to be the least number of states in any $M\in {\mathrm{partDFA}}_{\mathrm{\Sigma }}$ such that $L(M)\cap {\mathrm{\Sigma }}^n=\{x\}$.

Let $L(M)$ be the language recognized by the automaton $M$. Let $x$ be a finite word. The (unique-acceptance) nondeterministic automatic complexity $A_N(w)=A_{Nu}(w)$ of $w$ is the minimum number of states of an NFA $M$ such that $M$ accepts $w$ and the number of walks along which $M$ accepts words of length $|w|$ is 1.

The exact-acceptance nondeterministic automatic complexity $A_{Ne}(w)$ of $w$ is the minimum number of states of an NFA $M$ such that $M$ accepts $w$ and $L(M)\cap {\mathrm{\Sigma }}^{|w|}=\{w\}$.

A de Bruijn word of order $n$ over an alphabet $\mathrm{\Sigma }$ is a sequence $y$ such that every $x\in {\mathrm{\Sigma }}^n$ occurs exactly once as a cyclic substring of $y$.

A digraph $D=(V,E)$ consists of a set of vertices $V$ and a set of edges $E\subseteq V^2$. Let $s,t\in V$. Let $n\ge 0$, $n\in \mathbb{Z}$. A walk of length $n$ from $s$ to $t$ is a function $\mathrm{\Delta }:\{0,1,\dots ,n\}\to V$ such that $\mathrm{\Delta }(0)=s$, $\mathrm{\Delta }(n)=t$, and $(\mathrm{\Delta }(k),\mathrm{\Delta }(k+1))\in E$ for each $0\le k<n$.

A cycle of length $n=|\mathrm{\Delta }|\ge 1$ in $D$ is a walk from $s$ to $s$, for some $s\in V$, such that $\mathrm{\Delta }(t_1)=\mathrm{\Delta }(t_2),t_1\ne t_2⟹\{t_1,t_2\}=\{0,n\}$. Two cycles are disjoint if their ranges are disjoint.

Two occurrences of words $a$ (starting at position $i$) and $b$ (starting at position $j$) in a word $x$ are disjoint if $x=uavbw$ where $u,v,w$ are words and $|u|=i$, $|uav|=j$.

The length of a word $s\in {\mathrm{\Sigma }}^{\ast }$ is defined by induction:

Let $\alpha$ be a word of length $n$, and let ${\alpha }_i$ be the $i^{\text{th}}$ letter of $\alpha$ for $1\le i\le n$. We define the $u^{\text{th}}$ power of $\alpha$ for certain values of $u\in {\mathbb{Q}}_{\ge 0}$ (the set of nonnegative rational numbers) as follows. For $u\in \mathbb{N}$:

• If $u=v+k/n$ where $0<k<n$, and $k$ is an integer, then ${\alpha }^u$ denotes ${\alpha }^v{\alpha }_1\dots {\alpha }_k$ and is called a $u$-power.

The word $w$ is $u$-power-free if no nonempty $v$-power, $v\ge u$, occurs (Definition 5) in $w$. In particular, 2-power-free is called square-free and 3-power-free is called cube-free. Let $\mathbf{w}$ be an infinite word over the alphabet $\mathrm{\Sigma }$, and let $x$ be a finite word over $\mathrm{\Sigma }$. Let $u>0$ be a rational number. The word $x$ is said to occur in $\mathbf{w}$ with exponent $u$ if $x^u$ occurs in $\mathbf{w}$ (Definition 5).

Let $k,t\in \mathbb{N}$ with $k\ge 1$. In an alphabet of cardinality $k$, there exists a $t$-rainbow word of length $k^t+t-1$.

The nondeterministic automatic complexity $A_N(x)$ of a string $x$ of length $n$ satisfies

Suppose $n,t$ are positive integers with $t\le n+1$. A word of length $n$ has $n+1-t$ occurrences of subwords of length $t$.

Let $x,y\in {\mathrm{\Sigma }}^{+}$. Then the following four conditions are equivalent:

1. $xy=yx$.

2. There exists $z\in \mathrm{\Sigma }$ and integers $k,l>0$ such that $x=z^k$ and $y=z^l$.

3. There exist integers $i,j>0$ such that $x^i=y^j$.

Let $B$ be a set and let $P$ be the set of all partial functions from $\mathbb{N}$ to $B$. For each $F:\mathbb{N}\times P\to B$, there is a unique function $G:\mathbb{N}\to B$ such that

for all $n\in \mathbb{N}$.

Let $k,t\in \mathbb{N}$ with $k\ge 1$. In an alphabet of cardinality $k$, a $t$-rainbow word has length at most $k^t+t-1$.

The critical exponent of $\mathbf{w}$ is equal to

Let $c,d,e\in {\mathrm{\Sigma }}^{+}$. The equation $cd=de$ holds iff there exist a nonempty word $u$, a word $v$, and a natural number $p$ such that $c=uv$, $d=(uv{)}^{p}u$, and $e=vu$.

Suppose $w\in {\mathrm{\Sigma }}^{\ast }$ 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 \epsilon$. Then $A(w)\ge \frac{|w|+1}{k}$.

A word $x=x_0\dots x_{n-1}$, or an infinite word $x=x_0{x}_1\dots$, with each $x_i\in \mathrm{\Sigma }$, is viewed as a function $f_x:n\to \mathrm{\Sigma }$ with $f_x(i)=x_i$. An occurrence of $y=y_0\dots y_{m-1}$ in $x$ is a function $f_x\upharpoonright [a,a+m-1]$ such that $f_x(a+i)=y_i$ for each $0\le i<m$.

For $a,b\in \mathbb{N}$, let $[a,b]=\{x\in \mathbb{N}\mid a\le x\le b\}$. Two occurrences $f_x\upharpoonright [a,b]$, $f_x\upharpoonright [c,d]$ are disjoint if $[a,b]\cap [c,d]=\mathrm{\varnothing }$.

If moreover $[a,b+1]\cap [c,d]=\mathrm{\varnothing }$ then the occurrences are strongly disjoint.

A subword that occurs at least twice in a word $w$ is a repeated subword of $w$. Let $k\in \mathbb{N}$, $k\ge 1$. A word $x=x_0\dots x_{n-1}$, $x_i\in \mathrm{\Sigma }$, is $k$-rainbow if it has no repeated subword of length $k$: there are no $0\le i<j<n-k$ with $x\upharpoonright [i,i+k-1]=x\upharpoonright [j,j+k-1]$. A 1-rainbow word is also known simply as rainbow.