The complexity of belief update

DOI10.1016/S0004-3702(00)00016-3zbMath0947.68560MaRDI QIDQ1575185

Paolo Liberatore

Publication date: 21 August 2000

Published in: Artificial Intelligence (Search for Journal in Brave)

zbMATH Keywords

ComplexityBelief revisionBelief updateClosed world assumption

Mathematics Subject Classification ID

Artificial intelligence for robotics (68T40)

Related Items (6)

Reasoning under minimal upper bounds in propositional logic ⋮ Updating action domain descriptions ⋮ Knowledge updates: Semantics and complexity issues ⋮ Propositional belief base update and minimal change ⋮ The complexity of belief update ⋮ Default reasoning from conditional knowledge bases: Complexity and tractable cases

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of optimization problems
• Circumscription - a form of non-monotonic reasoning
• Propositional knowledge base revision and minimal change
• On the complexity of propositional knowledge base revision, updates, and counterfactuals
• The complexity of belief update
• The size of a revised knowledge base
• Abduction to plausible causes: an event-based model of belief update
• Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
• On the logic of theory change: Partial meet contraction and revision functions

This page was built for publication: The complexity of belief update