Complexity Boundaries for Horn Description Logics
Markus Krötzsch, Sebastian Rudolph, Pascal Hitzler
Complexity Boundaries for Horn Description Logics
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.
Published at AAAI2007 (Conference paper)
Download PDF (last update: August 22 2007)
Citation details
- Markus Krötzsch, Sebastian Rudolph, Pascal Hitzler. Complexity Boundaries for Horn Description Logics. In Proceedings of the 22nd AAAI Conference on Artificial Intelligence (AAAI-07), pp. 452–457. AAAI PressProperty "Publisher" has a restricted application area and cannot be used as annotation property by a user. 2007.
author = {Markus Kr{\"o}tzsch and Sebastian Rudolph
and Pascal Hitzler},
title = {Complexity Boundaries for {Horn} Description
Logics},
pages = {452--457},
booktitle = {Proceedings of the 22nd AAAI Conference on
Artificial Intelligence (AAAI'07)},
publisher = {AAAI Press},
year = {2007}
}
Remarks
This paper is superseded by the article Complexities of Horn Description Logics. It is strongly recommended to refer to the latter, which has been thoroughly updated for improving clarity and presentation. It also includes some updated results and pointers to related works.
