Defeasible Reasoning in SROEL : from Rational Entailment to Rational Closure

Giordano, L.; Dupré, D. T.

doi:10.3233/FI-2018-1698

Artykuł - szczegóły

Tytuł artykułu

Defeasible Reasoning in SROEL : from Rational Entailment to Rational Closure

Autorzy

Giordano L. , Dupré D. T.

Wybrane pełne teksty z tego czasopisma

https://fi.episciences.org/

Identyfikatory

DOI

10.3233/FI-2018-1698

Warianty tytułu

Konferencja

Italian Conference on Computational Logic (Convegno Italiano di Logica Computazionale, CILC 2016) (31; 20-22.07.2016; Università degli Studi di Milano-Bicocca, Italy)

Języki publikacji

Abstrakty

In this work we study a rational extension SROEL(⊓, x)^R T of the low complexity description logic SROEL(⊓, x), which underlies the OWL EL ontology language. The extension involves a typicality operator T, whose semantics is based on Lehmann and Magidor’s ranked models and allows for the definition of defeasible inclusions. We consider both rational entailment and minimal entailment. We show that deciding instance checking under minimal entailment is in general ∏₂^P -hard, while, under rational entailment, instance checking can be computed in polynomial time. We develop a Datalog calculus for instance checking under rational entailment and exploit it, with stratified negation, for computing the rational closure of simple KBs in polynomial time.

Słowa kluczowe

mathematical analysis mathematical models machine theory theorem polynomials ontology

Wydawca

IOS Press

Czasopismo

Fundamenta Informaticae

Rocznik

2018

Tom

Vol. 161, nr 1/2

Strony

135--161

Opis fizyczny

Bibliogr. 50 poz.

Twórcy

autor

Giordano L.

laura.giordano@uniupo.it

DISIT, Università del Piemonte Orientale “A. Avogadro”, Viale Teresa Michel, 11-15121, Alessandria, Italy

autor

Dupré D. T.

dtd@di.unipmn.it

DISIT, Università del Piemonte Orientale “A. Avogadro”, Viale Teresa Michel, 11-15121, Alessandria, Italy

Bibliografia

