## The Size of a Revised Knowledge Base

**Marco Cadoli, Francesco M. Donini, Paolo Liberatore, and
Marco Schaerf**
*Technical Report, Dipartimento di Informatica e Sistemistica,
Università di Roma ''La Sapienza''*

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 we are able to prove that 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). 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, and for the
special case in which the new formula has constant size.
Moreover we extend our analysis to sequences of revisions (i.e.,
iterated belief revision). A complete analysis along these four
coordinates is shown.

@techreport{cado-etal-96-d,
title = {The Size of a Revised Knowledge Base},
year = {1996},
author = {Cadoli, Marco and Donini, Francesco M. and Liberatore,
Paolo and Schaerf, Marco},
institution = {Dipartimento di Informatica e Sistemistica,
Universit\'a di Roma ''La Sapienza''},
number = {DIS 34-96},
}

HTTP download.

FTP
download.