6 papers
On Computing Minimum Wheeler DFA From Their Language
Ruben Becker, Davide Cenzato, Nicola Prezza +1
Wheeler automata have recently emerged as a powerful generalization of the Burrows-Wheeler Transform, enabling optimal linear-time pattern matching on compressed labeled graphs --…
Testing Suffixient Sets
Davide Cenzato, Francisco Olivares, Nicola Prezza
Suffixient sets are a novel prefix array (PA) compression technique based on subsampling PA (rather than compressing the entire array like previous techniques used to do): by stori…
Compressing Suffix Trees by Path Decompositions
Ruben Becker, Davide Cenzato, Travis Gagie +4
The suffix tree is arguably the most fundamental data structure on strings: introduced by Weiner (SWAT 1973) and McCreight (JACM 1976), it allows solving a myriad of computational…
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 ,…
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…
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…