Compositional Belief Update
  In this paper we explore a class of belief update operators, in which 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 sentences
structure, and that may be reasonably implemented. In addressing update, we
first provide a definition phrased in terms of the models of a knowledge base.
While this 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 restricting the
syntactic form of the sentence for update, we also obtain a hierarchy of update
operators with Winsletts standard semantics as the most basic interesting
approach captured. We subsequently give an algorithm which captures this
approach; in the general case the algorithm is exponential, but with some
not-unreasonable assumptions we obtain an algorithm that is linear in the size
of the knowledge base. Hence the resulting approach has much better complexity
characteristics than other operators in some situations. We also explore other
compositional belief change operators: erasure is developed as a dual operator
to update; we show that a forget operator is definable in terms of update; and
we give a definition of the compositional revision operator. We obtain that
compositional revision, under the most natural definition, yields the Satoh
revision operator.
