Tight Additive Sensitivity on LZ-style Compressors and String Attractors

The worst-case additive sensitivity of a string repetitiveness measure $c$ is defined to be the largest difference between $c(w)$ and $c(w^{\mathrm{\prime }})$, where $w$ is a string of length $n$ and $w^{\mathrm{\prime }}$ is a string that can be obtained by performing a single-character edit operation on $w$. We present $O(\sqrt{n})$ upper bounds for the worst-case additive sensitivity of the smallest string attractor size $\gamma$ and the smallest bidirectional scheme size $b$, which match the known lower bounds $\mathrm{\Omega }(\sqrt{n})$ for $\gamma$ and $b$ [Akagi et al. 2023]. Further, we present matching upper and lower bounds for the worst-case additive sensitivity of the Lempel-Ziv family - $\mathrm{\Theta }(n^{\frac{2}{3}})$ for LZSS and LZ-End, and $\mathrm{\Theta }(n)$ for LZ78.