1 citations · 2 across the 6 of their papers we have counts for
10 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 --…
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…
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…
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 ,…
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…
Sketching and Streaming for Dictionary Compression
Ruben Becker, Matteo Canton, Davide Cenzato +3
We initiate the study of sub-linear sketching and streaming techniques for estimating the output size of common dictionary compressors such as Lempel-Ziv '77, the run-length Burrow…
Random Wheeler Automata
Ruben Becker, Davide Cenzato, Sung-Hwan Kim +3
Wheeler automata were introduced in 2017 as a tool to generalize existing indexing and compression techniques based on the Burrows-Wheeler transform. Intuitively, an automaton is s…
Optimal Wheeler Language Recognition
Ruben Becker, Davide Cenzato, Sung-Hwan Kim +3
A Wheeler automaton is a finite state automaton whose states admit a total Wheeler order, reflecting the co-lexicographic order of the strings labeling source-to-node paths. A Whee…
Sorting Finite Automata via Partition Refinement
Ruben Becker, Manuel Cáceres, Davide Cenzato +4
Wheeler nondeterministic finite automata (WNFAs) were introduced as a generalization of prefix sorting from strings to labeled graphs. WNFAs admit optimal solutions to classic hard…