Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-25T05:19:40.127Z Has data issue: false hasContentIssue false

Towards closed world reasoning in dynamic open worlds

Published online by Cambridge University Press:  09 July 2010

MARTIN SLOTA
Affiliation:
CENTRIA and Departamento de Informática, Universidade Nova de Lisboa, 2829-516 Caparica, Portugal
JOÃO LEITE
Affiliation:
CENTRIA and Departamento de Informática, Universidade Nova de Lisboa, 2829-516 Caparica, Portugal

Abstract

The need for integration of ontologies with nonmonotonic rules has been gaining importance in a number of areas, such as the Semantic Web. A number of researchers addressed this problem by proposing a unified semantics for hybrid knowledge bases composed of both an ontology (expressed in a fragment of first-order logic) and nonmonotonic rules. These semantics have matured over the years, but only provide solutions for the static case when knowledge does not need to evolve.

In this paper we take a first step towards addressing the dynamics of hybrid knowledge bases. We focus on knowledge updates and, considering the state of the art of belief update, ontology update and rule update, we show that current solutions are only partial and difficult to combine. Then we extend the existing work on ABox updates with rules, provide a semantics for such evolving hybrid knowledge bases and study its basic properties.

To the best of our knowledge, this is the first time that an update operator is proposed for hybrid knowledge bases.

