7 papers
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…
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…
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…
Longest Common Extensions with Wildcards: Trade-off and Applications
Gabriel Bathie, Itai Boneh, Panagiotis Charalampopoulos +2
We study the Longest Common Extension (LCE) problem in a string containing wildcards. Wildcards (also called "don't cares" or "holes") are special characters that match any other c…
Internal Pattern Matching in Small Space and Applications
Gabriel Bathie, Panagiotis Charalampopoulos, Tatiana Starikovskaya
In this work, we consider pattern matching variants in small space, that is, in the read-only setting, where we want to bound the space usage on top of storing the strings. Our mai…
Pattern Matching with Mismatches and Wildcards
Gabriel Bathie, Panagiotis Charalampopoulos, Tatiana Starikovskaya
In this work, we address the problem of approximate pattern matching with wildcards. Given a pattern of length containing wildcards, a text of length , and an in…
Small-Space Algorithms for the Online Language Distance Problem for Palindromes and Squares
Gabriel Bathie, Tomasz Kociumaka, Tatiana Starikovskaya
We study the online variant of the language distance problem for two classical formal languages, the language of palindromes and the language of squares, and for the two most funda…