TOPICS
Search

String Attractor

A string attractor for a finite word is a set of its positions such that every distinct nonempty substring has an occurrence containing at least one of those positions. A smallest string attractor is one with minimum cardinality. For example, any one position is an attractor for the word aaaa.

For the Thue-Morse sequence prefix t_n of length 2^n, Kutsukake et al. (2020) proved that a smallest attractor has four positions for n>=4. Faro et al. (2026) classified these smallest attractors and found 87 for n=4, 40 for n=5, and 32 for every n>=6.

See also

Word

Explore with Wolfram|Alpha

References

Faro, S.; Marino, F. P.; and Pavone, A. "Smallest String Attractors and Minimal Coverage Certificates of Thue-Morse Words." 7 Oct 2026. https://arxiv.org/abs/2610.10950.Kutsukake, K.; Matsumoto, T.; Nakashima, Y.; Inenaga, S.; Bannai, H.; and Takeda, M. "On Repetitiveness Measures of Thue-Morse Words." 12 Aug 2020. https://arxiv.org/abs/2005.09524v3.

Cite this as:

Weisstein, Eric W. "String Attractor." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/StringAttractor.html

Subject classifications