Type
Regular Papers
Copyright
Copyright © Cambridge University Press 2010

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Alchourrón, C. E., Gärdenfors, P., and Makinson, D. 1985. On the logic of theory change: Partial meet contraction and revision functions. Journal of Symbolic Logic 50, 2, 510530.CrossRefGoogle Scholar
Alferes, J. J., Banti, F., Brogi, A., and Leite, J. A. 2005. The refined extension principle for semantics of dynamic logic programming. Studia Logica 79, 1, 732.Google Scholar
Alferes, J. J., Knorr, M., and Swift, T. 2009. Queries to hybrid MKNF knowledge bases through oracular tabling. In Proceedings of the 8th International Semantic Web Conference (ISWC 2009). 1–16.Google Scholar
Alferes, J. J., Leite, J. A., Pereira, L. M., Przymusinska, H., and Przymusinski, T. C. 2000. Dynamic updates of non-monotonic knowledge bases. The Journal of Logic Programming 45, 1–3 (September/October), 4370.Google Scholar
Baader, F., Calvanese, D., McGuinness, D. L., Nardi, D., and Patel-Schneider, P. F., Eds. 2003. The Description Logic Handbook: Theory, Implementation, and Applications. Cambridge University Press.Google Scholar
Berners-Lee, T., Hendler, J., and Lassila, O. 2001. The semantic web. Scientific American 284, 5, 2837.Google Scholar
Dalal, M. 1988. Investigations into a theory of knowledge base revision. In Proceedings of the 7th National Conference on Artificial Intelligence (AAAI 1988). AAAI Press / The MIT Press, St. Paul, MN, 475479.Google Scholar
Delgrande, J. P., Schaub, T., Tompits, H., and Woltran, S. 2008. Belief revision of logic programs under answer set semantics. In Proceedings of the 11th International Conference on Principles of Knowledge Representation and Reasoning (KR 2008), Brewka, G. and Lang, J., Eds. AAAI Press, Sydney, 411421.Google Scholar
Dix, J. 1995. A classification theory of semantics of normal logic programs: I. Strong properties. Fundamenta Informaticae 22, 3, 227255.CrossRefGoogle Scholar
Eiter, T., Fink, M., Sabbatini, G., and Tompits, H. 2002. On properties of update sequences based on causal rejection. Theory and Practice of Logic Programming (TPLP) 2, 6, 721777.Google Scholar
Eiter, T. and Wang, K. 2008. Semantic forgetting in answer set programming. Artificial Intelligence 172, 14, 16441672.CrossRefGoogle Scholar
Flouris, G., Makanatas, D., Kondylakis, H., Plexousakis, D., and Antoniou, G. 2008. Ontology change: Classification and survey. The Knowledge Engineering Review 23, 2, 117152.Google Scholar
Gelder, A. V., Ross, K. A., and Schlipf, J. S. 1991. The well-founded semantics for general logic programs. Journal of the ACM 38, 3, 620650.Google Scholar
Gelfond, M. and Lifschitz, V. 1988. The stable model semantics for logic programming. In Proceedings of the 5th International Conference and Symposium on Logic Programming (ICLP/SLP 1988), Kowalski, R. A. and Bowen, K. A., Eds. MIT Press, Seattle, Washington, 10701080.Google Scholar
Giacomo, G. D., Lenzerini, M., Poggi, A., and Rosati, R. 2007. On the approximation of instance level update and erasure in description logics. In Proceedings of the 22nd AAAI Conference on Artificial Intelligence (AAAI 2007). AAAI Press, Vancouver, BC, Canada, 403408.Google Scholar
Herzig, A. 2005. On updates with integrity constraints. In Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics, Delgrande, J. P., Lang, J., Rott, H., and Tallon, J.-M., Eds. Dagstuhl Seminar Proceedings, vol. 05321. Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, Germany.Google Scholar
Herzig, A. and Rifi, O. 1999. Propositional belief base update and minimal change. Artificial Intelligence 115, 1, 107138.Google Scholar
Hitzler, P. and Parsia, B. 2009. Ontologies and rules. In Handbook on Ontologies, 2nd ed., Staab, S. and Studer, R., Eds. International Handbooks on Information Systems. Springer, Berlin, 111132.Google Scholar
Katsuno, H. and Mendelzon, A. O. 1991. On the difference between updating a knowledge base and revising it. In Proceedings of the 2nd International Conference on Principles of Knowledge Representation and Reasoning (KR'91), Allen, J. F., Fikes, R., and Sandewall, E., Eds. Morgan Kaufmann, Cambridge, MA, 387394.Google Scholar
Leite, J. A. 2003. Evolving Knowledge Bases. Frontiers of Artificial Intelligence and Applications, xviii + 307 p. Hardcover, vol. 81. IOS Press.Google Scholar
Leite, J. A. and Pereira, L. M. 1997. Generalizing updates: From models to programs. In Proceedings of the 3rd International Workshop on Logic Programming and Knowledge Representation (LPKR '97), Dix, J., Pereira, L. M., and Przymusinski, T. C., Eds. Lecture Notes in Computer Science, vol. 1471. Springer, New York, 224246.Google Scholar
Lifschitz, V. 1991. Nonmonotonic databases and epistemic queries. In Proceedings of the 12th International Joint Conference on Artificial Intelligence (IJCAI91). Morgan Kaufmann, 381386.Google Scholar
Lifschitz, V., Pearce, D., and Valverde, A. 2001. Strongly equivalent logic programs. ACM Transactions on Computational Logic (TOCL) 2, 4, 526541.CrossRefGoogle Scholar
Liu, H., Lutz, C., Miličić, M., and Wolter, F. 2006. Updating description logic ABoxes. In Proceedings of the 10th International Conference on Principles of Knowledge Representation and Reasoning (KR'06), Doherty, P., Mylopoulos, J., and Welty, C. A., Eds. AAAI Press, Lake District, UK, 4656.Google Scholar
Makinson, D. 1988. General theory of cumulative inference. In Proceedings of the 2nd International Workshop on Non-Monotonic Reasoning (NMR'88), Michael, R., De Kleer, J., Ginsberg, M. L., and Sandewall, E., Eds. Lecture Notes in Computer Science, vol. 346. Springer, Grassau, FRG, 118.Google Scholar
Marek, V. W. and Truszczynski, M. 1998. Revision programming. Theoretical Computer Science 190, 2, 241277.Google Scholar
Motik, B. and Rosati, R. 2007. A faithful integration of description logics with logic programming. In Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI-07), Veloso, M. M., Ed. Hyderabad, India, 477482.Google Scholar
Sakama, C. and Inoue, K. 2003. An abductive framework for computing knowledge base updates. Theory and Practice of Logic Programming (TPLP) 3, 6, 671713.Google Scholar
Slota, M. and Leite, J. 2010. On semantic update operators for answer-set programs. In Proceedings of the 19th European Conference on Artificial Intelligence (ECAI 2010). To appear.Google Scholar
Wang, K., Wang, Z., Topor, R. W., Pan, J. Z., and Antoniou, G. 2009. Concept and role forgetting in ontologies. In Proceedings of the 8th International Semantic Web Conference (ISWC 2009), Bernstein, A., Karger, D. R., Heath, T., Feigenbaum, L., Maynard, D., Motta, E., and Thirunarayan, K., Eds. Lecture Notes in Computer Science, vol. 5823. Springer, Chantilly, VA, 666681.Google Scholar
Winslett, M. 1988. Reasoning about action using a possible models approach. In Proceedings of the 7th National Conference on Artificial Intelligence (AAAI 1988). AAAI Press / The MIT Press, Saint Paul, MN, 8993.Google Scholar
Winslett, M. 1990. Updating Logical Databases. Cambridge University Press, New York.Google Scholar
Zhang, Y. and Foo, N. Y. 2005. A unified framework for representing logic program updates. In Proceedings of the 20th National Conference on Artificial Intelligence (AAAI 2005), Veloso, M. M. and Kambhampati, S., Eds. AAAI Press / The MIT Press, Pittsburgh, PA, 707713.Google Scholar