1 citations · 1 across the 6 of their papers we have counts for
5 papers · 1 filter
On the Complexity of Computing the Co-lexicographic Width of a Regular Language
Ruben Becker, Davide Cenzato, Sung-Hwan Kim +4
Co-lex partial orders were recently introduced in (Cotumaccio et al., SODA 2021 and JACM 2023) as a powerful tool to index finite state automata, with applications to regular expre…
Suffixient Arrays: a New Efficient Suffix Array Compression Technique
Davide Cenzato, Lore Depuydt, Travis Gagie +4
The Suffix Array is a classic text index enabling on-line pattern matching queries via simple binary search. The main drawback of the Suffix Array is that it takes linear space in…
Indexing Finite-State Automata Using Forward-Stable Partitions
Ruben Becker, Sung-Hwan Kim, Nicola Prezza +1
An index on a finite-state automaton is a data structure able to locate specific patterns on the automaton's paths and consequently on the regular language accepted by the automato…
Algorithms for Galois Words: Detection, Factorization, and Rotation
Diptarama Hendrian, Dominik Köppl, Ryo Yoshinaka +1
Lyndon words are extensively studied in combinatorics on words -- they play a crucial role on upper bounding the number of runs a word can have [Bannai+, SIAM J. Comput.'17]. We ca…
Computing the LCP Array of a Labeled Graph
Jarno Alanko, Davide Cenzato, Nicola Cotumaccio +3
The LCP array is an important tool in stringology, allowing to speed up pattern matching algorithms and enabling compact representations of the suffix tree. Recently, Conte et al.…