35 citations · 99 across the 47 of their papers we have counts for
5 papers · 1 filter
Subsequence Automata with Default Transitions
Philip Bille, Inge Li Gørtz, Frederik Rye Skjoldjensen
Let be a string of length with characters from an alphabet of size . The \emph{subsequence automaton} of (often called the \emph{directed acyclic subsequence graph})…
Distance labeling schemes for trees
Stephen Alstrup, Inge Li Gørtz, Esben Bistrup Halvorsen +1
We consider distance labeling schemes for trees: given a tree with nodes, label the nodes with binary strings such that, given the labels of any two nodes, one can determine, b…
Finger Search in Grammar-Compressed Strings
Philip Bille, Anders Roy Christiansen, Patrick Hagge Cording +1
Grammar-based compression, where one replaces a long string by a small context-free grammar that generates the string, is a simple and powerful paradigm that captures many popular…
Longest Common Extensions in Sublinear Space
Philip Bille, Inge Li Gørtz, Mathias Bæk Tejs Knudsen +2
The longest common extension problem (LCE problem) is to construct a data structure for an input string of length that supports LCE queries. Such a query returns the…
Dynamic Relative Compression, Dynamic Partial Sums, and Substring Concatenation
Philip Bille, Patrick Hagge Cording, Inge Li Gørtz +3
Given a static reference string and a source string , a relative compression of with respect to is an encoding of as a sequence of references to substrings of $R…