Preference-based belief revision for rule-based agents (Q1024129)

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 required that both ground literals are in \(K\), in order to ensure that the relation is over \(K\). (2) The authors' consequence relation \(Cn\) is defined in such a way that when applied to a set of literals it is the identity operation; it becomes ampliative only when the argument set also contains a rule so that generalized modus ponens can be applied. This is why postulate (K-6) is vacuously true: when \(Cn(A) = Cn(B)\) then \(A = Cn(A) = Cn(B) = B\) and so \(f(K,A) = f(K,B)\) for any two-place function, e.g. contraction. It would be interesting to explore a variant on the authors' constructions in which the consequence operation \(Cn\) is rendered rather more powerful (and arguably more natural) without combinatorial explosion: take \(Cn(A)\) to be the closure of \({A}\) under generalized modus ponens using whatever rules are available in \(K\). This makes sense in the authors' principal context, where it is supposed that the agent's rules are not open to revision. Done alone, it would lead to the failure of postulate (K-6), but that could be remedied by using a suitable choice function in the definition of contraction.