3 papers
cs.DS2026
Sensitivity and Size Relationships of the Lempel-Ziv Factorization
Hiroki Shibata, Yuto Fujie
The Lempel-Ziv (LZ) factorization is a fundamental method for compressing repetitive strings. Its multiplicative sensitivity to an operation measures how much that operation can in…
cs.DS2026
Sensitivity of Repetitiveness Measures to String Reversal
Hideo Bannai, Yuto Fujie, Peaker Guo +4
We study the impact that string reversal can have on several repetitiveness measures. First, we exhibit an infinite family of strings where the number, , of runs in the run-leng…
cs.DS2025
Tight Additive Sensitivity on LZ-style Compressors and String Attractors
Yuto Fujie, Hiroki Shibata, Yuto Nakashima +1
The worst-case additive sensitivity of a string repetitiveness measure is defined to be the largest difference between and , where is a string of length a…