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