Metraipolis › archive › dc_345ec814156f

Smallest String Attractors and Minimal Coverage Certificates of Thue--Morse Words — arXiv:2610.10950

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.10950
License (as archived)
CC0-1.0
Archived
2026-10-09T06:28:59.553Z
SHA-256 of the archived text
f2359c9d820904781955ee2eb50afeb9e1b9b3a7e194013459dc7e40f164938b
Stable URL of this page
https://metraipolis.com/documento/dc_345ec814156f

How to cite

Smallest String Attractors and Minimal Coverage Certificates of Thue--Morse Words — arXiv:2610.10950 — arXiv (en), https://arxiv.org/abs/2610.10950 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_345ec814156f (Metraipolis archive dc_345ec814156f, sha256 f2359c9d820904781955ee2eb50afeb9e1b9b3a7e194013459dc7e40f164938b)
BibTeX
@misc{dc345ec814156f,
  title = {Smallest String Attractors and Minimal Coverage Certificates of Thue--Morse Words — arXiv:2610.10950},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.10950},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_345ec814156f; sha256 f2359c9d820904781955ee2eb50afeb9e1b9b3a7e194013459dc7e40f164938b},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.10950. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

String attractors provide a compact way of representing the complete factor structure of a word: a set of positions is an attractor if every distinct factor has at least one occurrence crossing one of the selected positions. Although the minimum attractor size is known for several classical families of words, describing \emph{all} optimal attractors is typically much more difficult, since it requires understanding the geometry of all factor occurrences rather than constructing a single optimal solution. We give a complete description for the finite Thue--Morse words. Earlier work proved that four positions are necessary and sufficient for every order $n\geq 4$, but the collection of all smallest attractors remained unknown. For every $n\geq 6$, writing $h=2^{n-3}$, we prove that the smallest attractors are exactly the two reflected families where the four offsets are chosen independently from $\{0,1\}$. Hence there are exactly $32$ smallest attractors for every $n\geq6$. The initial cases are genuinely exceptional: $t_5$ has $40$ smallest attractors and $t_4$ has $87$. We also study the attractor condition independently of optimality. For every $n\geq5$, we characterize the complete antichain of inclusion-minimal factor coverages of $t_n$. It consists precisely of the coverages of $aa$, $bb$, and the eight minimal unique substrings of every generation $t_m$, $4\leq m\leq n$. Thus there are exactly $8n-22$ canonical constraints, forming an irredundant exact certificate for attractors of arbitrary cardinality. When attention is restricted to four-position sets, this linear-size system collapses to a constant one: it is enough to test the $24$ minimal unique substrings coming from three consecutive generations, and sixteen of these already force the two optimal families. We also show that three generations are necessary within this natural consecutive-generation hierarchy.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Combinatorics (math.CO) ; Data Structures and Algorithms (cs.DS); Formal Languages and Automata Theory (cs.FL).
Pagina del lavoro: https://arxiv.org/abs/2610.10950 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-09T05:53:57.114Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).