Towards a Rational Closure for Expressive Description Logics : the Case of SHIQ

• Autorzy: Giordano L. , Gliozzi V. , Olivetti N.

Identyfikatory

DOI

10.3233/FI-2018-1659

• Konferencja: Convegno Italiano di Logica Computazionale : CILC 2015 (30th; 01-03.07.2015; University of Genoa, Italy)
• Języki publikacji: EN

Abstrakty

EN

We explore the extension of the notion of rational closure to logics lacking the finite model property, considering the logic SHIQ. We provide a semantic characterization of rational closure in SHIQ in terms of a preferential semantics, based on a finite rank characterization of minimal models. We show that the rational closure of a KB can be computed in EXPTIME based on a polynomial encoding of the rational extension of SHIQ into entailment in SHIQ. We discuss the extension of rational closure to more expressive description logics.

Słowa kluczowe

EN

description logics; nonmonotonic reasoning

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2018
• Tom: Vol. 159, nr 1/2
• Strony: 95--122
• Opis fizyczny: Bibliogr. 38 poz.

Twórcy

autor

Giordano L.

• DISIT, Università del Piemonte Orientale "A. Avogadro", viale Teresa Michel, 11-15121, Alessandria, Italy

autor

Gliozzi V.

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

autor

Olivetti N.

• Aix Marseille Univ, Universit de Toulon, CNRS, LIS, Marseille, France

Bibliografia

