research
∙
07/14/2023
Random Wheeler Automata
Wheeler automata were introduced in 2017 as a tool to generalize existin...
share
research
∙
06/09/2023
Space-time Trade-offs for the LCP Array of Wheeler DFAs
Recently, Conte et al. generalized the longest-common prefix (LCP) array...
research
∙
05/09/2023
Sorting Finite Automata via Partition Refinement
Wheeler nondeterministic finite automata (WNFAs) were introduced as a ge...
research
∙
05/05/2023
Verifiable Learning for Robust Tree Ensembles
Verifying the robustness of machine learning models against evasion atta...
research
∙
04/21/2023
Faster Prefix-Sorting Algorithms for Deterministic Finite Automata
Sorting is a fundamental algorithmic pre-processing technique which ofte...
research
∙
01/13/2023
Computing matching statistics on Wheeler DFAs
Matching statistics were introduced to solve the approximate string matc...
research
∙
01/02/2023
Algorithms for Massive Data – Lecture Notes
These are the lecture notes for the course CM0622 - Algorithms for Massi...
research
∙
08/09/2022
Co-lexicographically ordering automata and regular languages. Part I
In the present work, we lay out a new theory showing that all automata c...
research
∙
11/03/2021
Linear-time Minimization of Wheeler DFAs
Wheeler DFAs (WDFAs) are a sub-class of finite-state automata which is p...
research
∙
11/03/2021
HOLZ: High-Order Entropy Encoding of Lempel-Ziv Factor Distances
We propose a new representation of the offsets of the Lempel-Ziv (LZ) fa...
research
∙
06/04/2021
On (co-lex) Ordering Automata
The states of a deterministic finite automaton A can be identified with ...
research
∙
02/12/2021
Which Regular Languages can be Efficiently Indexed?
In the present work, we study the hierarchy of p-sortable languages: reg...
research
∙
11/19/2020
Subpath Queries on Compressed Graphs: a Survey
Text indexing is a classical algorithmic problem that has been studied f...
research
∙
11/13/2020
Substring Query Complexity of String Reconstruction
Suppose an oracle knows a string S that is unknown to us and we want to ...
research
∙
08/19/2020
Novel Results on the Number of Runs of the Burrows-Wheeler-Transform
The Burrows-Wheeler-Transform (BWT), a reversible string transformation,...
research
∙
07/15/2020
On Indexing and Compressing Finite Automata
An index for a finite automaton is a powerful data structure that suppor...
research
∙
04/02/2020
On Locating Paths in Compressed Cardinal Trees
A compressed index is a data structure representing a text within compre...
research
∙
12/26/2019
On the Reproducibility of Experiments of Indexing Repetitive Document Collections
This work introduces a companion reproducible paper with the aim of allo...
research
∙
10/04/2019
Towards a Definitive Measure of Repetitiveness
Unlike in statistical compression, where Shannon's entropy is a definiti...
research
∙
08/12/2019
Space-Efficient Construction of Compressed Suffix Trees
We show how to build several data structures of central importance to st...
research
∙
02/04/2019
On Prefix-Sorting Finite Automata
Being able to efficiently test the membership of a word in a formal lang...
research
∙
01/16/2019
Space-Efficient Computation of the LCP Array from the Burrows-Wheeler Transform
We show that the Longest Common Prefix Array of a text collection of tot...
research
∙
11/30/2018
Faster Attractor-Based Indexes
String attractors are a novel combinatorial object encompassing most kno...
research
∙
11/03/2018
Optimal Rank and Select Queries on Dictionary-Compressed Text
Let γ be the size of a string attractor for a string S of length n over ...
research
∙
09/08/2018
Fully-Functional Suffix Trees and Optimal Text Searching in BWT-runs Bounded Space
Indexing highly repetitive texts --- such as genomic databases, software...
research
∙
05/04/2018
Detecting Mutations by eBWT
In this paper we develop a theory describing how the extended Burrows-Wh...
research
∙
03/26/2018
Universal Compressed Text Indexing
The rise of repetitive datasets has lately generated a lot of interest i...
research
∙
03/26/2018
On the Approximation Ratio of Greedy Parsings
Shannon's entropy is a clear lower bound for statistical compression. Th...
research
∙
03/05/2018
Optimal Substring-Equality Queries with Applications to Sparse Text Indexing
We consider the problem of encoding a string of length n from an alphabe...
research
∙
03/05/2018
String Attractors: Verification and Optimization
String attractors [STOC 2018] are combinatorial objects recently introdu...
research
∙
02/28/2018
Fast Lempel-Ziv Decompression in Linear Space
We consider the problem of decompressing the Lempel-Ziv 77 representatio...
research
∙
11/20/2017
A Separation Between Run-Length SLPs and LZ77
In this paper we give an infinite family of strings for which the length...
research
∙
10/30/2017