ECAI 2004 Conference Paper

[full paper]

A Syntactical Approach to Revision

Guilherme Bittencourt, Laurent Perrussel, Jerusa Marchi

The aim of this article is to revisit Dalal's operator for belief revision. Dalal has proposed a technique for revising belief bases based on the minimization of a distance between interpretations. The result is a concrete operator that can be considered either from a semantical point of view (distance between interpretations) or from a syntactical point of view (number of atoms that have their truth values changed). Dalal has shown that the so-called Alchourrón, Gärdenfors and Makinson (AGM) postulates are satisfied by its operator. The AGM postulates constrain the revision process so that minimal changes occur in the belief set. In this article, our contribution is twofold: first, we improve Dalal's algorithm by avoiding multiple satisfiability checking, each one of which is a NP-complete task. Our algorithm requires only one NP-stage if beliefs are expressed in a specific syntax, namely the prime implicates and prime implicants. Second, we propose a new distance based on the number of prime implicates contradicted by the incoming new information. We argue that in some cases changing a minimal set of propositional symbols do not necessarily entail minimal changes.

Keywords: Belief Revision

Citation: Guilherme Bittencourt, Laurent Perrussel, Jerusa Marchi: A Syntactical Approach to Revision. In R.López de Mántaras and L.Saitta (eds.): ECAI2004, Proceedings of the 16th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2004, pp.788-792.