• [1] Baader F, and Hollunder B. Priorities on Defaults with Prerequisites, and Their Application in Treating Specificity in Terminological Default Logic, Journal of Automated Reasoning (JAR), 1995;15(1):41-68. URL https://doi.org/10.1007/BF00881830.
• [2] Bonatti PA, Faella M, Petrova I, and Sauro L. A new semantics for overriding in description logics, Artif. Intell., 2015;222:1-48. doi:10.1016/j.artint.2014.12.010.
• [3] Bonatti PA, Lutz C, and Wolter F. The Complexity of Circumscription in DLs, Journal of Artificial Intelligence Research (JAIR), 2009;35:717-773. doi:10.1613/jair.2763.
• [4] Britz K, Heidema J, and Meyer T. Semantic Preferential Subsumption, Principles of Knowledge Representation and Reasoning: Proceedings of the 11th International Conference (KR 2008) (G. Brewka, J. Lang, Eds.), AAAI Press, Sidney, Australia, September 2008.
• [5] Casini G, Meyer T, Varzinczak IJ, and Moodley K. Nonmonotonic Reasoning in Description Logics: Rational Closure for the ABox, DL 2013, 26th International Workshop on Description Logics, 1014, CEUR-WS.org, 2013.
• [6] Casini G, and Straccia U. Rational Closure for Defeasible Description Logics, Proceedings of the 12th European Conference on Logics in Artificial Intelligence (JELIA 2010) (T. Janhunen, I. Niemelä, Eds.), 6341, Springer, Helsinki, Finland, September 2010. URL https://doi.org/10.1007/978-3-642-15675-5_9.
• [7] Casini G, and Straccia U. Defeasible Inheritance-Based Description Logics, Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI 2011) (T. Walsh, Ed.), Morgan Kaufmann, Barcelona, Spain, July 2011.
• [8] Casini G, and Straccia U. Lexicographic Closure for Defeasible Description Logics, Proc. of Australasian Ontology Workshop, vol.969, 2012.
• [9] Casini G, and Straccia U. Defeasible inheritance-based description logics, Journal of Artificial Intelligence Research (JAIR), 2013;48:415-473. URL http://dl.acm.org/citation.cfm?id=2591248.2591258.
• [10] Donini FM, Nardi D, and Rosati R. Description logics of minimal knowledge and negation as failure, ACM Transactions on Computational Logic (ToCL), 2002;3(2):177-225. doi:10.1145/505372.505373.
• [11] Eiter T, Ianni G, Lukasiewicz T, Schindlauer R, and Tompits H. Combining answer set programming with description logics for the Semantic Web, Artif. Intell., 2008;172(12-13):1495-1539. URL https://doi.org/10.1016/j.artint.2008.04.002.
• [12] Eiter T, Lukasiewicz T, Schindlauer R, and Tompits H. Combining Answer Set Programming with Description Logics for the Semantic Web, Principles of Knowledge Representation and Reasoning: Proceedings of the 9th International Conference (KR 2004) (D. Dubois, C. Welty, M. Williams, Eds.), AAAI Press, Whistler, Canada, June 2004.
• [13] Freund M. Preferential Reasoning in the Perspective of Poole Default Logic, Artif. Intell., 1998;98(1-2):209-235. URL https://doi.org/10.1016/S0004-3702(97)00053-2.
• [14] Giordano L, and Gliozzi V. Encoding a Preferential Extension of the Description Logic SROIQ into SROIQ, Proc. ISMIS 2015, 9384, Springer, 2015 pp. 248-258. URL https://doi.org/10.1007/978-3-319-25252-0_27.
• [15] Giordano L, Gliozzi V, Olivetti N, and Pozzato GL. Preferential Description Logics, Proceedings of LPAR 2007 (14th Conference on Logic for Programming, Artificial Intelligence, and Reasoning) (N. Dershowitz, A. Voronkov, Eds.), 4790, Springer-Verlag, Yerevan, Armenia, 2007 pp. 257-272. URL https://doi.org/10.1007/978-3-540-75560-9_20.
• [16] Giordano L, Gliozzi V, Olivetti N, and Pozzato GL. ALC+T: a Preferential Extension of Description Logics, Fundamenta Informaticae, 2009;96(3):341-372. doi:10.3233/FI-2009-182.
• [17] Giordano L, Gliozzi V, Olivetti N, and Pozzato GL. Minimal Model Semantics and Rational Closure in Description Logics, 26th International Workshop on Description Logics (DL 2013) (T. Eiter, B. Glim, Y. Kazakov, M. Krtzsch, Eds.), 1014, Ulm, Germany, 7 2013.
• [18] Giordano L, Gliozzi V, Olivetti N, and Pozzato GL. A NonMonotonic Description Logic for Reasoning About Typicality, Artificial Intelligence, 2013;195:165-202. ISSN: 0004-3702. URL https://doi.org/10.1016/j.artint.2012.10.004.
• [19] Giordano L, Gliozzi V, Olivetti N, and Pozzato GL. Minimal models for rational closure in shiq, Proceedings of the 15th Italian Conference on Theoretical Computer Science, Perugia, Italy, September 17-19, CEUR Workshop Proceedings, 1231, CEUR-WS.org, 2014.
• [20] Giordano L, Gliozzi V, Olivetti N, and Pozzato GL. Rational Closure in SHIQ, DL2014, CEUR Workshop Proceedings, 1193, 2014. arXiv:1406.2023 [cs.AI].
• [21] Giordano L, Gliozzi V, Olivetti N, and Pozzato GL. Semantic characterization of rational closure: From propositional logic to description logics, Artificial Intelligence, 226, 2015, 1-33, ISSN 0004-3702.
• [22] Giordano L, Gliozzi V, Pozzato G, and Renzulli R. An Efficient Reasoner for Description Logics of Typicality and Rational Closure, DL 2013, Proceedings of the 30th International Workshop on Description Logics, Montpellier, France, July 18-21, 2017.
• [23] Giordano L, and Theseider Dupré D. ASP for minimal entailment in a rational extension of SROEL, TPLP, 2016;16(5-6):738-754. URL https://doi.org/10.1017/S1471068416000399.
• [24] Giordano L, and Theseider Dupré D. Reasoning in a Rational Extension of SROEL, Proceedings of the 31st Italian Conference on Computational Logic, Milano, Italy, June 20-22, 2016., 1645, CEUR-WS.org, 2016.
• [25] Gliozzi V. Reasoning about Multiple Aspects in Rational Closure for DLs, AI*IA 2016, XVth International Conference of the Italian Association for Artificial Intelligence, vol. 10037. Genova, Italy, November 29 - December 1, 2016, Proceedings, 2016 pp. 392-405. doi:10.1007/978-3-319-49130-1_29.
• [26] Gottlob G, Hernich A, Kupke C, and Lukasiewicz T. Stable Model Semantics for Guarded Existential Rules and Description Logics, Proc. KR. 2014 pp. 258-267. ISBN: 1-57735-657-8 978-1-57735-657-8.
• [27] Horrocks I, Kutz O, and Sattler U. The Even More Irresistible SROIQ, Proceedings, Tenth International Conference on Principles of Knowledge Representation and Reasoning, Lake District of the United Kingdom, June 2-5, 2006, 2006 pp. 57-67. ISBN: 978-1-57735-271-6.
• [28] Horrocks I, and Sattler U. A tableaux decision procedure for SHOIQ, Proc. of the 19th Int. Joint Conf. on Artificial Intelligence (IJCAI 2005) (L. P. Kaelbling, A. Saffiotti, Eds.), Professional Book Center, 2005 pp. 448-453. URL http://dl.acm.org/citation.cfm?id=1642293.1642365.
• [29] Horrocks I, Sattler U, and Tobies S. Practical Reasoning for Very Expressive Description Logics, Logic Journal of the IGPL, 2000;8(3):239-263. arXiv:cs/0005013 [cs.LO].
• [30] Ke P, and Sattler U. Next Steps for Description Logics of Minimal Knowledge and Negation as Failure, DL 2008, CEUR Workshop Proceedings (F. Baader, C. Lutz, B. Motik, Eds.), vol. 353 of CEUR-WS.org, Dresden, Germany, May 2008.
• [31] Knorr M, Hitzler P, and Maier F. Reconciling OWL and non-monotonic rules for the semantic web, ECAI 2012, 2012 pp. 474-479. doi:10.3233/978-1-61499-098-7-474.
• [32] Kraus S, Lehmann D, and Magidor M. Nonmonotonic Reasoning, Preferential Models and Cumulative Logics, Artificial Intelligence, 1990;44(1-2):167-207. doi:10.1016/0004-3702(90)90101-5.
• [33] Krisnadhi AA, Sengupta K, and Hitzler P. Local Closed World Semantics: Keep it simple, stupid!, Proceedings of Description Logics, 745, no 11. Barcelona, Spain, July 2011. URL http://corescholar.libraries.wright.edu/cse/112.
• [34] Krötzsch M. Efficient Inferencing for OWL EL, In: Janhunen T., Niemelä I. (eds) Logics in Artificial Intelligence. JELIA 2010. vol. 6341 of LNCS. Springer, Berlin, Heidelberg 2010 pp. 234-246. URL https://doi.org/10.1007/978-3-642-15675-5_21.
• [35] Lehmann D, and Magidor M. What does a conditional knowledge base entail?, Artificial Intelligence, 1992;55(1):1-60, ISSN: 0004-3702. URL https://doi.org/10.1016/0004-3702(92)90041-U.
• [36] Lehmann DJ. Another Perspective on Default Reasoning, Ann. Math. Artif. Intell., 1995;15(1):61-82. URL https://doi.org/10.1007/BF01535841.
• [37] Motik B, and Rosati R. Reconciling Description Logics and rules, Journal of the ACM, 2010;57(5), no.30. doi:10.1145/1754399.1754403.
• [38] Straccia U. Default Inheritance Reasoning in Hybrid KL-ONE-Style Logics, Proc. of the 13th Int. Joint Conf. on Artif. Intell. (IJCAI 1993) (R. Bajcsy, Ed.), Morgan Kaufmann, Chambéry, France, 1993 pp. 676-681. URL http://dl.acm.org/citation.cfm?id=1624025.1624120.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).