research
∙
06/22/2023
Faster Compression of Deterministic Finite Automata
Deterministic finite automata (DFA) are a classic tool for high throughp...
share
research
∙
01/23/2023
Sliding Window String Indexing in Streams
Given a string S over an alphabet Σ, the 'string indexing problem' is to...
research
∙
11/30/2022
Gapped String Indexing in Subquadratic Space and Sublinear Query Time
In Gapped String Indexing, the goal is to compactly represent a string S...
research
∙
08/24/2022
Hierarchical Relative Lempel-Ziv Compression
Relative Lempel-Ziv (RLZ) parsing is a dictionary compression method in ...
research
∙
06/21/2022
The Complexity of the Co-Occurrence Problem
Let S be a string of length n over an alphabet Σ and let Q be a subset o...
research
∙
01/27/2022
Predecessor on the Ultra-Wide Word RAM
We consider the predecessor problem on the ultra-wide word RAM model of ...
research
∙
08/19/2021
A Conditional Lower Bound for Episode Matching
Given two strings S and P, the Episode Matching problem is to compute th...
research
∙
02/04/2021
Gapped Indexing for Consecutive Occurrences
The classic string indexing problem is to preprocess a string S into a c...
research
∙
07/08/2020
String Indexing for Top-k Close Consecutive Occurrences
The classic string indexing problem is to preprocess a string S into a c...
research
∙
06/28/2020
Random Access in Persistent Strings
We consider compact representations of collections of similar strings th...
research
∙
11/08/2019
Space Efficient Construction of Lyndon Arrays in Linear Time
We present the first linear time algorithm to construct the 2n-bit versi...
research
∙
09/26/2019
String Indexing with Compressed Patterns
Given a string S of length n, the classic string indexing problem is to ...
research
∙
08/27/2019
Partial Sums on the Ultra-Wide Word RAM
We consider the classic partial sums problem on the ultra-wide word RAM ...
research
∙
07/10/2019
Sparse Regular Expression Matching
We present the first algorithm for regular expression matching that can ...
research
∙
02/06/2019
Top Tree Compression of Tries
We present a compressed representation of tries based on top tree compre...
research
∙
01/19/2019
Approximation Algorithms for the A Priori TravelingRepairman
We consider the a priori traveling repairman problem, which is a stochas...
research
∙
01/03/2019
Mergeable Dictionaries With Shifts
We revisit the mergeable dictionaries with shift problem, where the goal...
research
∙
06/08/2018
Compressed Communication Complexity of Longest Common Prefixes
We consider the communication complexity of fundamental longest common p...
research
∙
04/09/2018
From Regular Expression Matching to Parsing
Given a regular expression R and a string Q the regular expression match...
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
∙
11/01/2017