Lack of Finite Characterizations for the Distance-based Revision

Jonathan Ben-Naim

Lehmann, Magidor, and Schlechta developed an approach to belief revision based on distances between any two valuations. Suppose we are given such a distance D. This defines an operator |D, called a distance operator, which transforms any two sets of valuations V and W into the set V |D W of all those elements of W that are closest to V. This operator |D defines naturally the revision of K by A as the set of all formulas satisfied in mod(K) |D mod(A) (i.e. the set of all those models of A that are closest to the models of K). This constitutes a distance-based revision operator. Lehmann et al. characterized families of them using a loop condition of arbitrarily big size. An interesting question is to know whether this loop condition can be replaced by a finite one. Extending the results of Schlechta, we will provide elements of negative answer. In fact, we will show that for families of distance operators, there is no normal characterization. Approximatively, a characterization is normal iff it contains only finite and universally quantified conditions. Though they are negative, these results have an interest of their own for they help to understand more clearly the limits of what is possible in this area. In addition, we are quite confident that they can be used to show that for families of distance-based revision operators, there is no either normal characterization. For instance, the families of Lehmann et al. might well be concerned with this, which suggests that their big loop condition cannot be replaced by a finite and universally quantified condition.

Subjects: 15.1 Belief Revision; 5. Common Sense Reasoning

Submitted: Mar 1, 2006

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.