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.

 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.