TY - GEN
T1 - Edit and Alphabet-Ordering Sensitivity of Lex-Parse
AU - Nakashima, Yuto
AU - Köppl, Dominik
AU - Funakoshi, Mitsuru
AU - Inenaga, Shunsuke
AU - Bannai, Hideo
N1 - Publisher Copyright:
© Yuto Nakashima, Dominik Köppl, Mitsuru Funakoshi, Shunsuke Inenaga, and Hideo Bannai.
PY - 2024/8
Y1 - 2024/8
N2 - We investigate the compression sensitivity [Akagi et al., 2023] of lex-parse [Navarro et al., 2021] for two operations: (1) single character edit and (2) modification of the alphabet ordering, and give tight upper and lower bounds for both operations (i.e., we show Θ(log n) bounds for strings of length n). For both lower bounds, we use the family of Fibonacci words. For the bounds on edit operations, our analysis makes heavy use of properties of the Lyndon factorization of Fibonacci words to characterize the structure of lex-parse.
AB - We investigate the compression sensitivity [Akagi et al., 2023] of lex-parse [Navarro et al., 2021] for two operations: (1) single character edit and (2) modification of the alphabet ordering, and give tight upper and lower bounds for both operations (i.e., we show Θ(log n) bounds for strings of length n). For both lower bounds, we use the family of Fibonacci words. For the bounds on edit operations, our analysis makes heavy use of properties of the Lyndon factorization of Fibonacci words to characterize the structure of lex-parse.
KW - Compression sensitivity
KW - Fibonacci words
KW - Lex-parse
UR - http://www.scopus.com/inward/record.url?scp=85203331355&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85203331355&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.MFCS.2024.75
DO - 10.4230/LIPIcs.MFCS.2024.75
M3 - Conference contribution
AN - SCOPUS:85203331355
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 49th International Symposium on Mathematical Foundations of Computer Science, MFCS 2024
A2 - Kralovic, Rastislav
A2 - Kucera, Antonin
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 49th International Symposium on Mathematical Foundations of Computer Science, MFCS 2024
Y2 - 26 August 2024 through 30 August 2024
ER -