2025/06/28 by Yuto Fujie, Hiroki Shibata, Fujie, Yuto +5
Computer Science · #Algorithms and Data Compression #semigroups and automata theory #Cryptography and Data Security
paper · pdf · doi:10.48550/arxiv.2506.22778
The worst-case additive sensitivity of a string repetitiveness measure c is defined to be the largest difference between c(w) and c(w'), where w is a string of length n and w' is a string that can be obtained by performing a single-character edit operation on w. We present O(√(n)) upper bounds for the worst-case additive sensitivity of the smallest string attractor size γ and the smallest bidirectional scheme size b, which match the known lower bounds Ω(√(n)) for γ 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 - Θ(n(2)/(3)) for LZSS and LZ-End, and Θ(n) for LZ78.