14 citations · 26 across the 14 of their papers we have counts for
Showing 2014 · cs.CCShow all
3 papers · 2 filters
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★ 1 cited
Understanding model counting for -acyclic CNF-formulas
Johann Brault-Baron, Florent Capelli, Stefan Mengel
We extend the knowledge about so-called structural restrictions of by giving a polynomial time algorithm for -acyclic . In contrast to previous…
cs.CC2014★ 2 cited
Hypergraph Acyclicity and Propositional Model Counting
Florent Capelli, Arnaud Durand, Stefan Mengel
We show that the propositional model counting problem #SAT for CNF- formulas with hypergraphs that allow a disjoint branches decomposition can be solved in polynomial time. We show…