Powiadomienia systemowe
- Sesja wygasła!
- Sesja wygasła!
- Sesja wygasła!
Tytuł artykułu
Autorzy
Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
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
Wydawca
Czasopismo
Rocznik
Tom
Strony
377--393
Opis fizyczny
Bibliogr. 21 poz., rys.
Twórcy
autor
- Dipartimento di Informatica e Sistemistica, Università di Roma "La Sapienza", Via Salaria 113 - Roma, Italy
autor
- 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.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BUS2-0005-0086