Probabilistic DL reasoning with pinpointing formulas: a Prolog-based approach. (English) Zbl 1472.68194

Summary: When modeling real-world domains, we have to deal with information that is incomplete or that comes from sources with different trust levels. This motivates the need for managing uncertainty in the Semantic Web. To this purpose, we introduced a probabilistic semantics, named DISPONTE, in order to combine description logics (DLs) with probability theory. The probability of a query can be then computed from the set of its explanations by building a Binary Decision Diagram (BDD). The set of explanations can be found using the tableau algorithm, which has to handle non-determinism. Prolog, with its efficient handling of non-determinism, is suitable for implementing the tableau algorithm. TRILL and \(\mathrm{TRILL}^{P}\) are systems offering a Prolog implementation of the tableau algorithm. \(\mathrm{TRILL}^{P}\) builds a pinpointing formula that compactly represents the set of explanations and can be directly translated into a BDD. Both reasoners were shown to outperform state-of-the-art DL reasoners. In this paper, we present an improvement of \(\mathrm{TRILL}^{P}\), named TORNADO, in which the BDD is directly built during the construction of the tableau, further speeding up the overall inference process. An experimental comparison shows the effectiveness of TORNADO. All systems can be tried online in the TRILL on SWISH web application at http://trill.ml.unife.it/.


68T27 Logic in artificial intelligence
68N17 Logic programming
68T30 Knowledge representation
Full Text: DOI arXiv


