On the Complexity of Horn Description Logics
Markus Krötzsch, Sebastian Rudolph, Pascal Hitzler
On the Complexity of Horn Description Logics
Abstract. Horn-SHIQ has been identified as a fragment of the description logic SHIQ for which inferencing is in PTime with respect to the size of the ABox. This enables reasoning with larger ABoxes in situations where the TBox is static, and represents one approach towards tractable description logic reasoning. In this paper, we show that reasoning in Horn-SHIQ, in spite of its low data-complexity, is ExpTime-hard with respect to the overall size of the knowledge base. While this result is not unexpected, the proof is not a mere modification of existing reductions since it has to account for the restrictions of Hornness. We establish the result for Horn-FLE, showing that Hornness does not simplify TBox reasoning even for very restricted description logics. Moreover, we derive a context-free grammar that defines Horn-SHIQ in a simpler and more intuitive way than existing characterisations.
Published at OWLED2006 (Workshop paper)
Download PDF (last update: November 1 2006)
Citation details
- Markus Krötzsch, Sebastian Rudolph, Pascal Hitzler. On the Complexity of Horn Description Logics. In Bernardo Cuenca Grau, Pascal Hitzler, Conor Shankey, Evan Wallace, eds.: Proceedings of the 2nd Workshop on OWL: Experiences and Directions (OWLED-06). CEUR Workshop ProceedingsProperty "Publisher" has a restricted application area and cannot be used as annotation property by a user. 2006.
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.
