1 citations · 1 across the 1 of their papers we have counts for
4 papers
Dynamic Complexity of Document Spanners
Dominik D. Freydenberger, Sam M. Thompson
The present paper investigates the dynamic complexity of document spanners, a formal framework for information extraction introduced by Fagin, Kimelfeld, Reiss, and Vansummeren (JA…
Complexity Bounds for Relational Algebra over Document Spanners
Liat Peterfreund, Dominik D. Freydenberger, Benny Kimelfeld +1
We investigate the complexity of evaluating queries in Relational Algebra (RA) over the relations extracted by regex formulas (i.e., regular expressions with capture variables) ove…
Deterministic Regular Expressions With Back-References
Dominik D. Freydenberger, Markus L. Schmid
Most modern libraries for regular expression matching allow back-references (i.e., repetition operators) that substantially increase expressive power, but also lead to intractabili…
Joining Extractions of Regular Expressions
Dominik D. Freydenberger, Benny Kimelfeld, Liat Peterfreund
Regular expressions with capture variables, also known as "regex formulas," extract relations of spans (interval positions) from text. These relations can be further manipulated vi…