The Smallest String Attractors of Fibonacci and Period-Doubling Words
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_ | 1866910025607282688 |
|---|---|
| author | Banbara, Mutsunori Bannai, Hideo Guo, Peaker Köppl, Dominik Mieno, Takuya Okamoto, Yoshio |
| author_facet | Banbara, Mutsunori Bannai, Hideo Guo, Peaker Köppl, Dominik Mieno, Takuya Okamoto, Yoshio |
| contents | A string attractor of a string $T[1..|T|]$ is a set of positions $Γ$ of $T$ such that any substring $w$ of $T$ has an occurrence that crosses a position in $Γ$, i.e., there is a position $i$ such that $w = T[i..i+|w|-1]$ and the intersection $[i,i+|w|-1]\cap Γ$ is nonempty. The size of the smallest string attractor of Fibonacci words is known to be $2$. We completely characterize the set of all smallest string attractors of Fibonacci words, and show a recursive formula describing the $2^{n-4} + 2^{\lceil n/2 \rceil - 2}$ distinct position pairs that are the smallest string attractors of the $n$th Fibonacci word for $n \geq 7$. Similarly, the size of the smallest string attractor of period-doubling words is known to be $2$. We also completely characterize the set of all smallest string attractors of period-doubling words, and show a formula describing the two distinct position pairs that are the smallest string attractors of the $n$th period-doubling word for $n\geq 2$. Our results show that strings with the same smallest attractor size can have a drastically different number of distinct smallest attractors. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_16152 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The Smallest String Attractors of Fibonacci and Period-Doubling Words Banbara, Mutsunori Bannai, Hideo Guo, Peaker Köppl, Dominik Mieno, Takuya Okamoto, Yoshio Combinatorics Discrete Mathematics Formal Languages and Automata Theory A string attractor of a string $T[1..|T|]$ is a set of positions $Γ$ of $T$ such that any substring $w$ of $T$ has an occurrence that crosses a position in $Γ$, i.e., there is a position $i$ such that $w = T[i..i+|w|-1]$ and the intersection $[i,i+|w|-1]\cap Γ$ is nonempty. The size of the smallest string attractor of Fibonacci words is known to be $2$. We completely characterize the set of all smallest string attractors of Fibonacci words, and show a recursive formula describing the $2^{n-4} + 2^{\lceil n/2 \rceil - 2}$ distinct position pairs that are the smallest string attractors of the $n$th Fibonacci word for $n \geq 7$. Similarly, the size of the smallest string attractor of period-doubling words is known to be $2$. We also completely characterize the set of all smallest string attractors of period-doubling words, and show a formula describing the two distinct position pairs that are the smallest string attractors of the $n$th period-doubling word for $n\geq 2$. Our results show that strings with the same smallest attractor size can have a drastically different number of distinct smallest attractors. |
| title | The Smallest String Attractors of Fibonacci and Period-Doubling Words |
| topic | Combinatorics Discrete Mathematics Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2602.16152 |