KIT | KIT-Bibliothek | Impressum | Datenschutz

Complexity of Horn Description Logics

Krötzsch, Markus; Rudolph, Sebastian; Hitzler, Pascal

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.

Open Access Logo


Zugehörige Institution(en) am KIT Institut für Angewandte Informatik und Formale Beschreibungsverfahren (AIFB)
Publikationstyp Forschungsbericht/Preprint
Publikationsjahr 2007
Sprache Englisch
Identifikator KITopen-ID: 1000091460
Verlag Universität Karlsruhe, Karlsruhe
Umfang 26 S.
Externe Relationen Abstract/Volltext
Relationen in KITopen
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page