{"id":"arxiv/2603.18858","url":"https://arxiv.org/abs/2603.18858","tags":["cs.FL","cs.DM","math.NT"],"score":0,"title":"State Complexity of Shifts of the Fibonacci Word","domain":"cs.FL","source":"arxiv","authors":["Delaram Moradi","Pierre Popoli","Jeffrey Shallit","Ingrid Vukusic"],"reviews":0,"subject":"cs.FL","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-03-19","reactions":{}}