On the Tractable Counting of Theory Models and its Application to Truth Maintenance and Belief Revision

DOI10.3166/jancl.11.11-34zbMath1033.03505MaRDI QIDQ4443390

Adnan Darwiche

Publication date: 11 January 2004

Published in: Journal of Applied Non-Classical Logics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3166/jancl.11.11-34

zbMATH Keywords

belief revision; counting models; knowledge compilation; truth maintenance

Mathematics Subject Classification ID

68T27: Logic in artificial intelligence

03B42: Logics of knowledge and belief (including belief change)

Related Items

Local Diagnosis, Logical representation and fusion of prioritized information based on guaranteed possibility measures: Application to the distance-based merging of classical bases, Compiling propositional weighted bases, On probabilistic inference by weighted model counting, Heuristics for planning with penalties and rewards formulated in logic and computed through circuits

Cites Work

• Graph driven BDDs -- a new data structure for Boolean functions
• A logical notion of conditional independence: properties and applications
• Characterizing diagnoses and systems
• On the complexity of propositional knowledge base revision, updates, and counterfactuals
• Complexity theoretical results on partitioned (nondeterministic) binary decision diagrams
• Simultaneous computation of functions, partial derivatives and estimates of rounding errors —Complexity and practicality—
• Efficient Boolean manipulation with OBDD's can be extended to FBDD's
• Logic Programming and Nonmonotonic Reasoning
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Constant-space reasoning in dynamic Bayesian networks