Automatic complexity of Fibonacci and Tribonacci words

Abstract

For a complexity function $C$, the lower and upper $C$-complexity rates of an infinite word $\mathbf{x}$ are \[ \underline{C}(\mathbf x)=\liminf_{n\to\infty} \frac{C(\mathbf{x}\upharpoonright n)}n,\quad \overline{C}(\mathbf x)=\limsup_{n\to\infty} \frac{C(\mathbf{x}\upharpoonright n)}n \] respectively. Here $\mathbf{x}\upharpoonright n$ is the prefix of $x$ of length $n$. We consider the case $C={\mathrm{A}}_{\mathrm{N}}$, the nondeterministic automatic complexity. If these rates are strictly between 0 and $1/2$, we call them intermediate. Our main result is that words having intermediate ${\mathrm{A}}_{\mathrm{N}}$-rates exist, viz. the infinite Fibonacci and Tribonacci words.

Discrete Applied Mathematics, to appear