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: 69,959
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

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.
Transmission Failure, AGM Style.Jake Chandler - 2013 - Erkenntnis 78 (2):383-398.


Added to PP index

Total views
3 ( #1,356,858 of 2,504,602 )

Recent downloads (6 months)
1 ( #416,529 of 2,504,602 )

How can I increase my downloads?


My notes