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
| CREATOR | Delaram Moradi, Pierre Popoli, Jeffrey Shallit ∗, Ingrid Vukusic |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 61233 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.18858