4 citations · 16 across the 9 of their papers we have counts for
8 papers · 1 filter
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…
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…
Generic Expression Hardness Results for Primitive Positive Formula Comparison
Simone Bova, Hubie Chen, Matthew Valeriote
We study the expression complexity of two basic problems involving the comparison of primitive positive formulas: equivalence and containment. In particular, we study the complexit…
k-Hyperarc Consistency for Soft Constraints over Divisible Residuated Lattices
Simone Bova
We investigate the applicability of divisible residuated lattices (DRLs) as a general evaluation framework for soft constraint satisfaction problems (soft CSPs). DRLs are in fact n…
Proof Search in Hajek's Basic Logic
S. Bova, F. Montagna
We introduce a proof system for Hajek's logic BL based on a relational hypersequents framework. We prove that the rules of our logical calculus, called RHBL, are sound and invertib…