## The size of a revised knowledge base

**Marco Cadoli, Francesco M. Donini, Paolo Liberatore, and
Marco Schaerf**
*Artificial Intelligence*

In this paper we address a specific computational aspect of
belief revision: the size of the propositional formula obtained
by means of the revision of a formula with a new one. In
particular, we focus on the size of the smallest formula which is
logically equivalent to the revised knowledge base. The main
result of this paper is that not all formalizations of belief
revision are equal from this point of view. For some of them we
show that the revised knowledge base can be represented by a
polynomial-size formula (we call these results ''compactability''
results). On the other hand, for other ones the revised
knowledge base does not always admit a polynomial-space
representation, unless the polynomial hierarchy collapses at a
sufficiently low level (''non-compactability'' results). We also
show that the time complexity of query answering for the revised
knowledge base has definitely an impact on being able to
represent the result of the revision compactly. Nevertheless,
formalisms with the same complexity may have different
compactability properties. We also study compactability
properties for a weaker form of equivalence, called query
equivalence, which allows to introduce new propositional symbols.
Moreover, we extend our analysis to the special case in which the
new formula has constant size and to the case of sequences of
revisions (i.e., iterated belief revision). A complete analysis
along these four coordinates is shown.

@article{cado-etal-99-d,
title = {The size of a revised knowledge base},
year = {1999},
author = {Cadoli, Marco and Donini, Francesco M. and Liberatore,
Paolo and Schaerf, Marco},
journal = {Artificial Intelligence},
pages = {25--64},
number = {1},
volume = {115},
}

HTTP download.

doi: 10.1016/S0004-3702(99)00074-0