[1] Baader F, Hollunder B. Embedding Defaults into Terminological Knowledge Representation Formalisms. In: Proceedings of the 3rd International Conference on Principles of Knowledge Representation and Reasoning (KR’92). Cambridge, MA, October 25-29, 1992. 1992 pp. 306-317.
[2] Straccia U. Default Inheritance Reasoning in Hybrid KL-ONE-Style Logics. In: Proc. IJCAI 1993. 1993 pp. 676-681.
[3] Baader F, Hollunder B. Priorities on Defaults with Prerequisites, and Their Application in Treating Specificity in Terminological Default Logic. J. of Automated Reasoning, 1995. 15(1):41-68. doi:10.1007/BF00881830.
[4] Donini FM, Nardi D, 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.
[5] Giordano L, Gliozzi V, Olivetti N, Pozzato GL. Preferential Description Logics. In: Proceedings of LPAR 2007, volume 4790 of LNAI. Springer-Verlag, 2007 pp. 257-272. doi:10.1007/978-3-540-75560-9_20.
[6] Eiter T, Ianni G, Lukasiewicz T, Schindlauer R, 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.
[7] Ke P, Sattler U. Next Steps for Description Logics of Minimal Knowledge and Negation as Failure. In: Proc. DL 2008, volume 353 of CEUR Workshop Proceedings. 2008.
[8] Britz K, Heidema J, Meyer T. Semantic Preferential Subsumption. In: Brewka G, Lang J (eds.), Proc. KR 2008. 2008 pp. 476-484.
[9] Bonatti PA, Lutz C, Wolter F. The Complexity of Circumscription in DLs. J. of Artificial Intelligence Research, 2009. 35:717-773. doi:10.1613/jair.2763.
[10] Casini G, Straccia U. Rational Closure for Defeasible Description Logics. In: Proc. JELIA 2010, LNAI 6341. Springer, 2010 pp. 77-90. doi:10.1007/978-3-642-15675-5_9.
[11] Motik B, Rosati R. Reconciling Description Logics and rules. J. ACM, 2010. 57(5). doi:10.1145/1754399.1754403.
[12] Bonatti PA, Faella M, Sauro L. Defeasible Inclusions in Low-Complexity DLs. J. Artif. Intell. Res. (JAIR), 2011. 42:719-764. doi:10.1613/jair.3360.
[13] Knorr M, Hitzler P, Maier F. Reconciling OWL and non-monotonic rules for the semantic web. In: ECAI 2012. 2012 p. 474-479. doi:10.3233/978-1-61499-098-7-474.
[14] Casini G, Meyer T, Varzinczak IJ, Moodley K. Nonmonotonic Reasoning in Description Logics: Rational Closure for the ABox. In: Proc. DL 2013. 2013 pp. 600-615.
[15] Giordano L, Gliozzi V, Olivetti N, Pozzato GL. A NonMonotonic Description Logic for Reasoning About Typicality. Artificial Intelligence, 2013. 195:165-202. doi:10.1016/j.artint.2012.10.004.
[16] Bonatti PA, Faella M, Petrova I, Sauro L. A new semantics for overriding in description logics. Artif. Intell., 2015. 222:1-48. URL https://doi.org/10.1016/j.artint.2014.12.010.
[17] Giordano L, Gliozzi V, Olivetti N, Pozzato GL. Semantic characterization of rational closure: From propositional logic to description logics. Artif. Intell., 2015. 226:1-33. URL https://doi.org/10.1016/j.artint.2015.05.001.
[18] Eiter T, Ianni G, Lukasiewicz T, Schindlauer R. Well-founded semantics for description logic programs in the semantic web. ACM Trans. Comput. Log., 2011. 12(2):11. doi:10.1145/1877714.1877717.
[19] Gottlob G, Hernich A, Kupke C, Lukasiewicz T. Stable Model Semantics for Guarded Existential Rules and Description Logics. In: Proc. KR 2014. 2014.
[20] Gelfond M, Leone N. Logic programming and knowledge representation - The A-Prolog perspective. Artif. Intell., 2002. 138(1-2):3-38. URL https://doi.org/10.1016/S0004-3702(02)00207-2.
[21] Gelfond M. Handbook of Knowledge Representation, chapter 7, Answer Sets. Elsevier, 2007. ISBN:0444522115, 9780444522115.
[22] Xiao G, Eiter T, Heymans S. The DReW System for Nonmonotonic DL-Programs. In: Proc. CSWS 2012. 2012 pp. 383-390. doi:10.1007/978-1-4614-6880-6_33.
[23] Krötzsch M. Efficient Inferencing for OWL EL. In: Proc. JELIA 2010. 2010 pp. 234-246. doi:10.1007/978-3-642-15675-5_21.
[24] Baader F, Brandt S, Lutz C. Pushing the EL envelope. In: Proc IJCAI 2005. 2005 pp. 364-369. URL http://dl.acm.org/citation.cfm?id=1642293.1642351.
[25] Kraus S, Lehmann D, Magidor M. Nonmonotonic Reasoning, Preferential Models and Cumulative Logics. Artif. Intell., 1990. 44(1-2):167-207.
[26] Lehmann D, Magidor M. What does a conditional knowledge base entail? Artificial Intelligence, 1992. 55(1):1-60. doi:http://dx.doi.org/10.1016/0004-3702(92)90041-U.
[27] Giordano L, Gliozzi V, Olivetti N, Pozzato GL. ALC+T: a Preferential Extension of Description Logics. Fundamenta Informaticae, 2009. 96:1-32. doi:10.3233/FI-2009-185.
[28] Booth R, Casini G, Meyer T, Varzinczak IJ. On the Entailment Problem for a Logic of Typicality. In: Proc. IJCAI 2015. 2015 pp. 2805-2811. ISBN:978-1-57735-738-4.
[29] Giordano L, Gliozzi V. Encoding a Preferential Extension of the Description Logic SROIQ into SROIQ. In: Proc. ISMIS 2015, volume 9384 of LNCS. Springer, 2015 pp. 248-258. doi:10.1007/978-3-319-25252-0_27.
[30] Casini G, 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.
[31] Moodley K. Practical Reasoning for Defeasible Description Logics. PhD Thesis, University of Kwazulu-Natal, 2016. doi:10.3233/978-1-61499-421-3-191.
[32] Giordano L, Theseider Dupré D. Reasoning in a Rational Extension of SROEL. In: DL2016, volume 1577 of CEUR Workshop Proceedings. 2016.
[33] Giordano L, Theseider Dupré D. Reasoning in a Rational Extension of SROEL. In: Proceedings of the 31st Italian Conference on Computational Logic, Milano, Italy, June 20-22, 2016., volume 1645 of CEUR Workshop Proceedings. CEUR-WS.org, 2016 pp. 53-68.
[34] Giordano L, Theseider Dupré D. ASP for minimal entailment in a rational extension of SROEL. TPLP, 2016. 16(5-6):738-754. doi:10.1017/S1471068416000399.
[35] Eiter T, Gottlob G. On the Computational Cost of Disjunctive Logic Programming: Propositional Case. Annals of Mathematics and Artificial Intelligence, 1995. 15(3-4):289-323. doi:10.1007/BF01536399.
[36] Krötzsch M. Efficient Inferencing for the description logic underlying OWL EL. Tech. Rep. 3005, Institute AIFB, Karlsruhe Institute of Technology, 2010.
[37] Przymusinski TC. Stable Semantics for Disjunctive Programs. New Generation Comput., 1991. 9(3/4): 401-424. doi:10.1007/BF03037171.
[38] Eiter T, Gottlob G, Mannila H. Disjunctive Datalog. ACM Trans. Database Syst., 1997. 22(3):364-418. doi:10.1145/261124.261126.
[39] Bozzato L, Eiter T, Serafini L. Contextualized Knowledge Repositories with Justifiable Exceptions. In: DL 2014, volume 1193 of CEUR Workshop Proceedings. CEUR-WS.org, 2014 pp. 112-123.
[40] Giordano L, Gliozzi V, Olivetti N, Pozzato GL. Prototypical Reasoning with Low Complexity Description Logics: Preliminary Results. In: Proc. LPNMR 2009. 2009 pp. 430-436. doi:10.1007/978-3-642-04238-6_38.
[41]Giordano L, Gliozzi V, Olivetti N, Pozzato GL. Reasoning about typicality in low complexity DLs: the logics EL⊥Tmin and DL-Lite cTmin. In: Proc. IJCAI 2011. Barcelona, 2011 pp. 894-899.
[42] Casini G, Straccia U. Lexicographic Closure for Defeasible Description Logics. In: Proc. Australasian Ontology Workshop. 2012 pp. 28-39.
[43] Lehmann DJ. Another Perspective on Default Reasoning. Ann. Math. Artif. Intell., 1995. 15(1):61-82. doi:10.1007/BF01535841.
[44] Gil OF. On the Non-Monotonic Description Logic ALC+Tmin. CoRR, 2014. abs/1404.6566.
[45] Gliozzi V. A Minimal Model Semantics for Rational Closure. In: Kern-Isberner G, Wassermann R (eds.), NMR 2016 (16th International Workshop on Non-Monotonic Reasoning). Cape Town, South Africa, 2016.
[46] Beierle C, Eichhorn C, Kern-Isberner G. Skeptical Inference Based on C-Representations and Its Characterization as a Constraint Satisfaction Problem. In: Foundations of Information and Knowledge Systems - 9th International Symposium, FoIKS 2016, Linz, Austria, March 7-11, 2016. Proceedings. 2016 pp. 65-82. doi:10.1007/978-3-319-30024-5_4.
[47] Deane G, Broda K, Russo A. Reasoning in the presence of inconsistency through Preferential ALC. In: 20th International Conferences on Logic for Programming, Artificial Intelligence and Reasoning – Short Presentations, LPAR 2015, Suva, Fiji, November 24-28, 2015. 2015 pp. 67-80. doi:10.29007/8qr4.
[48] Bonatti PA, Petrova IM, Sauro L. Optimizing the Computation of Overriding. In: Proc. ISWC 2015. 2015 pp. 356-372. doi:10.1007/978-3-319-25007-6_21.
[49] Lembo D, Lenzerini M, Rosati R, Ruzzi M, Savo D. Inconsistency-tolerant query answering in ontology-based data access. J. Web Sem., 2015. 33:3-29. URL https://doi.org/10.1016/j.websem.2015.04.002.
[50] Baget J, Benferhat S, Bouraoui Z, Croitoru M, Mugnier M, Papini O, Rocher S, Tabia K. Inconsistency-Tolerant Query Answering: Rationality Properties and Computational Complexity Analysis. In: Logics in Artificial Intelligence - 15th European Conference, JELIA 2016, Larnaca, Cyprus, November 9-11, 2016, Proceedings. 2016 pp. 64-80. doi:10.1007/978-3-319-48758-8_5.

Uwagi

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

Typ dokumentu

Bibliografia

Identyfikator YADDA

bwmeta1.element.baztech-cb978d2d-50f5-4e1a-9a84-0ccac1ec5d0e