6 citations · 12 across the 10 of their papers we have counts for
Showing 2014Show all
3 papers · 1 filter
cs.LO2014★ 2 cited
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…
cs.CC2014★ 2 cited
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.…
cs.CC2014
Model Counting for Formulas of Bounded Clique-Width
Friedrich Slivovsky, Stefan Szeider
We show that #SAT is polynomial-time tractable for classes of CNF formulas whose incidence graphs have bounded symmetric clique-width (or bounded clique-width, or bounded rank-widt…