Graduate studies at Western
Synthese 165 (2):159-177 (2008)
|Abstract||Agents which perform inferences on the basis of unreliable information need an ability to revise their beliefs if they discover an inconsistency. Such a belief revision algorithm ideally should be rational, should respect any preference ordering over the agent’s beliefs (removing less preferred beliefs where possible) and should be fast. However, while standard approaches to rational belief revision for classical reasoners allow preferences to be taken into account, they typically have quite high complexity. In this paper, we consider belief revision for agents which reason in a simpler logic than full first-order logic, namely rule-based reasoners. We show that it is possible to define a contraction operation for rule-based reasoners, which we call McAllester contraction, which satisfies all the basic Alchourrón, Gärdenfors and Makinson (AGM) postulates for contraction (apart from the recovery postulate) and at the same time can be computed in polynomial time. We prove a representation theorem for McAllester contraction with respect to the basic AGM postulates (minus recovery), and two additional postulates. We then show that our contraction operation removes a set of beliefs which is least preferred, with respect to a natural interpretation of preference. Finally, we show how McAllester contraction can be used to define a revision operation which is also polynomial time, and prove a representation theorem for the revision operation.|
|Keywords||Belief revision Reason maintenance systems Preferences Rule-based agents|
|Categories||categorize this paper)|
|Through your library||Configure|
Similar books and articles
John Cantwell (2005). A Formal Model of Multi-Agent Belief-Interaction. Journal of Logic, Language and Information 14 (4):397-422.
Jake Chandler (2013). Transmission Failure, AGM-Style. Erkenntnis 78 (2):383-398.
Renata Wassermann (1999). Resource Bounded Belief Revision. Erkenntnis 50 (2-3):429-446.
Hans Van Ditmarsch & Willem Labuschagne (2007). My Beliefs About Your Beliefs: A Case Study in Theory of Mind and Epistemic Logic. Synthese 155 (2):191 - 209.
Hans van Ditmarsch & Willem Labuschagne (2007). My Beliefs About Your Beliefs: A Case Study in Theory of Mind and Epistemic Logic. Synthese 155 (2):191-209.
Abhaya C. Nayak (1994). Foundational Belief Change. Journal of Philosophical Logic 23 (5):495 - 533.
Adnan Darwiche & Judea Pearl (1997). On the Logic of Iterated Belief Revision. Artificial Intelligence 89:1-29.
Neil Tennant (2006). New Foundations for a Relational Theory of Theory-Revision. Journal of Philosophical Logic 35 (5):489 - 528.
Mark Jago (2006). Resource-Bounded Belief Revision and Contraction. In P. Torroni, U. Endriss, M. Baldoni & A. Omicini (eds.), Declarative Agent Languages and Technologies III. Springer.
Added to index2009-01-28
Total downloads22 ( #62,830 of 740,565 )
Recent downloads (6 months)2 ( #37,453 of 740,565 )
How can I increase my downloads?