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.
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.3166/jancl.11.11-34
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 70,130
Through your library

References found in this work BETA

Handbook of Mathematical Logic.Jon Barwise (ed.) - 1977 - North-Holland.
Characterizing Diagnoses and Systems.Johan de Kleer, Alan K. Mackworth & Raymond Reiter - 1992 - Artificial Intelligence 56 (2-3):197-222.

Add more references

Citations of this work BETA

Algebraic Model Counting.Angelika Kimmig, Guy Van den Broeck & Luc De Raedt - 2017 - Journal of Applied Logic 22:46-62.

Add more citations

Similar books and articles

A Paraconsistent Theory of Belief Revision.Edwin D. Mares - 2002 - Erkenntnis 56 (2):229 - 246.
Distance Semantics for Belief Revision.Daniel Lehmann, Menachem Magidor & Karl Schlechta - 2001 - Journal of Symbolic Logic 66 (1):295-317.
Belief Revision I: The AGM Theory.Franz Huber - 2013 - Philosophy Compass 8 (7):604-612.
Infinitary Belief Revision.Dongmo Zhang & Norman Foo - 2001 - Journal of Philosophical Logic 30 (6):525-570.
Revising Beliefs Towards the Truth.Ilkka Niiniluoto - 2011 - Erkenntnis 75 (2):165-181.


Added to PP index

Total views
16 ( #665,578 of 2,506,442 )

Recent downloads (6 months)
1 ( #416,997 of 2,506,442 )

How can I increase my downloads?


My notes