State Complexity of Shifts of the Fibonacci Word

2026/03/19 by Delaram Moradi, Pierre Popoli, Jeffrey Shallit +1 · 1 voice · 1 citation
Computer Science · Mathematics · #cs.DM #cs.FL #math.NT

paper · pdf · doi:10.48550/arxiv.2603.18858

Abstract

The Fibonacci infinite word \bf f = (f_i)_{i ≥ 0} = 01001010⋯ 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 ≥ 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.

Citations

• Complexity of Linear Subsequences of k-Automatic Sequences
• Automatic Theorem Proving in Walnut
• Zeckendorf Representations Using Negative Fibonacci Numbers
• On the base-dependence of sets of numbers recognizable by finite automata

Cited by

• Complexity of Linear Subsequences of Fibonacci-Automatic Sequences

Discussions

• Delaram Moradi, Pierre Popoli, Jeffrey Shallit, Ingrid Vukusic: State Complexity of Shifts of the Fibonacci Word https://arxiv.org/abs/2603.18858 https://arxiv.org/pdf/2603.18858 https://arxiv.org/htm [bsky, 0 points, 0 comments]

Related

• Complexity of Linear Subsequences of Fibonacci-Automatic Sequences
• Improvement Ergodic Theory For The Infinite Word \mathfrakF=\mathfrakF_b:=( _b f_n)_{n \geqslant 0} on Fibonacci Density
• Automatic complexity of Fibonacci and Tribonacci words
• A combinatorial approach for the state complexity of the Shuffle product
• Lower bounds for the state complexity of probabilistic languages and the language of prime numbers