14 citations · 15 across the 4 of their papers we have counts for
3 papers · 1 filter
The theory of concatenation over finite models
Dominik D. Freydenberger, Liat Peterfreund
We propose FC, a new logic on words that combines finite model theory with the theory of concatenation - a first-order logic that is based on word equations. Like the theory of con…
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…