Propositional belief base update and minimal change

In this paper we examine ten concrete propositional update operations of th e literature. We start by completely characterizing their relative strength and their computational complexity. Then we evaluate the competing update operations with respect to the postulates proposed by Katsuno and Mendelzon , It turns out that the majority violates most of the postulates. We argue that all violated postulates are undesirable except one. After that we eval uate the update operations with respect to another property which has been investigated extensively in the literature, viz. that disjunctive updates s hould not be identified with the exclusive disjunction. We argue that this is desirable, and show that the argument gives further support to the rejec tion of two of the postulates. Finally we study how the different approache s accommodate general laws governing the world, alias integrity constraints . Summing up our results, we conclude that only two of the update operation s are satisfactory. (C) 1999 Elsevier Science B.V. All rights reserved.