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, then for any consistent set of literals S, we can simultaneously count 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 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. Finally, we discuss some applications of the counting results to truth maintenance systems, belief revision, and model-based diagnosis. (shrink)

In this paper, the problem of purifying an assumption-based theory KB, i.e., identifying the right extension of KB using knowledge-gathering actions (tests), is addressed. Assumptions are just normal defaults without prerequisite. Each assumption represents all the information conveyed by an agent, and every agent is associated with a (possibly empty) set of tests. Through the execution of tests, the epistemic status of assumptions can change from "plausible" to "certainly true", "certainly false" or "irrelevant", and the KB must be revised so (...) as to incorporate such a change. Because removing all the extensions of an assumption-based theory except one enables both identifying a larger set of plausible pieces of information and renders inference computationally easier, we are specifically interested in finding out sets of tests allowing to purify a KB (whatever their outcomes). We address this problem especially from the point of view of computational complexity. (shrink)