Complexity Boundaries for Horn Description Logics

Authors

Markus Krotzsch
Sebastian Rudolph
Pascal HitzlerFollow

Document Type

Conference Proceeding

Publication Date

7-1-2007

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.

Comments

Presented at the 22nd AAAI Conference on Artificial Intelligence, Vancouver, BC, July 22-26, 2007.

Repository Citation

Krotzsch, M., Rudolph, S., & Hitzler, P. (2007). Complexity Boundaries for Horn Description Logics. Proceedings of the 22nd AAAI Conference on Artificial Intelligence, 452-457.
https://corescholar.libraries.wright.edu/cse/134