4 papers
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…
The Trie Measure, Revisited
Jarno N. Alanko, Ruben Becker, Davide Cenzato +4
In this paper, we study the following problem: given subsets of an integer universe , having total cardinality ,…
Encoding Co-Lex Orders of Finite-State Automata in Linear Space
Ruben Becker, Nicola Cotumaccio, Sung-Hwan Kim +2
The Burrows-Wheeler transform (BWT) is a string transformation that enhances string indexing and compressibility. Cotumaccio and Prezza [SODA '21] extended this transformation to n…
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…