35 citations · 99 across the 47 of their papers we have counts for
59 papers · 1 filter
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…
An Optimal Algorithm for Stochastic Vertex Cover
Jan van den Brand, Inge Li Gørtz, Chirag Pabbaraju +5
The goal in the stochastic vertex cover problem is to obtain an approximately minimum vertex cover for a graph that is realized by sampling each edge independently with s…
How many users have been here for a long time? Efficient solutions for counting long aggregated visits
Peyman Afshani, Rezaul Chowdhury, Inge Li Gørtz +3
This paper addresses the Counting Long Aggregated Visits problem, which is defined as follows. We are given users and regions, where each user spends some time visiting som…
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…