2026-09-05T07:01:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25959 2026-06-23T13:12:47Z ddc:004 open_access

The Smallest String Attractors of Fibonacci and Period-Doubling Words Banbara, Mutsunori Bannai, Hideo Guo, Peaker Köppl, Dominik Mieno, Takuya Okamoto, Yoshio String attractors Fibonacci words Period-doubling words Combinatorics on words 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]∩ Γ 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^{⌈n/2⌉ - 2} distinct position pairs that are the smallest string attractors of the nth Fibonacci word for n ≥ 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 nth period-doubling word for n ≥ 2. Our results show that strings with the same smallest attractor size can have a drastically different number of distinct smallest attractors. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mutsunori Banbara and Hideo Bannai and Peaker Guo and Dominik Köppl and Takuya Mieno and Yoshio Okamoto 2026 Is Part Of LIPIcs, Volume 369, 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2026.33 urn:nbn:de:0030-drops-259599 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2026.33 eng https://creativecommons.org/licenses/by/4.0/legalcode