Proceedings

Consequence-Based Reasoning beyond Horn Ontologies

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 1093-1097.

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

© 2011 International Joint Conferences on Artificial Intelligence

Abstract

Consequence-based ontology reasoning procedures have so far been known only for Horn ontology languages. A difficulty in extending such procedures is that non-Horn axioms seem to require reasoning by case, which causes non-determinism in tableau-based procedures. In this paper we present a consequence-based procedure for ALCH that overcomes this difficulty by using rules similar to ordered resolution to deal with disjunctive axioms in a deterministic way; it retains all the favourable attributes of existing consequence-based procedures, such as goal-directed “one pass” classification, optimal worst-case complexity, and “pay-asyou- go” behaviour. Our preliminary empirical evaluation suggests that the procedure scales well to non-Horn ontologies.

  1. [Baader et al., 2005] Franz Baader, Sebastian Brandt, and Carsten Lutz. Pushing the EL envelope. In IJCAI, pages 364-369. Professional Book Center, 2005.
  2. [Baader et al., 2007] Franz Baader, Diego Calvanese, Deb- orah L. McGuinness, Daniele Nardi, and Peter F. Patel- Schneider. The Description Logic Handbook: Theory, Im- plementation, and Applications. Cambridge University Press, 2nd edition, 2007.
  3. [Bachmair and Ganzinger, 2001] Leo Bachmair and Harald Ganzinger. Resolution theorem proving. In Handbook of Aut. Reas., pages 19-99. Elsevier and MIT Press, 2001.
  4. [Cuenca Grau et al., 2008] Bernardo Cuenca Grau, Ian Hor- rocks, Boris Motik, Bijan Parsia, Peter F. Patel-Schneider, and Ulrike Sattler. OWL 2: The next step for OWL. J. Web Sem., 6(4):309-322, 2008.
  5. [de Nivelle et al., 2000] Hans de Nivelle, Renate A. Schmidt, and Ulrich Hustadt. Resolution-based methods for modal logics. Logic J. IGPL, 8(3), 2000.
  6. [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.
  7. [Kazakov, 2009] Yevgeny Kazakov. Consequence-driven reasoning for Horn SHIQ ontologies. In IJCAI, pages 2040-2045, 2009. IJCAI
  8. [Ortiz et al., 2010] Magdalena Ortiz, Sebastian Rudolph, and Mantas Simkus. Worst-case optimal reasoning for the Horn-DL fragments of OWL 1 and 2. In KR, pages 269- 279. AAAI Press, 2010.
  9. [Simančík et al., 2011] František Simančík, Yevgeny Kaza- kov, and Ian Horrocks. Consequence-based reasoning be- yond Horn ontologies. Technical report, University of Ox- ford, 2011.
  10. [Suntisrivaraporn et al., 2007] Boontawee Suntisrivaraporn, Franz Baader, Stefan Schulz, and Kent A. Spackman. Re- placing SEP-triplets in SNOMED CT using tractable de- scription logic operators. In AIME, volume 4594 of LNCS, pages 287-291. Springer, 2007.
  11. [Suntisrivaraporn, 2009] Boontawee Suntisrivaraporn. Polynomial-Time Reasoning Support for Design and Maintenance of Large-Scale Biomedical Ontologies. PhD thesis, Fakultät Informatik, TU Dresden, 2009.

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

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