Considerations on Compositional Update Operators

All Papers

We propose an update operator for modifying a knowledge base. The approach differs from other belief change operators in that the definition of the operator is compositional with respect to the sentence to be added. The goal is to provide an update operator that is intuitive, in that its definition is based on a recursive decomposition of the update sentence's structure, and that may be reasonably implemented. It proves to be the case that the resulting approach has better complexity characteristics than other operators in at least some cases. However, while the operator satisfies a core group of the benchmark Katsuno-Mendelzon update postulates, not all of the postulates are satisfied. Other Katsuno Mendelzon postulates can be obtained by suitably restricting the syntactic form of the sentence for update, as we show. In this fashion we also come up with a hierarchy of update operators with, it turns out, Winslett's standard semantics as the weakest approach captured.