143 citations · 363 across the 42 of their papers we have counts for
10 papers · 1 filter
Suffixient Sets
Lore Depuydt, Travis Gagie, Ben Langmead +2
We define a suffixient set for a text to be a set of positions between 1 and such that, for any edge descending from a node to a node in the suffix tree…
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…
Space-time Trade-offs for the LCP Array of Wheeler DFAs
Nicola Cotumaccio, Travis Gagie, Dominik Köppl +1
Recently, Conte et al. generalized the longest-common prefix (LCP) array from strings to Wheeler DFAs, and they showed that it can be used to efficiently determine matching statist…
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…