2025/06/05 by Hiroto Fujimaru, Fujimaru, Hiroto, Gonzalo Navarro +5
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Algorithms and Data Compression #Genome Rearrangement Algorithms #Machine Learning and Algorithms #cs.DS #cs.FL #math.CO
paper · pdf · doi:10.48550/arxiv.2506.05638
openalex publication_date 2025/06/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
A suffixient set is a novel combinatorial object that captures the essential information of repetitive strings in a way that, provided with a random access mechanism, supports various forms of pattern matching. In this paper, we study the size χ of the smallest suffixient set as a repetitiveness measure. First, we study its sensitivity to various string operations. We show that χ cannot increase by more than 2 after appending or prepending a character to the string. As a consequence, we are able to give simple linear-time online algorithms to compute smallest suffixient sets. We also show that, although reversing the string can increase χ by an arbitrary O(n) value, it always holds χ(T)/χ(TR)≤ 2. We also prove lower and upper bounds for the additive or multiplicative increase of χ after applying arbitrary edit operations, or rotating the text. In particular, we show that the additive increase can be as large as Ω(√(n)) for all those operations. Secondly, we place χ among known repetitiveness measures. In particular, we show χ≤ 2r (where r is the number of runs in the Burrows-Wheeler Transform of the string), that there are string families where χ=o(v) (where v is the size of the smallest lexicographic parse of the string), and that χ is uncomparable to almost all reachable measures based on copy-paste mechanisms. In passing, we give precise bounds for χ for some relevant string families, for example χ≤ σ+2 on episturmian words over alphabets of size σ (e.g., χ≤ 4 on Fibonacci strings, for which we precisely characterize the only two smallest suffixient sets).