String Representation in Suffixient Set Size Space
This solves a foundational problem in string repetitiveness measures, impacting compressed representations and indexing data structures in computer science.
The paper tackled the open problem of whether every string admits a string representation of size O(χ(w)) words, where χ is the size of the smallest suffixient set, and answered it affirmatively by presenting the first such representation scheme based on a new substring equation system (SES) model.
Repetitiveness measures quantify how much repetitive structure a string contains and serve as parameters for compressed representations and indexing data structures. We study the measure $Ï$, defined as the size of the smallest suffixient set. Although $Ï$ has been studied extensively, its reachability, whether every string $w$ admits a string representation of size $O(Ï(w))$ words, has remained an important open problem. We answer this question affirmatively by presenting the first such representation scheme. Our construction is based on a new model, the substring equation system (SES), and we show that every string admits an SES of size $O(Ï(w))$.