4 papers · 1 filter
Linear Time Subsequence and Supersequence Regex Matching
Antoine Amarilli, Bartlomiej Dudek, Florin Manea +2
It is well-known that checking whether a given string matches a given regular expression can be done in quadratic time and that this cannot be improved to…
Revisiting Weighted Information Extraction: A Simpler and Faster Algorithm for Ranked Enumeration
Pawel Gawrychowski, Florin Manea, Markus L. Schmid
Information extraction from textual data, where the query is represented by a finite transducer and the task is to enumerate all results without repetition, and its extension to th…
Subsequences With Generalised Gap Constraints: Upper and Lower Complexity Bounds
Florin Manea, Jonas Richardsen, Markus L. Schmid
For two strings u, v over some alphabet A, we investigate the problem of embedding u into w as a subsequence under the presence of generalised gap constraints. A generalised gap co…
Enumerating m-Length Walks in Directed Graphs with Constant Delay
Duncan Adamson, Pawel Gawrychowski, Florin Manea
In this paper, we provide a novel enumeration algorithm for the set of all walks of a given length within a directed graph. Our algorithm has worst-case constant delay between outp…