4 papers
Tighter Bounds for Wheeler Determinization
Philip Bille, Inge Li Gørtz, Máximo Pérez-López +1
Given a Wheeler NFA , the Wheeler determinization problem is to construct a Wheeler DFA that accepts the same language as . We use the notat…
Compressed Dictionary Matching on Run-Length Encoded Strings
Philip Bille, Inge Li Gørtz, Simon J. Puglisi +1
Given a set of pattern strings and a text string , the classic dictionary matching problem is to report all occurrences of each pattern in…
Succinct Data Structures for Segments
Philip Bille, Inge Li Gørtz, Simon R. Tarnow
We consider succinct data structures for representing a set of horizontal line segments in the plane given in rank space to support \emph{segment access}, \emph{segment selecti…
Hierarchical Relative Lempel-Ziv Compression
Philip Bille, Inge Li Gørtz, Simon J. Puglisi +1
Relative Lempel-Ziv (RLZ) parsing is a dictionary compression method in which a string is compressed relative to a second string (called the reference) by parsing into…