The Compactness of Belief Revision and Update Operators

Paolo Liberatore and Marco Schaerf

Fundamenta Informaticae

A propositional knowledge base can be seen as a compact representation of a set of models. When a knowledge base T is updated with a formula P, the resulting set of models can be represented in two ways: either by a theory T' that is equivalent to T*P or by the pair (T,P). The second representation can be super-polinomially more compact than the first. In this paper, we prove that the compactness of this representation depends on the specific semantics of *, e.g., Winslett's semantics is more compact than Ginsberg's.

 title = {The Compactness of Belief Revision and Update
 year = {2004},
 author = {Liberatore, Paolo and Schaerf, Marco},
 journal = {Fundamenta Informaticae},
 pages = {377--393},
 number = {3--4},
 volume = {62},