14 citations · 15 across the 4 of their papers we have counts for
10 papers
Characterization and Decidability of FC-Definable Regular Languages
Sam M. Thompson, Nicole Schweikardt, Dominik D. Freydenberger
FC is a first-order logic that reasons over all factors of a finite word using concatenation, and can define non-regular languages like that of all squares (ww). In this paper, we…
FC-Datalog as a Framework for Efficient String Querying
Owen M. Bell, Joel D. Day, Dominik D. Freydenberger
Core spanners are a class of document spanners that capture the core functionality of IBM's AQL. FC is a logic on strings built around word equations that when extended with constr…
Generalized Core Spanner Inexpressibility via Ehrenfeucht-Fraïssé Games for FC
Sam M. Thompson, Dominik D. Freydenberger
Despite considerable research on document spanners, little is known about the expressive power of generalized core spanners. In this paper, we use Ehrenfeucht-Fraïssé games to obta…
Splitting Spanner Atoms: A Tool for Acyclic Core Spanners
Dominik D. Freydenberger, Sam M. Thompson
This paper investigates regex CQs with string equalities (SERCQs), a subclass of core spanners. As shown by Freydenberger, Kimelfeld, and Peterfreund (PODS 2018), these queries are…
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…
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…
Testing k-binomial equivalence
Dominik D. Freydenberger, Pawel Gawrychowski, Juhani Karhumäki +2
Two words and are said to be -binomial equivalent if every non-empty word of length at most over the alphabet of and appears as a scattered facto…