Preference-based belief revision for rule-based agents
type: Item
instance of: scholarly article
title: Preference-based belief revision for rule-based agents
zbMATH Open document ID: 1170.03006
author: Natasha Alechina
author: Mark Jago
author: Brian Logan
published in: Synthese
publication date: 2009-06-16T00:00:00Z
review text: Belief change operations tend to have high computational complexity due to repeated consistency checks. As noted by Nebel in 1992, one way to try to get around this is by restricting the language and/or its logic, so that consistency checks become unnecessary or trivial. Adapting an idea of McAllester in 1980 for truth-maintenance systems, the authors do both: they restrict the language to consist only of literals (for facts) and rules (for passing from a finite set of literals to a literal) and within this language restrict classical consequence to generalized modus ponens. In this context, they introduce a notion that they call the McAllester contraction of a literal from a set of literals and such rules. This operation can be computed in polynomial time but still satisfies some desirable AGM-style conditions (other than recovery). An associated revision function (not defined by the Levi identity, but rather by contracting contradictions from the expansion) is also polynomial. Representation theorems for both are given. The paper is based on two earlier ones by Alechina et al., published as conference proceedings [\textit{N. Alechina}, \textit{M. Jago} and \textit{B. Logan}, ``Resource-bounded belief revision and contraction'', Lect. Notes Comput. Sci. 3904, 141--154 (2006); \textit{N. Alechina}, \textit{R. H. Bordini}, \textit{J. F. Hübner}, \textit{M. Jago} and \textit{B. Logan}, ``Automating belief revision for AgentSpeak'', Lect. Notes Comput. Sci. 4327, 61--77 (2006)]. There are some connections, but also significant differences, to earlier work of \textit{H. Bezzazi}, \textit{S. Janot}, \textit{S. Konieczny} and \textit{R. Pino Pérez} in [``Analysing rational properties of change operators based on forward chaining'', Lect. Notes Comput. Sci. 1472, 317--339 (1998; Zbl 0928.03014)]. Reviewer's comments: It may help the reader to clarify two points. (1) There is an obvious oversight in the definition of dependence on page 165: in the first clause it should be …
reviewed by: David Makinson
Mathematics Subject Classification ID: 03B42
zbMATH DE Number: 5565227
zbMATH Keywords: belief revision
zbMATH Keywords: reason maintenance systems
zbMATH Keywords: preferences
zbMATH Keywords: rule-based agents
zbMATH Keywords: belief contraction
zbMATH Keywords: complexity
MaRDI profile type: Publication
full work available at URL: s11229-008-9364-0
OpenAlex ID: W1990982254
cites work: On the logic of theory change: Partial meet contraction and revision functions
cites work: On the logic of theory change: safe contraction
cites work: Q4247260
cites work: Approximate belief revision
cites work: The complexity of nested counterfactuals and iterated knowledge base revisions
cites work: Q3495345
cites work: Belief contraction without recovery
cites work: Theory contraction and base contraction unified
cites work: Kernel contraction
cites work: Semi-revision
cites work: Propositional knowledge base revision and minimal change
cites work: Q3862380
cites work: On the status of the postulate of recovery in the logic of theory change
cites work: Q3493313
cites work: Q4944922
cites work: Theory-Contraction is NP-Complete
cites work: New foundations for a relational theory of theory-revision
DOI: 10.1007/S11229-008-9364-0
description: scientific article; zbMATH DE number 5565227