Abstract
In this work, we propose a meaningful extension of description logics for non-monotonic reasoning. We introduce \(\mathcal {ALCH}^{\bullet }\), a logic allowing for the representation of and reasoning about both typical class-membership and typical instances of a relation. We propose a preferential semantics for \(\mathcal {ALCH}^{\bullet }\) in terms of partially-ordered DL interpretations which intuitively captures the notions of typicality we are interested in. We define a tableau-based algorithm for checking \(\mathcal {ALCH}^{\bullet }\) knowledge-base consistency that always terminates and we show that it is sound and complete w.r.t. our preferential semantics. The general framework we here propose can serve as the foundation for further exploration of non-monotonic reasoning in description logics and similarly structured logics.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Baader, F., Calvanese, D., McGuinness, D., Nardi, D., Patel-Schneider, P. (eds.): The Description Logic Handbook: Theory, Implementation and Applications, 2nd edn. Cambridge University Press, Cambridge (2007)
Baader, F., Hollunder, B.: How to prefer more specific defaults in terminological default logic. In: Bajcsy, R. (ed.) Proceedings of the 13th International Joint Conference on Artificial Intelligence (IJCAI), pp. 69–675. Morgan Kaufmann Publishers, San Francisco (1993)
Baader, F., Hollunder, B.: Embedding defaults into terminological knowledge representation formalisms. J. Autom. Reason. 14(1), 149–180 (1995)
Baader, F., Horrocks, I., Lutz, C., Sattler, U.: An Introduction to Description Logic. Cambridge University Press, Cambridge (2017)
Benferhat, S., Bouraoui, Z.: Min-based possibilistic DL-Lite. J. Logic Comput. 27(1), 261–297 (2017)
Blackburn, P., van Benthem, J., Wolter, F.: Handbook of Modal Logic. Elsevier, North-Holland (2006)
Bonatti, P., Faella, M., Petrova, I.M., Sauro, L.: A new semantics for overriding in description logics. Artif. Intell. 222, 1–48 (2015)
Bonatti, P., Faella, M., Sauro, L.: Defeasible inclusions in low-complexity DLs. J. Artif. Intell. Res. 42, 719–764 (2011)
Bonatti, P., Lutz, C., Wolter, F.: The complexity of circumscription in description logic. J. Artif. Intell. Res. 35, 717–773 (2009)
Bonatti, P., Sauro, L.: On the logical properties of the nonmonotonic description logic DL\(^{N}\). Artif. Intell. 248, 85–111 (2017)
Booth, R., Casini, G., Meyer, T., Varzinczak, I.: On the entailment problem for a logic of typicality. In: Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI), pp. 2805–2811 (2015)
Booth, R., Meyer, T., Varzinczak, I.: PTL: a propositional typicality logic. In: Fariñas del Cerro, L., Herzig, A., Mengin, J. (eds.) Proceedings of the 13th European Conference on Logics in Artificial Intelligence (JELIA), Number 7519 in LNCS, pp. 107–119. Springer, New York (2012)
Booth, R., Meyer, T., Varzinczak, I.: A propositional typicality logic for extending rational consequence. In: Fermé, E.L., Gabbay, D.M., Simari, G.R. (eds.) Trends in Belief Revision and Argumentation Dynamics, volume 48 of Studies in Logic–Logic and Cognitive Systems, pp. 123–154. King’s College Publications, London (2013)
Boutilier, C.: Conditional logics of normality: a modal approach. Artif. Intell. 68(1), 87–154 (1994)
Britz, K., Casini, G., Meyer, T., Varzinczak, I.: Preferential role restrictions. In: Proceedings of the 26th International Workshop on Description Logics, pp. 93–106 (2013)
Britz, K., Heidema, J., Meyer, T.: Semantic preferential subsumption. In: Lang, J., Brewka, G. (eds.) Proceedings of the 11th International Conference on Principles of Knowledge Representation and Reasoning (KR), pp. 476–484. AAAI Press/MIT Press, Cambridge (2008)
Britz, K., Heidema, J., Meyer, T.: Modelling object typicality in description logics. In: Nicholson, A., Li, X. (eds.) Proceedings of the 22nd Australasian Joint Conference on Artificial Intelligence, Number 5866 in LNAI, pp. 506–516. Springer, New York (2009)
Britz, K., Meyer, T., Varzinczak, I.: Semantic foundation for preferential description logics. In: Wang, D., Reynolds, M. (eds.) Proceedings of the 24th Australasian Joint Conference on Artificial Intelligence, Number 7106 in. Springer, New York (2011)
Britz, K., Varzinczak, I.: Introducing role defeasibility in description logics. In: Michael, L., Kakas, A.C. (eds.) Proceedings of the 15th European Conference on Logics in Artificial Intelligence (JELIA), Number 10021 in LNCS, pp. 174–189. Springer, New York (2016)
Britz, K., Varzinczak, I.: Context-based defeasible subsumption for \(d\cal{SROIQ}\). In: Proceedings of the 13th International Symposium on Logical Formalizations of Commonsense Reasoning (2017)
Britz, K., Varzinczak, I.: Toward defeasible \(\cal{SROIQ}\). In: Proceedings of the 30th International Workshop on Description Logics (2017)
Britz, K., Varzinczak, I.: From KLM-style conditionals to defeasible modalities, and back. J. Appl. Non Class. Log. (JANCL) 28(1), 92–121 (2018)
Britz, K., Varzinczak, I.: Preferential accessibility and preferred worlds. J. Log. Lang. Inf. (JoLLI) 27(2), 133–155 (2018)
Britz, K., Varzinczak, I.: Rationality and context in defeasible subsumption. In: Ferrarotti, F., Woltran, S. (eds.) Proceedings of the 10th International Symposium on Foundations of Information and Knowledge Systems (FoIKS), Number 10833 in LNCS, pp. 114–132. Springer, New York (2018)
Casini, G., Meyer, T., Moodley, K., Sattler, U., Varzinczak, I.: Introducing defeasibility into OWL ontologies. In: Arenas, M., Corcho, O., Simperl, E., Strohmaier, M., d’Aquin, M., Srinivas, K., Groth, P.T., Dumontier, M., Heflin, J., Thirunarayan, K., Staab, S. (eds.) Proceedings of the 14th International Semantic Web Conference (ISWC), Number 9367 in LNCS, pp. 409–426. Springer, New York (2015)
Casini, G., Straccia, U.: Rational closure for defeasible description logics. In: Janhunen, T., Niemelä, I. (eds.) Proceedings of the 12th European Conference on Logics in Artificial Intelligence (JELIA), Number 6341 in LNCS, pp. 77–90. Springer, New York (2010)
Casini, G., Straccia, U.: Defeasible inheritance-based description logics. J. Artif. Intellv Res. (JAIR) 48, 415–473 (2013)
Donini, F.M., Nardi, D., Rosati, R.: Description logics of minimal knowledge and negation as failure. ACM Trans. Comput. Log. 3(2), 177–225 (2002)
Giordano, L., Gliozzi, V., Olivetti, N., Pozzato, G.L.: Preferential description logics. In: Dershowitz, N., Voronkov, A. (eds.) Logic for Programming, Artificial Intelligence, and Reasoning (LPAR), Number 4790 in LNAI, pp. 257–272. Springer, New York (2007)
Giordano, L., Gliozzi, V., Olivetti, N., Pozzato, G.L.: Reasoning about typicality in preferential description logics. In: Hölldobler, S., Lutz, C., Wansing, H. (eds.) Proceedings of the 11th European Conference on Logics in Artificial Intelligence (JELIA), Number 5293 in LNAI, pp. 192–205. Springer, New York (2008)
Giordano, L., Gliozzi, V., Olivetti, N., Pozzato, G.L.: Analytic tableaux calculi for KLM logics of nonmonotonic reasoning. ACM Trans. Comput. Log. 10(3), 18:1–18:47 (2009)
Giordano, L., Gliozzi, V., Olivetti, N., Pozzato, G.L.: \(\cal{ALC}+{T}\): a preferential extension of description logics. Fundam. Inform. 96(3), 341–372 (2009)
Giordano, L., Gliozzi, V., Olivetti, N., Pozzato, G.L.: A non-monotonic description logic for reasoning about typicality. Artif. Intell. 195, 165–202 (2013)
Giordano, L., Gliozzi, V., Olivetti, N., Pozzato, G.L.: Semantic characterization of rational closure: from propositional logic to description logics. Artif. Intell. 226, 1–33 (2015)
Governatori, G.: Defeasible description logics. In: Antoniou, G., Boley, H. (eds.) Rules and Rule Markup Languages for the Semantic Web, Number 3323 in LNCS, pp. 98–112. Springer, New York (2004)
Grosof, B.N., Horrocks, I., Volz, R., Decker, S.: Description logic programs: combining logic programs with description logic. In: Proceedings of the 12th International Conference on World Wide Web (WWW), pp. 48–57. ACM (2003)
Heymans, S., Vermeir, D.: A defeasible ontology language. In: Meersman, R., Tari, Z. (eds.) CoopIS/DOA/ODBASE Number 2519 in LNCS, pp. 1033–1046. Springer, New York (2002)
Kraus, S., Lehmann, D., Magidor, M.: Nonmonotonic reasoning, preferential models and cumulative logics. Artif. Intell. 44, 167–207 (1990)
Lehmann, D., Magidor, M.: What does a conditional knowledge base entail? Artif. Intell. 55, 1–60 (1992)
Lindström, P.: First-order predicate logic with generalized quantifiers. Theoria 32, 286–195 (1966)
McCarthy, J.: Circumscription, a form of nonmonotonic reasoning. Artif. Intell. 13(1–2), 27–39 (1980)
McCarthy, J.: Applications of circumscription to formalizing common-sense knowledge. Artif. Intell. 28(1), 89–116 (1986)
Padgham, L., Zhang, T.: A terminological logic with defaults: A definition and an application. In: Bajcsy, R. (ed.) Proceedings of the 13th International Joint Conference on Artificial Intelligence (IJCAI), pp. 662–668. Morgan Kaufmann Publishers, London (1993)
Qi, G., Pan, J.Z., Ji, Q.: Extending description logics with uncertainty reasoning in possibilistic logic. In: Mellouli, K. (ed.) Proceedings of the 9th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty, Number 4724 in LNAI, pp. 828–839. Springer, New York (2007)
Quantz, J., Royer, V.: A preference semantics for defaults in terminological logics. In: Proceedings of the 3rd International Conference on Principles of Knowledge Representation and Reasoning (KR), pp. 294–305 (1992)
Quantz, J., Ryan, M.: Preferential default description logics. Technical report, TU Berlin (1993)
Schild, K.: A correspondence theory for terminological logics: Preliminary report. In: Proceedings of the 12th International Joint Conference on Artificial Intelligence (IJCAI), pp. 466–471 (1991)
Sengupta, K., Alfa Krisnadhi, A., Hitzler, P.: Local closed world semantics: grounded circumscription for OWL. In: Aroyo, L., Welty, C., Alani, H., Taylor, J., Bernstein, A., Kagal, L., Noy, N., Blomqvist, E. (eds.) Proceedings of the 10th International Semantic Web Conference (ISWC), Number 7031 in LNCS, pp. 617–632. Springer, New York (2011)
Shoham, Y.: Reasoning about Change: Time and Causation from the Standpoint of Artificial Intelligence. MIT Press, Cambridge (1988)
Straccia, U.: Default inheritance reasoning in hybrid KL-ONE-style logics. In: Bajcsy, R. (ed.) Proceedings of the 13th International Joint Conference on Artificial Intelligence (IJCAI), pp. 676–681. Morgan Kaufmann Publishers, London (1993)
Acknowledgements
I am grateful to Richard Booth, Arina Britz, Giovanni Casini, Fred Freitas and Tommie Meyer for many stimulating discussions on the topics of the present paper. I would like to thank Jean-Yves Béziau for encouraging me to participate in the logic contests. I am also grateful to the Universal Logic Prize jury members Hartry Field, Michèle Friend, Grzegorz Malinowski, Ahti-Veikko Pietarinen, Peter Schroeder-Heister, Göran Sundholm and Leon van der Torre for their appreciation of this work, and to the Louis Couturat Logic Prize anonymous referees for their constructive comments on an earlier version of the present paper. This work was partially supported by the project Reconciling Description Logics and Non-Monotonic Reasoning in the Legal Domain (PRC CNRS–FACEPE France–Brazil). Special thanks to Sihem, without whose support this work would have not come to existence, and to whom I dedicate the logic prizes it has won.
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was the recipient of the first Louis Couturat Logic Prize (France, 2018). It was then presented at the Universal Logic Contest at UNILOG 2018 in Vichy and subsequently won the first Universal Logic Prize.
Rights and permissions
About this article
Cite this article
Varzinczak, I. A Note on a Description Logic of Concept and Role Typicality for Defeasible Reasoning Over Ontologies. Log. Univers. 12, 297–325 (2018). https://doi.org/10.1007/s11787-018-0211-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11787-018-0211-x