## 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.

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