State Complexity of Shifts of the Fibonacci Word
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915875373711360 |
|---|---|
| author | Moradi, Delaram Popoli, Pierre Shallit, Jeffrey Vukusic, Ingrid |
| author_facet | Moradi, Delaram Popoli, Pierre Shallit, Jeffrey Vukusic, Ingrid |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_18858 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | State Complexity of Shifts of the Fibonacci Word Moradi, Delaram Popoli, Pierre Shallit, Jeffrey Vukusic, Ingrid Formal Languages and Automata Theory Discrete Mathematics Number Theory 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. |
| title | State Complexity of Shifts of the Fibonacci Word |
| topic | Formal Languages and Automata Theory Discrete Mathematics Number Theory |
| url | https://arxiv.org/abs/2603.18858 |