[1] Baader, F., Horrocks, I. and Sattler, U.2008. Description Logics. Elsevier, Amsterdam, Chapter 3, 135-179. · Zbl 1098.68705
[2] Baader, F. and Peñaloza, R.2010a. Automata-based axiom pinpointing. Journal of Automated Reasoning45, 2, 91-129. · Zbl 1213.68589
[3] Baader, F. and Peñaloza, R.2010b. Axiom pinpointing in general tableaux. Journal of Logic and Computation20, 1, 5-34. · Zbl 1191.68645
[4] Baader, F. and Sattler, U.2001. An overview of tableau algorithms for description logics. Studia Logica69, 1, 5-40. · Zbl 0991.03012
[5] Beckert, B. and Posegga, J.1995. leanTAP: Lean tableau-based deduction. Journal of Automated Reasoning15, 3, 339-358. · Zbl 0838.68097
[6] Bellodi, E., Lamma, E., Riguzzi, F. and Albani, S.2011. A distribution semantics for probabilistic ontologies. In Proc. of the 7th International Workshop on Uncertainty Reasoning for the Semantic Web, Bonn, Germany, 23 Oct. 2011, Bobillo, F., Carvalho, R., Da Costa, P. C. G., D’Amato, C., Fanizzi, N., Laskey, K. B., Laskey, K. J., Lukasiewicz, T., Martin, T., Nickles, M., and Pool, M., Eds. CEUR-WS, vol. 778. Sun SITE Central Europe, Aachen, Germany, 75-86.
[7] Bock, C., Fokoue, A., Hoekstra, R., Horrocks, I., Ruttenberg, A., Sattler, U. and Smith, M.2012. OWL 2 web ontology language: Structural specification and functional-style syntax. W3C Recommendation. URL: https://www.w3.org/TR/owl2-syntax/.
[8] Bryant, R. E.1986. Graph-based algorithms for boolean function manipulation. IEEE Transactions on Computers35, 8 (Aug.), 677-691. · Zbl 0593.94022
[9] Carvalho, R. N., Laskey, K. B. and Da Costa, P. C. G.2013. PR-OWL 2.0 - bridging the gap to OWL semantics. In Uncertainty Reasoning for the Semantic Web II, International Workshops URSW 2008-2010 Held at ISWC and UniDL 2010 Held at FLoC, Revised Selected Papers, Bobillo, F., Da Costa, P. C. G., D’Amato, C., Fanizzi, N., Laskey, K. B., Laskey, K. J., Lukasiewicz, T., Nickles, M., and Pool, M., Eds. LNCS, vol. 7123. Springer, 1-18.
[10] Ceylan, İ. İ., Mendez, J. and Peñaloza, R.2015. The Bayesian ontology reasoner is born! In Informal Proc. of the 4th International Workshop on OWL Reasoner Evaluation (ORE-2015) Co-located with the 28th International Workshop on Description Logics (DL 2015), Dumontier, M., Glimm, B., Gonçalves, R. S., Horridge, M., Jiménez-Ruiz, E., Matentzoglu, N., Parsia, B., Stamou, G. B., and Stoilos, G., Eds. CEUR-WS, vol. 1387. CEUR-WS.org, 8-14.
[11] Ceylan, İ. İ. and Peñaloza, R.2015. Probabilistic query answering in the bayesian description logic BEl. In SUM 2015, Beierle, C., and Dekhtyar, A., Eds. Lecture Notes in Computer Science (LNCS), vol. 9310. Springer, 21-35.
[12] Ding, Z. and Peng, Y.2004. A probabilistic extension to ontology language OWL. In 37th Hawaii International Conference on System Sciences (HICSS-37 2004), CD-ROM / Abstracts Proceedings, 5-8 Jan. 2004, Sprague, R. H. Jr., Ed. IEEE Computer Society, Big Island, HI, USA, 1-10.
[13] Gavanelli, M., Lamma, E., Riguzzi, F., Bellodi, E., Zese, R. and Cota, G.2015. An abductive framework for datalog± ontologies. In Technical Communications of the 31st International Conference on Logic Programming (ICLP 2015), Vos, M. D., Eiter, T., Lierler, Y., and Toni, F., Eds. CEUR-WS, vol. 1433. CEUR-WS.org. · Zbl 1407.68479
[14] Heinsohn, J. 1994. Probabilistic description logics. In 10th Conference on Uncertainty in Artificial Intelligence (UAI 1994), Seattle, Washington, 29-31 Jul. 1994, De Mántaras, R. L., and Poole, D., Eds. Morgan Kaufmann, 311-318.
[15] Horrocks, I., Kutz, O. and Sattler, U.2006. The even more irresistible SROIQ. In Proc. of the 10th International Conference on Principles of Knowledge Representation and Reasoning, Lake District of the United Kingdom, 2-5 Jun. 2006, Doherty, P., Mylopoulos, J., and Welty, C. A., Eds. AAAI Press, 57-67.
[16] Horrocks, I. and Sattler, U.2007. A tableau decision procedure for \({\cal S}{\cal H}{\cal O}{\cal I}{\cal Q}\). Journal of Automated Reasoning39, 3, 249-276. · Zbl 1132.68734
[17] Hustadt, U., Motik, B. and Sattler, U.2008. Deciding expressive description logics in the framework of resolution. Information and Computation206, 5, 579-601. · Zbl 1146.68456
[18] Jaeger, M. 1994. Probabilistic reasoning in terminological logics. In 4th International Conference on Principles of Knowledge Representation and Reasoning, Doyle, J., Sandewall, E., and Torasso, P., Eds. Morgan Kaufmann, 305-316.
[19] Jung, J. C. and Lutz, C.2012. Ontology-based access to probabilistic data with OWL QL. In The Semantic Web- ISWC 2012- 11th International Semantic Web Conference, Cudré-Mauroux, P., Heflin, J., Sirin, E., Tudorache, T., Euzenat, J., Hauswirth, M., Parreira, J. X., Hendler, J., Schreiber, G., Bernstein, A., and Blomqvist, E., Eds. LNCS, vol. 7649. Springer, Berlin, Heidelberg, 182-197.
[20] Kifer, M. and Subrahmanian, V. S.1992. Theory of generalized annotated logic programming and its applications. The Journal of Logic Programming12, 3&4, 335-367.
[21] Kimmig, A., Demoen, B., De Raedt, L., Costa, V. S., and Rocha, R.2011. On the implementation of the probabilistic logic programming language ProbLog. Theory and Practice of Logic Programming11, 2-3, 235-262. · Zbl 1220.68037
[22] Klinov, P. 2008. Pronto: A non-monotonic probabilistic description logic reasoner. In Proc. of the Semantic Web: Research and Applications, 5th European Semantic Web Conference, ESWC 2008, Tenerife, Canary Islands, Spain, 1-5 Jun. 2008, Bechhofer, S., Hauswirth, M., Hoffmann, J., and Koubarakis, M., Eds. LNCS, vol. 5021. Springer, 822-826.
[23] Klinov, P. and Parsia, B.2008. Optimization and evaluation of reasoning in probabilistic description logic: Towards a systematic approach. In Proc. of the Semantic Web - ISWC 2008, 7th International Semantic Web Conference, ISWC 2008, Karlsruhe, Germany, 26-30 Oct. 2008, Sheth, A. P., Staab, S., Dean, M., Paolucci, M., Maynard, D., Finin, T. W., and Thirunarayan, K., Eds. Lecture Notes in Computer Science, vol. 5318. Springer, 213-228.
[24] Klinov, P. and Parsia, B.2011. A hybrid method for probabilistic satisfiability. In CADE, Bjørner, N., and Sofronie-Stokkermans, V., Eds. LNCS, vol. 6803. 354-368. · Zbl 1341.68191
[25] Koller, D., Levy, A. Y. and Pfeffer, A.1997. P-CLASSIC: A tractable probabilistic description logic. In Fourteenth National Conference on Artificial Intelligence and Ninth Innovative Applications of Artificial Intelligence Conference, AAAI 97, IAAI 97, Providence, Rhode Island, 27-31 Jul. 1997, Kuipers, B., and Webber, B. L., Eds. AAAI Press/The MIT Press, 390-397.
[26] Lakshmanan, L. V. S. and Sadri, F.2001. On a theory of probabilistic deductive databases. Theory and Practice of Logic Programming1, 1, 5-42.
[27] Lukácsy, G. and Szeredi, P.2009. Efficient description logic reasoning in prolog: The dlog system. Theory and Practice of Logic Programming9, 3, 343-414. · Zbl 1179.68024
[28] Lukasiewicz, T.2008. Expressive probabilistic description logics. Artificial Intelligence172, 6-7, 852-883. · Zbl 1182.68283
[29] Lutz, C. and Schröder, L.2010. Probabilistic Description Logics for subjective uncertainty. In 12th International Conference on Principles of Knowledge Representation and Reasoning (KR 2010), Lin, F., Sattler, U., and Truszczynski, M., Eds. AAAI Press, Menlo Park, CA, USA, 393-403.
[30] Nilsson, N. J.1986. Probabilistic logic. Artificial Intelligence28, 1, 71-87. · Zbl 0589.03007
[31] Panda, S. and Somenzi, F.1995. Who are the variables in your neighborhood. In Proceedings of the 1995 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 1995, San Jose, California, USA, 5-9 Nov. 1995, Rudell, R. L., Ed. IEEE Computer Society/ACM, 74-77.
[32] Patel-Schneider, P. F., Horrocks, I. and Bechhofer, S.2003. Tutorial on OWL. In The Semantic Web - ISWC 2003, 2nd International Semantic Web Conference, Sanibel Island, FL, USA, 2023 Oct. 2013. URL: http://www.cs.man.ac.uk/ horrocks/ISWC2003/Tutorial/.
[33] Reiter, R.1987. A theory of diagnosis from first principles. Artificial Intelligence32, 1, 57-95. · Zbl 0643.68122
[34] Ricca, F., Gallucci, L., Schindlauer, R., Dell’Armi, T., Grasso, G. and Leone, N.2009. OntoDLV: An ASP-based system for enterprise ontologies. Journal of Logic and Computation19, 4, 643-670. · Zbl 1192.68132
[35] Riguzzi, F., Bellodi, E., Lamma, E. and Zese, R.2013. Parameter learning for probabilistic ontologies. In RR 2013, Faber, W., and Lembo, D., Eds. LNCS, vol. 7994. Springer, Berlin, Heidelberg, 265-270. · Zbl 1347.68320
[36] Riguzzi, F., Bellodi, E., Lamma, E. and Zese, R.2015. Probabilistic description logics under the distribution semantics. Semantic Web6, 5, 447-501. · Zbl 1400.68226
[37] Riguzzi, F. and Swift, T.2010. Tabling and answer subsumption for reasoning on logic programs with annotated disjunctions. In Technical Communications of the 26th International Conference on Logic Programming, ICLP 2010, Edinburgh, Scotland, UK, 16-19 Jul. 2010, Hermenegildo, M. V., and Schaub, T., Eds. LIPIcs, vol. 7. Schloss Dagstuhl - Leibniz - Zentrum fuer Informatik, Dagstuhl, Germany, 162-171. · Zbl 1237.68049
[38] Riguzzi, F. and Swift, T.2011. The PITA system: Tabling and answer subsumption for reasoning under uncertainty. Theory and Practice of Logic Programming11, 4-5, 433-449. · Zbl 1218.68169
[39] Sato, T.1995. A statistical learning method for logic programs with distribution semantics. In Logic Programming, Proc. of the 12th International Conference on Logic Programming, Tokyo, Japan, 13-16 Jun. 1995, Sterling, L., Ed. MIT Press, 715-729.
[40] Shearer, R., Motik, B. and Horrocks, I.2008. HermiT: A highly-efficient OWL reasoner. In Proc. of the 5th OWLED Workshop on OWL: Experiences and Directions, Collocated with the 7th International Semantic Web Conference (ISWC-2008), Karlsruhe, Germany, 26-27 Oct. 2008, Dolbear, C., Ruttenberg, A., and Sattler, U., Eds. CEUR-WS, vol. 432. CEUR-WS.org.
[41] Sirin, E., Parsia, B., Cuenca-Grau, B., Kalyanpur, A., and Katz, Y.2007. Pellet: A practical OWL-DL reasoner. Journal of Web Semantics5, 2, 51-53.
[42] Steigmiller, A., Liebig, T. and Glimm, B.2014. Konclude: System description. Journal of Web Semantics27, 78-85. · Zbl 1423.68486
[43] Tsarkov, D. and Horrocks, I.2006. FaCT++ description logic reasoner: System description. In Proc. of the Automated Reasoning, 3rd International Joint Conference, IJCAR 2006, Seattle, WA, USA, 17-20 Aug. 2006, Furbach, U., and Shankar, N., Eds. LNCS, vol. 4130. Springer, 292-297.
[44] Zese, R.2017. Probabilistic Semantic Web: Reasoning and Learning. Studies on the Semantic Web, vol. 28. IOS Press, Amsterdam.
[45] Zese, R., Bellodi, E., Riguzzi, F., Cota, G. and Lamma, E.2018. Tableau reasoning for description logics and its extension to probabilities. Annals of Mathematics and Artificial Intelligence82, 1-3, 101-130. · Zbl 1398.68506
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.