Nothing Special   »   [go: up one dir, main page]
Skip to main content
SpringerLink
Log in

Tableau reasoning for description logics and its extension to probabilities

  • Published:
Annals of Mathematics and Artificial Intelligence Aims and scope Submit manuscript

Abstract

The increasing popularity of the Semantic Web drove to a widespread adoption of Description Logics (DLs) for modeling real world domains. To help the diffusion of DLs, a large number of reasoning algorithms have been developed. Usually these algorithms are implemented in procedural languages such as Java or C++. Most of the reasoners exploit the tableau algorithm which features non-determinism, that is not easily handled by those languages. Prolog directly manages non-determinism, thus is a good candidate for dealing with the tableau’s non-deterministic expansion rules. We present TRILL, for “Tableau Reasoner for descrIption Logics in proLog”, that implements a tableau algorithm and is able to return explanations for queries and their corresponding probability, and TRILLP, for “TRILL powered by Pinpointing formulas”, which is able to compute a Boolean formula representing the set of explanations for a query. Reasoning on real world domains also requires the capability of managing probabilistic and uncertain information. We show how TRILL and TRILLP can be used to compute the probability of queries to knowledge bases following DISPONTE semantics. Experiments comparing these with other systems show the feasibility of the approach.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Baader, F., Calvanese, D., McGuinness, D.L., Nardi, D., Patel-Schneider, P.F. (eds.): The Description Logic Handbook: Theory, Implementation, and Applications. Cambridge University Press (2003)

  2. Baader, F., Horrocks, I., Sattler, U.: Description logics. In: Handbook of Knowledge Representation, chap. 3, pp. 135–179. Elsevier (2008)

  3. Baader, F., Peñaloza, R.: Automata-based axiom pinpointing. J. Autom. Reas. 45(2), 91–129 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  4. Baader, F., Peñaloza, R.: Axiom pinpointing in general tableaux. J. Log. Comput. 20(1), 5–34 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  5. Bacchus, F.: Representing and Reasoning with Probabilistic Knowledge - a Logical Approach to Probabilities. MIT Press, Cambridge (1990)

    Google Scholar 

  6. Beckert, B., Posegga, J.: leantap: Lean tableau-based deduction. J. Autom. Reas. 15(3), 339–358 (1995)

    Article  MATH  Google Scholar 

  7. Bellodi, E., Lamma, E., Riguzzi, F., Albani, S.: A distribution semantics for probabilistic ontologies. In: Bobillo, F., et al. (eds.) URSW 2011, CEUR Workshop Proceedings, vol. 778. Sun SITE Central Europe (2011)

  8. Bellodi, E., Riguzzi, F.: Learning the structure of probabilistic logic programs. In: Muggleton, S.H., Tamaddoni-Nezhad, A., Lisi, F.A. (eds.) ILP 2011, LNCS, vol. 7207, pp. 61–75. Springer (2012). doi:10.1007/978-3-642-31951-8_10

  9. Bellodi, E., Riguzzi, F.: Expectation Maximization over binary decision diagrams for probabilistic logic programs. Intel. Data Anal. 17(2), 343–363 (2013)

    Google Scholar 

  10. Bruynooghe, M., Mantadelis, T., Kimmig, A., Gutmann, B., Vennekens, J., Janssens, G., Raedt, L.D.: Problog technology for inference in a probabilistic first order logic. In: ECAI 2010 - 19th European Conference on Artificial Intelligence, Lisbon, Portugal, August 16-20, 2010, Proceedings, Frontiers in Artificial Intelligence and Applications, vol. 215, pp. 719–724. IOS Press (2010)

  11. Calì, A., Lukasiewicz, T., Predoiu, L., Stuckenschmidt, H.: Tightly coupled probabilistic description logic programs for the semantic web. In: Journal on Data Semantics XII, pp. 95–130. Springer (2009)

  12. Carvalho, R.N., Laskey, K.B., Costa, P.C.G.: PR-OWL 2.0 - bridging the gap to OWL semantics. In: Bobillo, F., et al. (eds.) URSW 2010, CEUR Workshop Proceedings, vol. 654. Sun SITE Central Europe (2010)

  13. Ceylan, İ.İ., Mendez, J., Peṅaloza, R.: The bayesian ontology reasoner is born!. In: Dumontier, M., Glimm, B., Gonċalves, R.S., Horridge, M., Jimėnez-Ruiz, E., Matentzoglu, N., Parsia, B., Stamou, G.B., Stoilos, G. (eds.) Informal Proceedings of the 4th International Workshop on OWL Reasoner Evaluation (ORE-2015) co-located with the 28th International Workshop on Description Logics (DL 2015), CEUR Workshop Proceedings, vol. 1387, pp. 8–14. CEUR-WS.org (2015)

  14. Ceylan, İ.İ., Peṅaloza, R.: Bayesian description logics. In: Bienvenu, M., Ortiz, M., Rosati, R., Simkus, M. (eds.) Informal Proceedings of the 27th International Workshop on Description Logics, Vienna, Austria, July 17-20, 2014., CEUR Workshop Proceedings, vol. 1193, pp. 447–458. CEUR-WS.org (2014)

  15. Ceylan, İ.İ., Peṅaloza, R.: Probabilistic query answering in the bayesian description logic BEl. In: Beierle, C., Dekhtyar, A. (eds.) Proceedings of Scalable Uncertainty Management - 9th International Conference, SUM 2015, Lecture Notes in Computer Science, vol. 9310, pp. 21–35. Springer (2015)

  16. Codish, M., Lagoon, V., Stuckey, P.J.: Logic programming with satisfiability. TPLP 8(1), 121–128 (2008)

    MATH  Google Scholar 

  17. da Costa, P.C.G., Laskey, K.B., Laskey, K.J.: PR-OWL: A bayesian ontology language for the semantic web. In: da Costa, P.C.G., d’Amato, C., Fanizzi, N., Laskey, K.B., Laskey, K.J., Lukasiewicz, T., Nickles, M., Pool, M. (eds.) Uncertainty Reasoning for the Semantic Web I, ISWC International Workshops, URSW 2005-2007, Revised Selected and Invited Papers, Lecture Notes in Computer Science, vol. 5327, pp. 88–107. Springer (2008)

  18. d’Amato, C., Fanizzi, N., Lukasiewicz, T.: Tractable reasoning with bayesian description logics. In: Greco, S., Lukasiewicz, T. (eds.) Scalable Uncertainty Management, Second International Conference, SUM 2008, Naples, Italy, October 1-3, 2008. Proceedings, Lecture Notes in Computer Science, vol. 5291, pp. 146–159. Springer (2008)

  19. Demir, E., Cary, M.P., Paley, S., Fukuda, K., Lemer, C., Vastrik, I., Wu, G., D’Eustachio, P., Schaefer, C., Luciano, J., et al.: The biopax community standard for pathway data sharing. Nat. Biotechnol. 28(9), 935–942 (2010)

    Article  Google Scholar 

  20. Ding, Z., Peng, Y.: A probabilistic extension to ontology language OWL. In: 37th Hawaii International Conference on System Sciences (HICSS-37 2004), CD-ROM / Abstracts Proceedings, 5-8 January 2004. IEEE Computer Society, USA (2004)

    Google Scholar 

  21. Eėn, N., Sȯrensson, N.: An extensible sat-solver. In: Giunchiglia, E., Tacchella, A. (eds.) Theory and Applications of Satisfiability Testing, 6th International Conference, SAT 2003. Santa Margherita Ligure, Italy, May 5-8, 2003 Selected Revised Papers, Lecture Notes in Computer Science, vol. 2919, pp. 502–518. Springer (2003)

  22. Faizi, I.: A Description Logic Prover in Prolog, Bachelor’s thesis. Informatics Mathematical Modelling, Technical University of Denmark (2011)

  23. Gavanelli, M., Lamma, E., Riguzzi, F., Bellodi, E., Zese, R., Cota, G.: An abductive framework for datalog ± ontologies. In: Vos, M.D., Eiter, T., Lierler, Y., Toni, F. (eds.) Proceedings of the Technical Communications of the 31st International Conference on Logic Programming (ICLP 2015), Cork, Ireland, August 31 - September 4, 2015., CEUR Workshop Proceedings, vol. 1433. CEUR-WS.org (2015)

  24. Gavanelli, M., Lamma, E., Riguzzi, F., Bellodi, E., Zese, R., Cota, G.: Abductive logic programming for datalog +/- ontologies. In: Ancona, D., Maratea, M., Mascardi, V. (eds.) Proceedings of the 30th Italian Conference on Computational Logic, Genova, Italy, July 1-3, 2015., CEUR Workshop Proceedings, vol. 1459, pp. 128–143. CEUR-WS.org (2015)

  25. Giugno, R., Lukasiewicz, T.: P-SHOQ(D): A probabilistic extension of SHOQ(D) for probabilistic ontologies in the semantic web. In: Flesca, S., Greco, S., Leone, N., Ianni, G. (eds.) Logics in Artificial Intelligence, European Conference, JELIA 2002, Cosenza, Italy, September, 23-26, Proceedings, Lecture Notes in Computer Science, vol. 2424, pp. 86–97. Springer (2002)

  26. Gottlob, G., Lukasiewicz, T., Simari, G.I.: Conjunctive query answering in probabilistic datalog+/- ontologies. In: Rudolph, S., Gutierrez, C. (eds.) Web Reasoning and Rule Systems - 5th International Conference, RR 2011, Galway, Ireland, August 29-30, 2011. Proceedings, Lecture Notes in Computer Science, vol. 6902, pp. 77–92. Springer (2011)

  27. Halaschek-Wiener, C., Kalyanpur, A., Parsia, B.: Extending Tableau Tracing for ABox Updates. University of Maryland, Tech. rep. (2006)

    Google Scholar 

  28. Halpern, J.Y.: An analysis of first-order logics of probability. Artif. Intell. 46(3), 311–350 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  29. Heinsohn, J.: Probabilistic description logics. In: de Mántaras, R.L., Poole, D. (eds.) Conference on Uncertainty in Artificial Intelligence, pp. 311–318, Morgan Kaufmann (1994)

  30. Herchenröder, T.: Lightweight Semantic Web Oriented Reasoning in Prolog: Tableaux Inference for Description Logics. Master’s thesis, School of Informatics, University of Edinburgh (2006)

  31. Hitzler, P., Krötzsch, M., Rudolph, S.: Foundations of Semantic Web Technologies. CRC Press (2009)

  32. Hustadt, U., Motik, B., Sattler, U.: Deciding expressive description logics in the framework of resolution. Inf. Comput. 206(5), 579–601 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  33. Jaeger, M.: Probabilistic reasoning in terminological logics. In: Doyle, J., Sandewall, E., Torasso, P. (eds.) Proceedings of the 4th International Conference on Principles of Knowledge Representation and Reasoning (KR’94), pp. 305–316. Morgan Kaufmann, Bonn (1994)

    Chapter  Google Scholar 

  34. Jung, J.C., Lutz, C.: Ontology-based access to probabilistic data with OWL QL. In: Cudré-Mauroux, P., Heflin, J., Sirin, E., Tudorache, T., Euzenat, J., Hauswirth, M., Parreira, J.X., Hendler, J., Schreiber, G., Bernstein, A., Blomqvist, E. (eds.) The Semantic Web - ISWC 2012 - 11th International Semantic Web Conference, Boston, MA, USA, November 11-15, 2012, Proceedings, Part I, Lecture Notes in Computer Science (LNCS), vol. 7649, pp. 182–197. Springer, Berlin (2012)

    Google Scholar 

  35. Kalyanpur, A.: Debugging and Repair of OWL Ontologies. The Graduate School of the University of Maryland, Ph.D. thesis (2006)

    Google Scholar 

  36. Kalyanpur, A., Parsia, B., Horridge, M., Sirin, E., et al.: Finding all justifications of OWL DL entailments. In: Aberer, K. (ed.) ISWC/ASWC 2007, LNCS, vol. 4825, pp. 267–280. Springer (2007)

  37. Klinov, P.: Pronto: A non-monotonic probabilistic description logic reasoner. In: Bechhofer, S., Hauswirth, M., Hoffmann, J., Koubarakis, M. (eds.) The Semantic Web: Research and Applications, 5th European Semantic Web Conference, ESWC 2008, Tenerife, Canary Islands, Spain, June 1-5, 2008, Proceedings, Lecture Notes in Computer Science, vol. 5021, pp. 822–826. Springer (2008)

  38. Klinov, P., Parsia, B.: Optimization and evaluation of reasoning in probabilistic description logic: Towards a systematic approach. In: Sheth, A.P., Staab, S., Dean, M., Paolucci, M., Maynard, D., Finin, T.W., Thirunarayan, K. (eds.) The Semantic Web - ISWC 2008, 7th International Semantic Web Conference, ISWC 2008, Karlsruhe, Germany, October 26-30, 2008. Proceedings, Lecture Notes in Computer Science, vol. 5318, pp. 213–228. Springer (2008)

  39. Koller, D., Levy, A.Y., Pfeffer, A.: P-CLASSIC: A tractable probablistic description logic. In: Kuipers, B., Webber, B.L. (eds.) Proceedings of the Fourteenth National Conference on Artificial Intelligence and Ninth Innovative Applications of Artificial Intelligence Conference, AAAI 97, IAAI 97, July 27-31, 1997, Providence, Rhode Island, pp. 390–397. AAAI Press / The MIT Press (1997)

  40. Lager, T., Wielemaker, J.: Pengines: Web logic programming made easy. TPLP 14(4–5), 539–552 (2014)

    MATH  Google Scholar 

  41. Laskey, K.B., da Costa, P.C.G.: Of starships and klingons: Bayesian logic for the 23rd century. In: UAI ’05, Proceedings of the 21st Conference in Uncertainty in Artificial Intelligence, Edinburgh, Scotland, July 26-29, 2005, pp. 346–353. AUAI Press (2005)

  42. Lukácsy, G., Szeredi, P.: Efficient description logic reasoning in prolog: The dlog system. TPLP 9(3), 343–414 (2009)

    MathSciNet  MATH  Google Scholar 

  43. Lukasiewicz, T.: Probabilistic default reasoning with conditional constraints. Ann. Math. Artif. Int. 34(1–3), 35–88 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  44. Lukasiewicz, T.: Expressive probabilistic description logics. Artif. Int. 172(6–7), 852–883 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  45. Luna, J.E.O., Revoredo, K., Cozman, F.G.: Learning probabilistic Description Logics: A framework and algorithms. In: Batyrshin, I.Z., Sidorov, G. (eds.) Advances in Artificial Intelligence - 10th Mexican International Conference on Artificial Intelligence, MICAI 2011, Puebla, Mexico, November 26 - December 4, 2011, Proceedings, Part I, Lecture Notes in Computer Science, vol. 7094, pp. 28–39. Springer, Berlin (2011)

    Google Scholar 

  46. Lutz, C., Schröder, L.: Probabilistic description logics for subjective uncertainty. In: Lin, F., Sattler, U., Truszczynski, M. (eds.) Principles of Knowledge Representation and Reasoning: Proceedings of the Twelfth International Conference, KR 2010, Toronto, Ontario, Canada, May 9-13, 2010, pp. 393–403. AAAI Press, Menlo Park (2010)

    Google Scholar 

  47. Meissner, A.: An automated deduction system for description logic with alcn language. Studia z Automatyki i Informatyki 28–29, 91–110 (2004)

    Google Scholar 

  48. Nagypȧl, G., Deswarte, R., Oosthoek, J.: Applying the semantic web: The VICODI experience in creating visual contextualization for history. Literary Linguis. Comput. 20(3), 327–349 (2005)

    Google Scholar 

  49. Nilsson, N.J.: Probabilistic logic. Artif. Intell. 28(1), 71–87 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  50. Patel-Schneider, PF., Horrocks, I., Bechhofer, S.: Tutorial on OWL (2003)

  51. Poole, D.: The Independent Choice Logic for modelling multiple agents under uncertainty. Artif. Intell. 94(1–2), 7–56 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  52. Poole, D.: Abducing through negation as failure: stable models within the independent choice logic. J. Log. Program 44(1–3), 5–35 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  53. Reiter, R.: A theory of diagnosis from first principles. Artif. Intell. 32(1), 57–95 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  54. Ricca, F., Gallucci, L., Schindlauer, R., Dell’Armi, T., Grasso, G., Leone, N.: OntoDLV: An ASP-based system for enterprise ontologies. J. Log. Comput. 19 (4), 643–670 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  55. Riguzzi, F., Bellodi, E., Lamma, E., Zese, R.: Epistemic and statistical probabilistic ontologies. In: Bobillo, F., et al. (eds.) URSW 2012, CEUR Workshop Proceedings, vol. 900, pp. 3–14. Sun SITE Central Europe (2012)

  56. Riguzzi, F., Bellodi, E., Lamma, E., Zese, R.: BUNDLE: A reasoner for probabilistic ontologies. In: Faber, W., Lembo, D. (eds.) Web Reasoning and Rule Systems - 7th International Conference, RR 2013, Mannheim, Germany, July 27-29, 2013. Proceedings, Lecture Notes in Computer Science, vol. 7994, pp. 183–197. Springer (2013)

  57. Riguzzi, F., Bellodi, E., Lamma, E., Zese, R.: Parameter learning for probabilistic ontologies. In: Faber, W., Lembo, D. (eds.) Web Reasoning and Rule Systems - 7th International Conference, RR 2013, Mannheim, Germany, July 27-29, 2013. Proceedings, Lecture Notes in Computer Science, vol. 7994, pp. 265–270. Springer (2013)

  58. Riguzzi, F., Bellodi, E., Lamma, E., Zese, R.: Probabilistic description logics under the distribution semantics. Semantic Web - Interoperab. Usabil. Appl. 6 (5), 447–501 (2015). doi:10.3233/SW-140154

    MATH  Google Scholar 

  59. Riguzzi, F., Bellodi, E., Lamma, E., Zese, R.: Reasoning with probabilistic ontologies. In: Yang, Q., Wooldridge, M. (eds.) IJCAI 2015, pp. 4310–4316. AAAI Press (2015)

  60. Riguzzi, F., Bellodi, E., Lamma, E., Zese, R., Cota, G.: Learning probabilistic description logics. In: URSW III, LNCS, vol. 8816, pp. 63–78. Springer (2014)

  61. Sato, T.: A statistical learning method for logic programs with distribution semantics. In: ICLP 1995, pp. 715–729. MIT Press (1995)

  62. Schlobach, S., Cornet, R.: Non-standard reasoning services for the debugging of description logic terminologies. In: Gottlob, G., Walsh, T. (eds.) IJCAI 2003, pp. 355–362. Morgan Kaufmann (2003)

  63. Sirin, E., Parsia, B., Cuenca-Grau, B., Kalyanpur, A., Katz, Y.: Pellet: A practical OWL-DL reasoner. J. Web Sem. 5(2), 51–53 (2007)

    Article  Google Scholar 

  64. Vassiliadis, V., Wielemaker, J., Mungall, C.: Processing OWL2 ontologies using thea: An application of logic programming. In: OWLED 2009, CEUR Workshop Proceedings, vol. 529. CEUR-WS.org (2009)

Download references

Author information

Authors and Affiliations

  1. Dipartimento di Ingegneria, University of Ferrara, Via Saragat 1, 44122, Ferrara, Italy

    Riccardo Zese, Elena Bellodi, Giuseppe Cota & Evelina Lamma

  2. Dipartimento di Matematica e Informatica, University of Ferrara, Via Saragat 1, 44122, Ferrara, Italy

    Fabrizio Riguzzi

Authors
  1. Riccardo Zese
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Elena Bellodi
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Fabrizio Riguzzi
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Giuseppe Cota
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Evelina Lamma
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Riccardo Zese.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Zese, R., Bellodi, E., Riguzzi, F. et al. Tableau reasoning for description logics and its extension to probabilities. Ann Math Artif Intell 82, 101–130 (2018). https://doi.org/10.1007/s10472-016-9529-3

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10472-016-9529-3

Keywords

Mathematics Subject Classifications (2010)

Search

Navigation