State Complexity of Shifts of the Fibonacci Word
This work addresses a theoretical problem in combinatorics on words, specifically for researchers studying automata and state complexity, and is incremental as it builds on known results about the Fibonacci word.
The paper tackles the problem of determining the state complexity of automata generating shifted sequences of the Fibonacci infinite word, showing it is O(log c) for both msd-first and lsd-first input, which is close to the information-theoretic minimum for aperiodic sequences.
The Fibonacci infinite word ${\bf f} = (f_i)_{i \geq 0} = 01001010\cdots$ is one of the most celebrated objects in combinatorics on words. There is a simple $5$-state automaton that, given $i$ in lsd-first Zeckendorf representation, computes its $i$'th term $f_i$, and a $2$-state automaton for msd-first. In this paper we consider the state complexity of the automaton generating the shifted sequence $(f_{i+c})_{i \geq 0}$, and show that it is $O(\log c)$ for both msd-first and lsd-first input. This is close to the information-theoretic minimum for an aperiodic sequence. The techniques involve a mixture of state complexity techniques and Diophantine approximation.