On the Complexity of Horn Description Logics

TitleOn the Complexity of Horn Description Logics
Publication TypeConference Paper
Year of Publication2006
AuthorsSebastian Rudolph, Markus Krotzsch, Pascal Hitzler
PublisherSecond Workshop OWL - Experiences and Directions, OWLED2006
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 datacomplexity, 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.

Full Text

Markus Krotzsch, Sebastian Rudolph, Pascal Hitzler, 'On the Complexity of Horn Description Logics,' Proceedings of the Second Workshop OWL - Experiences and Directions, OWLED2006, Athens, Georgia, November 2006.
year: 2006
venue name: Second Workshop OWL - Experiences and Directions, OWLED2006
hasURL: http://knoesis.wright.edu/faculty/pascal/resources/publications/owled-ho...