The Compactness of Belief Revision and Update Operators

• Autorzy: Liberatore P. , Schaerf M.
• Języki publikacji: EN

Abstrakty

EN

A propositional knowledge base can be seen as a compact representation of a set of models. When a knowledge base T is updated with a formula P, the resulting set of models can be represented in two ways: either by a theory T' that is equivalent to T*P or by the pair ‹T,P›. The second representation can be super-polinomially more compact than the first. In this paper, we prove that the compactness of this representation depends on the specific semantics of *, , Winslett's semantics is more compact than Ginsberg's.

Słowa kluczowe

EN

compact representation; belief change; belief revision

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2004
• Tom: Vol. 62, nr 3,4
• Strony: 377--393
• Opis fizyczny: Bibliogr. 21 poz., rys.

Twórcy

autor

Liberatore P.

• Dipartimento di Informatica e Sistemistica, Università di Roma "La Sapienza", Via Salaria 113 - Roma, Italy

autor

Schaerf M.

• Dipartimento di Informatica e Sistemistica, Università di Roma "La Sapienza", Via Salaria 113 - Roma, Italy

Bibliografia

• [1] Borgida, A.: Language Features for Flexible Handling of Exceptions in Information Systems, ACM Transactions on Database Systems, 10, 1985, 563-603.
• [2] Cadoli, M., Donini, F. M., Liberatore, R, Schaerf, M.: The size of a revised knowledge base. Artificial Intelligence, 115(1), 1999,25-64.
• [3] Cadoli, M., Donini, F. M., Liberatore, P., Schaerf, M.: Space Efficiency of Propositional Knowledge Representation Formalisms, Journal of Artificial Intelligence Research, 13,2000, 1-31.
• [4] Cadoli, M., Donini, F. M., Liberatore, P., Schaerf, M.: Preprocessing of intractable problems. Information and Computation, 176(2), 2002, 89-120.
• [5] Dalai, M.: Investigations into a Theory of Knowledge Base Revision: Preliminary Report, Proceedings of the Seventh National Conference on Artificial Intelligence (AAAl'88), 1988.
• [6] Eiter, T., Gottlob, G.: On the Complexity of Propositional Knowledge Base Revision, Updates and Counterfactuals. Artificial Intelligence, 57, 1992, 227-270.
• [7] Fagin, R., Ullman, J. D., Vardi, M. Y.: On the Semantics of Updates in Databases, Proceedings of the Second ACM SIGACTSIGMOD Symposium on Principles of Database Systems (PODS'83), 1983.
• [8] Forbus, K. D.: Introducing Actions into Qualitative Simulation, Proceedings of the Eleventh International Joint Conference on Artificial Intelligence (IJCAI'89), 1989.
• [9] Ginsberg, M. L.: Conterfactuals, Artificial Intelligence, 30, 1986, 35-79.
• [10] Johnson, D. S.: A Catalog of Complexity Classes, in: Handbook of Theoretical Computer Science (J. van Leeuwen, Ed.), vol. A, chapter 2, Elsevier Science Publishers (North-Holland), Amsterdam, 1990, 67-161.
• [11] Katsuno, H., Mendelzon, A. O.: On the Difference between Updating a Knowledge Base and Revising It, Proceedings of the Second International Conference on the Principles of Knowledge Representation and Reasoning (KR'91), 1991.
• [12] Levesque, H. J.: Making believers out of computers, Artificial Intelligence, 30, 1986,81-108.
• [13] Liberatore, P.: Monotonic Reductions, Representative Equivalence, and Compilation of Intractable Problems, Journal of the ACM, 48(6), 2001, 1091-1125.
• [14] Liberatore, P., Schaerf, M.: Reducing Belief Revision to Circumscription (and vice versa). Artificial Intelligence, 93(1-2), 1997, 261-296.
• [15] Liberatore, P., Schaerf, M.: Belief Revision and Update: Complexity of Model Checking, Journal of Computer and System Sciences, 62, 2001, 43-72.
• [16] Nebel, B.: Belief Revision and Default Reasoning: Syntax-Based Approaches, Proceedings of the Second International Conference on the Principles of Knowledge Representation and Reasoning (KR'91), 1991.
• [17] Nebel, B.: How Hard is it to Revise a Belief Base?, in: Belief Change - Handbook of Defeasible Reasoning and Uncertainty Management Systems, Vol. 3 (D. Dubois, H. Prade, Eds.), Kluwer Academic, 1998.
• [18] Satoh, K.: Nonmonotonic Reasoning by Minimal Belief Revision, Proceedings of the International Conference on Fifth Generation Computer Systems (FGCS'88), 1988.
• [19] Stockmeyer, L. J.: The Polynomial-Time Hierarchy, Theoretical Computer Science, 3, 1976, 1-22.
• [20] Winslett, M.: Sometimes updates are circumscription. Proceedings of the Eleventh International Joint Conference on Artificial Intelligence (IJCAr89), 1989.
• [21] Winslett, M.: Updating Logical Databases, Cambridge University Press, 1990.