ML Anthology

Complexity Boundaries for Horn Description Logics

Markus Krötzsch, Sebastian Rudolph, Pascal Hitzler
AAAI 2007 pp. 452-457
/aaai/2007/krotzsch2007aaai-complexity/

Abstract

Horn description logics (Horn-DLs) have recently started to attract attention due to the fact that their (worst-case) data complexities are in general lower than their overall (i.e. combined) complexities, which makes them attractive for reasoning with large ABoxes. However, the natural question whether Horn-DLs also provide advantages for TBox reasoning has hardly been addressed so far. In this paper, we therefore provide a thorough and comprehensive analysis of the combined complexities of Horn-DLs. While the combined complexity for many Horn-DLs turns out to be the same as for their non-Horn counterparts, we identify subboolean DLs where Hornness simplifies reasoning. Copyright ©2007, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

PDF AAAI Semantic Scholar

Cite

Text

Krötzsch et al. "Complexity Boundaries for Horn Description Logics." AAAI Conference on Artificial Intelligence, 2007.

Markdown

[Krötzsch et al. "Complexity Boundaries for Horn Description Logics." AAAI Conference on Artificial Intelligence, 2007.](https://mlanthology.org/aaai/2007/krotzsch2007aaai-complexity/)

BibTeX

@inproceedings{krotzsch2007aaai-complexity,
  title     = {{Complexity Boundaries for Horn Description Logics}},
  author    = {Krötzsch, Markus and Rudolph, Sebastian and Hitzler, Pascal},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2007},
  pages     = {452-457},
  url       = {https://mlanthology.org/aaai/2007/krotzsch2007aaai-complexity/}
}