5 papers
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…
On the Enumeration Complexity of Unions of Conjunctive Queries
Nofar Carmeli, Markus Kröll
We study the enumeration complexity of Unions of Conjunctive Queries(UCQs). We aim to identify the UCQs that are tractable in the sense that the answer tuples can be enumerated wit…
Enumeration Complexity of Conjunctive Queries with Functional Dependencies
Nofar Carmeli, Markus Kröll
We study the complexity of enumerating the answers of Conjunctive Queries (CQs) in the presence of Functional Dependencies (FDs). Our focus is on the ability to list output tuples…
A Complexity Theory for Hard Enumeration Problems
Nadia Creignou, Markus Kröll, Reinhard Pichler +2
Complexity theory provides a wealth of complexity classes for analyzing the complexity of decision and counting problems. Despite the practical relevance of enumeration problems, t…
Efficiently Enumerating Minimal Triangulations
Nofar Carmeli, Batya Kenig, Benny Kimelfeld +1
We present an algorithm that enumerates all the minimal triangulations of a graph in incremental polynomial time. Consequently, we get an algorithm for enumerating all the proper t…