Propositional belief base update and minimal change

Herzig, Andreas and Rifi, Omar


In this paper we examine ten concrete propositional update operations of the literature. We start by completely characterizing their relative strength and their computational complexity. Then we evaluate the competing update operations w.r.t. 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 evaluate the update operations w.r.t. another property which has been investigated extensively in the literature, viz. that disjunctive updates should not be identified with the exclusive disjunction. We argue that this is desirable, and show that the argument gives further support to the rejection of two of the postulates. Finally we study how the different approaches accommodate general laws governing the world, alias integrity constraints. Summing up our results, we conclude that only two of the update operations are satisfactory.



PDF of conference publication (ECAI 1998)


        author  = "Herzig, Andreas and Rifi, Omar",
        title   = "Propositional belief base update and minimal change",
	journal = "Artificial Intelligence Journal",
        year    = "1999",
	volume	= "115",
	number  = "1",
	pages	= "107--138",
	month   = dec