35 citations · 113 across the 47 of their papers we have counts for
63 papers
Improved Regular Expression Matching with Simple Backreferences
Philip Bille, Inge Li Gørtz, Rikke Schjeldrup Jessen
A regular expression with backreferences (rewb) specifies a set of strings formed by characters combined with concatenation, union, star operators, and backreferences. A backrefere…
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…
Average-Case Optimal Encodings and Efficient Worst-Case Indices for Element Distinctness Queries
Philip Bille, Johannes Fischer, Inge Li Gørtz +1
We study the data structure version of the \emph{element distinctness problem}: preprocess an array of elements from an alphabet of size to answer \textsc{All-Distinct} que…
Fast and Compact Graph Cuts for the Boykov-Kolmogorov Algorithm
Christian Møller Mikkelstrup, Anders Bjorholm Dahl, Philip Bille +2
Computing a minimum - cut in a graph is a solution to a wide range of computer vision problems, and is often done using the Boykov-Kolmogorov (BK) algorithm. In this paper, w…
Improved Extended Regular Expression Matching
Philip Bille, Inge Li Gørtz, Rikke Schjeldrup Jessen
An extended regular expression specifies a set of strings formed by characters from an alphabet combined with concatenation, union, intersection, complement, and star operators…
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…