14 citations · 26 across the 14 of their papers we have counts for
19 papers
Lexicographic Direct Access with Functional Dependencies
Florent Capelli, Nofar Carmeli, Stefan Mengel
We study the complexity of lexicographic direct access to join query answers over databases that satisfy functional dependencies (FDs). More precisely, we give fine-grained lower a…
A canonical generalization of OBDD
Florent Capelli, YooJung Choi, Stefan Mengel +2
We introduce Tree Decision Diagrams (TDD) as a model for Boolean functions that generalizes OBDD. They can be seen as a restriction of structured d-DNNF; that is, d-DNNF that respe…
Dynamic direct access of MSO query evaluation over strings
Pierre Bourhis, Florent Capelli, Stefan Mengel +1
We study the problem of evaluating a Monadic Second Order (MSO) query over strings under updates in the setting of direct access. We present an algorithm that, given an MSO query w…
Ranked Enumeration for MSO on Trees via Knowledge Compilation
Antoine Amarilli, Pierre Bourhis, Florent Capelli +1
We study the problem of enumerating the satisfying assignments for circuit classes from knowledge compilation, where assignments are ranked in a specific order. In particular, we s…
Linear Programs with Conjunctive Database Queries
Florent Capelli, Nicolas Crosetti, Joachim Niehren +1
In this paper, we study the problem of optimizing a linear program whose variables are the answers to a conjunctive query. For this we propose the language LP(CQ) for specifying li…
From Amortized to Worst Case Delay in Enumeration Algorithms
Florent Capelli, Yann Strozecki
The quality of enumeration algorithms is often measured by their delay, that is, the maximal time spent between the output of two distinct solutions. If the goal is to enumerate $t…