Syntactic Characterizations of Belief Change Operators

Abstract

We provide syntactic characterizations for a number of propositional model-based belief revision and update operators proposed in the literature, as well as algorithms based on these characterizations. 1 Introduction In this paper, we provide syntactic characterizations and algorithms for a number of belief change operators proposed in the literature. We already characterized Winslett's `possible models approach' (PMA) update operators in [ del Val, 1992b ] , where we explored in depth some of the operators in the PMA family, provided algorithms to compute them and experimentally showed that they could be of practical value for (small) updates of quite large databases. In this paper, we show how other operators can be characterized in a very similar way, and show how to design algorithms for computing the result of applying these operators to disjunctive, negation and conjunctive normal form (DNF, NNF and CNF, respectively) databases, which return a database in the same format. The i...