Showing 2026Show all
2 papers · 1 filter
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
The k-bit Sensitivity of LZ77
Gabriel Bathie, Paul Huber, Guillaume Lagarde +1
In this paper, we study the sensitivity of the Lempel--Ziv 77 (LZ77) algorithm under multiple substitutions. Akagi, Funakoshi and Inenaga [JIC, 2023] showed that when applying a si…