3 papers
cs.FL2026
Separating Words with Automata in the Half-adversarial Case
Gabriel Bathie
We consider the problem of separating words with deterministic finite automata (DFA) (Goral{č}{í}k and Koubek, 1986). This problem asks: given two distinct words of length at…
cs.DS2026
Analyzing and Leveraging the -Sensitivity of LZ77
Gabriel Bathie, Paul Huber, Guillaume Lagarde +1
We study the sensitivity of the Lempel-Ziv 77 compression algorithm to edits, showing how modifying a string can deteriorate or improve its compression. Our first result is a t…
cs.DS2024
Small Space Encoding and Recognition of -Palindromic Prefixes
Gabriel Bathie, Jonas Ellert, Tatiana Starikovskaya
Palindromes are non-empty strings that read the same forward and backward. The problem of recognizing strings that can be represented as the concatenation of even-length palindrome…