The Size of a Revised Knowledge Base.

Marco Cadoli, Francesco M. Donini, Paolo Liberatore, Marco Schaerf: The Size of a Revised Knowledge Base. PODS 1995: 151-162

@inproceedings{DBLP:conf/pods/CadoliDLS95,
  author    = {Marco Cadoli and
               Francesco M. Donini and
               Paolo Liberatore and
               Marco Schaerf},
  title     = {The Size of a Revised Knowledge Base},
  booktitle = {Proceedings of the Fourteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 22-25, 1995, San Jose,
               California},
  publisher = {ACM Press},
  year      = {1995},
  isbn      = {0-89791-730-8},
  pages     = {151-162},
  ee        = {http://doi.acm.org/10.1145/212433.220205, db/conf/pods/CadoliDLS95.html},
  crossref  = {DBLP:conf/pods/95},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

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.

Copyright © 1995 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

BibTeX

Printed Edition

Proceedings of the Fourteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 22-25, 1995, San Jose, California. ACM Press 1995, ISBN 0-89791-730-8
Contents BibTeX

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1118 KB]

References

[Bor85]: Alexander Borgida: Language Features for Flexible Handling of Exceptions in Information Systems. ACM Trans. Database Syst. 10(4): 565-603(1985) BibTeX
[Dal88]: Mukesh Dalal: Investigations into a Theory of Knowledge Base Revision. AAAI 1988: 475-479 BibTeX
[EG92]: Thomas Eiter, Georg Gottlob: On the Complexity of Propositional Knowledge Base Revision, Updates, and Counterfactuals. Artif. Intell. 57(2-3): 227-270(1992) BibTeX
[FHV83]: Ronald Fagin, Jeffrey D. Ullman, Moshe Y. Vardi: On the Semantics of Updates in Databases. PODS 1983: 352-365 BibTeX
[For89]: ...
[Gin86]: ...
[Joh90]: ...
[KL80]: Richard M. Karp, Richard J. Lipton: Some Connections between Nonuniform and Uniform Complexity Classes. STOC 1980: 302-309 BibTeX
[KM91]: Hirofumi Katsuno, Alberto O. Mendelzon: On the Difference between Updating a Knowledge Base and Revising It. KR 1991: 387-394 BibTeX
[Neb91]: Bernhard Nebel: Belief Revision and Default Reasoning: Syntax-Based Approaches. KR 1991: 417-428 BibTeX
[Neb94]: ...
[Sat88]: Ken Satoh: Nonmonotonic Reasoning by Minimal Belief Revision. FGCS 1988: 455-462 BibTeX
[Web86]: Andreas Weber: Updating Propositional Formulas. Expert Database Conf. 1986: 487-500 BibTeX
[Win90]: ...
[Yap83]: Chee-Keng Yap: Some Consequences of Non-Uniform Conditions on Uniform Classes. Theor. Comput. Sci. 26: 287-300(1983) BibTeX

Referenced by

Paolo Liberatore: The Complexity of Iterated Belief Revision. ICDT 1997: 276-290

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]