2026-07-21T01:00:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25943 2026-06-23T13:12:33Z ddc:004 open_access

Sensitivity of Repetitiveness Measures to String Reversal Bannai, Hideo Fujie, Yuto Guo, Peaker Inenaga, Shunsuke Nakashima, Yuto Puglisi, Simon J. Urbina, Cristian String reversal Repetitiveness measures Burrows-Wheeler transform Lempel-Ziv parsing Lexicographic parsings We study the impact that string reversal can have on several repetitiveness measures. First, we exhibit an infinite family of strings where the number, r, of runs in the run-length encoding of the Burrows-Wheeler transform (BWT) can increase additively by Θ(n) when reversing the string. This substantially improves the known Ω(log n) lower-bound for the additive sensitivity of r and it is asymptotically tight. We generalize our result to other variants of the BWT, including the variant with an appended end-of-string symbol and the bijective BWT. We show that an analogous result holds for the size z of the Lempel-Ziv 77 (LZ) parsing of the text, and also for some of its variants, including the non-overlapping LZ parsing, and the LZ-end parsing. Moreover, we describe a family of strings for which the ratio z(w^R)/z(w) approaches 3 from below as |w| → ∞. We also show an asymptotically tight lower-bound of Θ(n) for the additive sensitivity of the size v of the smallest lexicographic parsing to string reversal. Finally, we show that the multiplicative sensitivity of v to reversing the string is Θ(log n), and this lower-bound is also tight. Overall, our results expose the limitations of repetitiveness measures that are widely used in practice, against string reversal - a simple and natural data transformation. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hideo Bannai and Yuto Fujie and Peaker Guo and Shunsuke Inenaga and Yuto Nakashima and Simon J. Puglisi and Cristian Urbina 2026 Is Part Of LIPIcs, Volume 369, 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2026.17 urn:nbn:de:0030-drops-259434 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2026.17 eng https://creativecommons.org/licenses/by/4.0/legalcode