## The Size of a Revised Knowledge Base

**Marco Cadoli, Francesco M. Donini, Paolo Liberatore, and
Marco Schaerf**
*Proceedings of the Fourteenth ACM SIGACT SIGMOD SIGART
Symposium on Principles of Database Systems (PODS'95)*

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 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 expressed with a formula admitting a
polynomial-space representation (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.

@inproceedings{cado-etal-95,
title = {The Size of a Revised Knowledge Base},
year = {1995},
author = {Cadoli, Marco and Donini, Francesco M. and Liberatore,
Paolo and Schaerf, Marco},
booktitle = {Proceedings of the Fourteenth ACM SIGACT SIGMOD
SIGART Symposium on Principles of Database Systems (PODS'95)},
pages = {151--162},
publisher = {ACM Press and Addison Wesley},
}

HTTP download.

FTP
download.

doi: 10.1145/212433.220205