ALC + T: a Preferential Extension of Description Logics

• Autorzy: Giordano L. , Gliozzi V. , Olivetti N. , Pozzato G.L.
• Języki publikacji: EN

Abstrakty

EN

We extend the Description Logic ALC with a "typicality" operator T that allows us to reason about the prototypical properties and inheritance with exceptions. The resulting logic is called ALC + T. The typicality operator is intended to select the “most normal” or "most typical" instances of a concept. In our framework, knowledge bases may then contain, in addition to ordinary ABoxes and TBoxes, subsumption relations of the form "T(C) is subsumed by P", expressing that typical C-members have the property P. The semantics of a typicality operator is defined by a set of postulates that are strongly related to Kraus-Lehmann-Magidor axioms of preferential logic P. We first show that T enjoys a simple semantics provided by ordinary structures equipped with a preference relation. This allows us to obtain a modal interpretation of the typicality operator. We show that the satisfiability of an ALC+Tknowledge base is decidable and it is precisely EXPTIME. We then present a tableau calculus for deciding satisfiability of ALC + T knowledge bases. Our calculus gives a (suboptimal) nondeterministic-exponential time decision procedure for ALC + T. We finally discuss how to extend ALC + T in order to infer defeasible properties of (explicit or implicit) individuals. We propose two alternatives: (i) a nonmonotonic completion of a knowledge base; (ii) a "minimal model" semantics for ALC + T whose intuition is that minimal models are those that maximise typical instances of concepts.

Słowa kluczowe

EN

description logics; Prototypical Reasoning; Tableaux Calculi

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 96, nr 3
• Strony: 341--372
• Opis fizyczny: Bibliogr. 23 poz.

Twórcy

autor

Giordano L.

autor

Gliozzi V.

autor

Olivetti N.

autor

Pozzato G.L.

• Dipartimento di Informatica, Universita degli Studi di Torino, c.so Svizzera 185, 10145 Torino, Italy,

Bibliografia

• [1] Baader, F., Calvanese, D., McGuinness, D., Nardi, D., Patel-Schneider, P., Eds.: The Description Logic Handbook - Theory, Implementation, and Applications, 2nd edition, Cambridge, 2007.
• [2] Baader, F., Hollunder, B.: Embedding Defaults into Terminological Knowledge Representation Formalisms, J. Autom. Reasoning, 14(1), 1995, 149-180.
• [3] Baader, F., Hollunder, B.: Priorities on Defaults with Prerequisites, and Their Application in Treating Specificity in Terminological Default Logic, J. of Automated Reasoning (JAR), 15(1), 1995, 41-68.
• [4] Bonatti, P. A., Lutz, C., Wolter, F.: Description Logics with Circumscription., Proc. of KR, 2006.
• [5] Brewka, G.: Adding Priorities and Specificity to Default Logic, Proceedings of the European Workshop on Logics in Artificial Intelligence (C. MacNish, D. Pearce, L. Moniz Pereira, Eds.), 838, Springer, Verlag, 1994.
• [6] Brewka, G., Junker, U.: Handling partially ordered defaults in TMS, Proceedings of the 1st European Conference on Symbolic and Quantitative Approaches for Uncertainty, ECSQARU, Marseille, France, 548, Springer, 1991.
• [7] Buchheit,M., Donini, F.M., Schaerf, A.: Decidable Reasoning in Terminological Knowledge Representation Systems, J. Artif. Int. Research (JAIR), 1, 1993, 109-138.
• [8] Donini, F.M., Lenzerini,M., Nardi, D., Nutt,W., Schaerf, A.: An Epistemic Operator for Description Logics, Artif. Intell., 100(1-2), 1998, 225-274.
• [9] Donini, F. M., Nardi, D., Rosati, R.: Autoepistemic Description Logics, Proceedings of IJCAI (1), 1997.
• [10] Donini, F. M., Nardi, D., Rosati, R.: Description logics of minimal knowledge and negation as failure, ACM Trans. Comput. Log., 3(2), 2002, 177-225.
• [11] Eiter, T., Lukasiewicz, T., Schindlauer, R., Tompits, H.: Combining Answer Set Programming with Description Logics for the Semantic Web, KR 2004, 141-151.
• [12] Giordano, L., Gliozzi, V., Olivetti, N., Pozzato, G. L.: Reasoning About Typicality in Preferential Description Logics, Proceedings of JELIA 2008. LNCS(LNAI), vol. 5293, pp. 192-205 (S. Hólldobler, C. Lutz, H. Wansing, Eds.), Springer, Heidelberg.
• [13] Giordano, L., Gliozzi, V., Olivetti, N., Pozzato, G. L.: Preferential Description Logics, Proceedings of LPAR 2007. LNCS(LNAI), vol. 4790, pp. 257-272, 2007.
• [14] Giordano, L., Gliozzi, V., Olivetti, N., Pozzato, G. L.: Analytic Tableaux Calculi for KLM Logics of Nonmonotonic Reasoning, ACM Transactions on Computational Logics (TOCL), 10(3), 2009.
• [15] Giordano, L., Gliozzi, V., Olivetti, N., Pozzato, G. L.: On Extending Description Logics for Reasoning About Typicality: a First Step, TR Dip. di Informatica, http://www.di.unito.it/∼pozzato/tr09.pdf, 2009.
• [16] Giugno, R., Lukasiewicz, T.: P-SHOQ(D): A Probabilistic Extension of SHOQ(D) for Probabilistic Ontologies in the SemanticWeb, Proceedings of JELIA 2002. LNCS(LNAI), vol. 2424, pp. 86-97, 2002.
• [17] Ke, P., Sattler, U.: Next Steps for Description Logics of Minimal Knowledge and Negation as Failure, Proceedings of DL2008, 2008.
• [18] Kraus, S., Lehmann, D., Magidor,M.: Nonmonotonic Reasoning, Preferential Models and Cumulative Logics, Artificial Intelligence, 44(1-2), 1990, 167-207.
• [19] Lehmann, D., Magidor, M.: What does a conditional knowledge base entail?, Artificial Intelligence, 55(1), 1992, 1-60.
• [20] Lifschitz, V.: Nonmonotonic Databases and Epistemic Queries, Proceedings of IJCAI, 1991.
• [21] Lifschitz, V.: Minimal Belief and Negation as Failure, Artificial Intelligence, 70(1-2), 1994, 53-72.
• [22] Papadimitriou, C. H.: Computational Complexity, Addison-Wesley Publishing Company, 1994.
• [23] Straccia, U.: Default Inheritance Reasoning in Hybrid KL-ONE-Style Logics, Proc. of IJCAI, 1993.