22 citations · 90 across the 29 of their papers we have counts for
34 papers
Bounds on BDD-Based Bucket Elimination
Stefan Mengel
We study BDD-based bucket elimination, an approach to satisfiability testing using variable elimination which has seen several practical implementations in the past. We prove that…
Skyline Operators for Document Spanners
Antoine Amarilli, Benny Kimelfeld, Sébastien Labbé +1
When extracting a relation of spans (intervals) from a text document, a common practice is to filter out tuples of the relation that are deemed dominated by others. The domination…
No Efficient Disjunction or Conjunction of Switch-Lists
Stefan Mengel
It is shown that disjunction of two switch-lists can blow up the representation size exponentially. Since switch-lists can be negated without any increase in size, this shows that…
Tight Fine-Grained Bounds for Direct Access on Join Queries
Karl Bringmann, Nofar Carmeli, Stefan Mengel
We consider the task of lexicographic direct access to query answers. That is, we want to simulate an array containing the answers of a join query sorted in a lexicographic order c…
Lower Bounds on Intermediate Results in Bottom-Up Knowledge Compilation
Alexis de Colnet, Stefan Mengel
Bottom-up knowledge compilation is a paradigm for generating representations of functions by iteratively conjoining constraints using a so-called apply function. When the input is…
A short note on the counting complexity of conjunctive queries
Stefan Mengel
This note closes a minor gap in the literature on the counting complexity of conjunctive queries by showing that queries that are not free-connex do not have a linear time counting…