Complexity Boundaries for Horn Description Logics

Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche

Toggle side column
Markus Krötzsch, Sebastian Rudolph, Pascal Hitzler
Complexity Boundaries for Horn Description Logics
Proceedings of the 22nd AAAI Conference on Artficial Intelligence, 452--457, 2007. AAAI Press
  • KurzfassungAbstract
    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.
  • Bemerkung: Note: A significantly improved and extended version of this work is Complexities of Horn Description Logics .
  • Forschungsgruppe:Research Group: Computational LogicWissensbasierte Systeme
  author    = {Markus Kr{\"{o}}tzsch and Sebastian Rudolph and Pascal Hitzler},
  title     = {Complexity Boundaries for Horn Description Logics},
  booktitle = {Proceedings of the 22nd {AAAI} Conference on Artficial
  publisher = {AAAI Press},
  year      = {2007},
  pages     = {452--457}