KIT | KIT-Bibliothek | Impressum | Datenschutz

Complexity of Horn Description Logics

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

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
Jahr 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