The Smallest String Attractors of Fibonacci, Period-Doubling, and Thue--Morse Words
A string attractor of a string $T[1..|T|]$ is a set of positions $Γ$ of $T$ such that any nonempty 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 and period-doubling words of length at least $2$ is known to be $2$. The size of the smallest string attractor of Thue--Morse words of length at least $25$ is known to be $4$. We completely characterize the set of all smallest string attractors of…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2602.16152
curl -X POST /api/v1/records/arxiv/2602.16152/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2602.16152/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'