Answers are grounded in this paper and cite their sources.
We address in this paper the problem of counting the models of a propositional theory under incremental changes to its literals. Specifcally, we show that if a propositional theory Δ is in a special form that we call smooth, deterministic, decomposable negation normal form (sd-DNNF), then for any consistent set of literals S, we can simultaneously count (in time linear in the size of Δ) the models of Δ ∪ S and the models of every theory Δ ∪ T where T results from adding, removing or flipping a literal in S. We present two results relating to the time and space complexity of compiling propositional theories into sd-DNNF. First, we show that if a conjunctive normal form (CNF) has a bounded treewidth, then it can be compiled into an sd-DNNF in time and space which are linear in its size. Second, we show that sd-DNNF is a strictly more space efficient representation than Free Binary Decision Diagrams (FBDDs). Finally, we discuss some applications of the counting results to truth maintenance systems, belief revision, and model-based diagnosis.
No takes yet. Share an insight, caveat, or question.
Adnan Darwiche (2001) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: