Lack of Finite Characterizations for the Distance-based Revision

Principles of Knowledge Representation and Reasoning: Proceedings of the Tenth International Conference (KR2006)

Volume

Principles of Knowledge Representation and Reasoning: Proceedings of the Tenth International Conference (KR2006)

Contents

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.