Proceedings

A Practical Automata-Based Technique for Reasoning in Expressive Description Logics

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 798-803.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-140

© 2011 International Joint Conferences on Artificial Intelligence

Abstract

In this work we describe the theoretical foundations and the implementation of a new automata-based technique for reasoning over expressive Description Logics that is worst-case optimal and lends itself to an efficient implementation. In order to show the feasibility of the approach, we have realized a working prototype of a reasoner based upon these techniques. An experimental evaluation of this prototype shows encouraging results.

  1. [Baader and Sattler, 2001] Franz Baader and Ulrike Sattler. An overview of tableau algorithms for description logics. Studia Logica, 69(1):5-40, 2001.
  2. [Baader and Tobies, 2001] Franz Baader and Stephan To- bies. The inverse method implements the automata ap- proach for modal satisfiability. In Proc. of the Int. Joint Conf. on Automated Reasoning (IJCAR 2001), pages 92- 106, 2001.
  3. [Baader et al., 2007] Franz Baader, Diego Calvanese, Deb- orah McGuinness, Daniele Nardi, and Peter F. Patel- Schneider, editors. The Description Logic Handbook: Theory, Implementation and Applications. Cambridge University Press, 2nd edition, 2007.
  4. [Calvanese et al., 2002] Diego Calvanese, Giuseppe De Gi- acomo, and Maurizio Lenzerini. 2ATAs make DLs easy. In Proc. of the 15th Int. Workshop on Description Logic (DL 2002), volume 53 of CEUR, http://ceur-ws. org/, pages 107-118, 2002. Link
  5. [Calvanese et al., 2007] Diego Calvanese, Thomas Eiter, and Magdalena Ortiz. Answering regular path queries in ex- pressive description logics: An automata-theoretic ap- proach. In Proc. of the 22nd AAAI Conf. on Artificial In- telligence (AAAI 2007), pages 391-396, 2007.
  6. [Carbotta, 2010] Domenico Carbotta. A practical automata- based technique for reasoning in expressive description logics. Master's thesis, Fakultät für Informatik, Technis- che Universität Wien, October 2010. Available at http: //www.emcl-study.eu/graduates.html. Link
  7. [Davis et al., 1962] M. Davis, G. Logemann, and D. Love- land. A machine program for theorem proving. Commu- nications of the ACM, 5:394-397, 1962.
  8. [De Giacomo and Lenzerini, 1994] Giuseppe De Giacomo and Maurizio Lenzerini. Boosting the correspondence be- tween description logics and propositional dynamic logics. In Proc. of the 12th Nat. Conf. on Artificial Intelligence (AAAI'94), pages 205-212, 1994. [Eén and Sörensson, 2003] Niklas Eén and Niklas Sörensson. An extensible SAT-solver. In Proc. of the 6th Int. Conf. on Theory and Applications of Satisfia- bility Testing (SAT 2003), volume 2919 of LNCS, pages 502-518. Springer, 2003.
  9. [Gardiner et al., 2006] Tom Gardiner, Ian Horrocks, and Dmitry Tsarkov. Automated benchmarking of descrip- tion logic reasoners. In Proc. of the 19th Int. Workshop on Description Logic (DL 2006), volume 189 of CEUR, http://ceur-ws.org/, 2006. Link
  10. [Hustadt et al., 2008] Ullrich Hustadt, Boris Motik, and Ul- rike Sattler. Deciding expressive description logics in the framework of resolution. Information and Computation, 206(5):579-601, 2008.
  11. [Motik et al., 2009] Boris Motik, Rob Shearer, and Ian Hor- rocks. Hypertableau reasoning for description logics. J. of Artificial Intelligence Research, 36:165-228, 2009.
  12. [Shearer et al., 2008] Rob Shearer, Boris Motik, and Ian Horrocks. HermiT: A highly-efficient OWL reasoner. In Proc. of the 5th Int. Workshop on OWL: Experiences and Directions (OWLED 2008), volume 432 of CEUR, http: //ceur-ws.org/, 2008. Link
  13. [Sirin and Parsia, 2006] Evren Sirin and Bijan Parsia. Pel- let system description. In Proc. of the 19th Int. Workshop on Description Logic (DL 2006), volume 189 of CEUR, http://ceur-ws.org/, 2006. Link
  14. [Tobies, 2001] Stephan Tobies. Complexity Results and Practical Algorithms for Logics in Knowledge Represen- tation. PhD thesis, LuFG Theoretical Computer Science, RWTH-Aachen, Germany, 2001.
  15. [Tsarkov and Horrocks, 2006] Dmitry Tsarkov and Ian Hor- rocks. FaCT++ description logic reasoner: System de- scription. In Proc. of the 3rd Int. Joint Conf. on Automated Reasoning (IJCAR 2006), pages 292-297, 2006.
  16. [Vardi and Wilke, 2007] Moshe Vardi and Thomas Wilke. Automata: From logics to algorithms. In Proc. of the Au- tomata and Logic Workshop (WAL 2007), pages 645-753, December 2007.
  17. [Vardi, 1997] Moshe Y. Vardi. Why is modal logic so ro- bustly decidable. In DIMACS Series in Discrete Math- ematics and Theoretical Computer Science, volume 31, pages 149-184. American Mathematical Society, 1997.
  18. [Vardi, 1998] Moshe Y. Vardi. Reasoning about the past with two-way automata. In Proc. of the 25th Int. Coll. on Au- tomata, Languages and Programming (ICALP'98), vol- ume 1443 of LNCS, pages 628-641. Springer, 1998.
  19. [Voronkov, 2001] Andrei Voronkov. How to optimize proof- search in modal logics: New methods of proving redun- dancy criteria for sequent calculi. ACM Trans. on Compu- tational Logic, 2(2):182-215, 2001.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards