4 citations · 16 across the 9 of their papers we have counts for
10 papers
Circuit Treewidth, Sentential Decision, and Query Compilation
Simone Bova, Stefan Szeider
The evaluation of a query over a probabilistic database boils down to computing the probability of a suitable Boolean function, the lineage of the query over the database. The meth…
SDDs are Exponentially More Succinct than OBDDs
Simone Bova
Introduced by Darwiche (2011), sentential decision diagrams (SDDs) are essentially as tractable as ordered binary decision diagrams (OBDDs), but tend to be more succinct in practic…
On Compiling Structured CNFs to OBDDs
Simone Bova, Friedrich Slivovsky
We present new results on the size of OBDD representations of structurally characterized classes of CNF formulas. First, we identify a natural sufficient condition, which we call t…
A Strongly Exponential Separation of DNNFs from CNF Formulas
Simone Bova, Florent Capelli, Stefan Mengel +1
Decomposable Negation Normal Forms (DNNFs) are Boolean circuits in negation normal form where the subcircuits leading into each AND gate are defined on disjoint sets of variables.…
Quantified Conjunctive Queries on Partially Ordered Sets
Simone Bova, Robert Ganian, Stefan Szeider
We study the computational problem of checking whether a quantified conjunctive query (a first-order sentence built using only conjunction as Boolean connective) is true in a finit…
Model Checking Existential Logic on Partially Ordered Sets
Simone Bova, Robert Ganian, Stefan Szeider
We study the problem of checking whether an existential sentence (that is, a first-order sentence in prefix form built using existential quantifiers and all Boolean connectives) is…