Paper Info
Title
Preference-based belief revision for rule-based agents
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.
Year
DOI
Venue
2008
10.1007/s11229-008-9364-0
Synthese
Keywords
Field
DocType
Belief revision,Reason maintenance systems,Preferences,Rule-based agents
Rule-based system,Information needs,Representation theorem,Artificial intelligence,Time complexity,Epistemology,Belief revision,Mathematics
Journal
Volume
Issue
ISSN
165
2
0039-7857
Citations 
PageRank 
References 
5
0.44
21
Authors
3
Name
Order
Citations
PageRank
Natasha Alechina136841.63
Mark Jago2738.49
Brian Logan380389.41