State Complexity of Shifts of the Fibonacci Word

Delaram Moradi, Pierre Popoli, Jeffrey Shallit ∗, Ingrid Vukusic · 2026

Read State Complexity of Shifts of the Fibonacci Word by Delaram Moradi, Pierre Popoli, Jeffrey Shallit ∗, Ingrid Vukusic (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-18858.txt.

Description

Moradi, Popoli, Shallit, and Vukusic study automata that read shifted Fibonacci word terms. The Fibonacci word is a classic object in combinatorics on words. A five-state machine computes each term from Zeckendorf digits, least significant first. A two-state machine works most significant first. For a shift by c, the machine size grows like the log of c. That growth nearly matches the least possible for an aperiodic sequence. The proof blends state complexity tools with Diophantine approximation.

Catalog record

CREATORDelaram Moradi, Pierre Popoli, Jeffrey Shallit ∗, Ingrid Vukusic
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE61233
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.18858

Browse the full library · About the Tower of Babel