A string attractor of a string T1. . |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 = Ti. . 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.
Banbara et al. (Thu,) studied this question.