Showing cs.FLShow all
3 papers · 1 filter
cs.FL2025
Universally Wheeler Languages
Ruben Becker, Giuseppa Castiglione, Giovanna D'Agostino +4
The notion of Wheeler languages is rooted in the Burrows-Wheeler transform (BWT), one of the most central concepts in data compression and indexing. The BWT has been generalized to…
cs.FL2024
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…
cs.FL2024
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…