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},
}