Techreport1432: Unterschied zwischen den Versionen

Version vom 8. September 2009, 10:06 Uhr

Complexity of Horn Description Logics

Markus Krötzsch, Sebastian Rudolph, Pascal Hitzler

Published: 2007 Februar
Institution: Instistute AIFB, Universität Karlsruhe
Archivierungsnummer:1432

Kurzfassung
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.

Download: Media:2007_1432_Krötzsch_Complexity_of_H_1.pdf

Projekt

ReaSem

Forschungsgebiet

Komplexitätstheorie, Logik

@@ Zeile 1: / Zeile 1: @@
-{{Publikation Author
+{{Publikation Erster Autor
-|Rank=3
+|ErsterAutorNachname=Krötzsch
-|Author=Pascal Hitzler
+|ErsterAutorVorname=Markus
 }}
 {{Publikation Author
-|Rank=1
+|Rank=2
-|Author=Markus Krötzsch
+|Author=Sebastian Rudolph
 }}
 {{Publikation Author
-|Rank=2
+|Rank=3
-|Author=Sebastian Rudolph
+|Author=Pascal Hitzler
 }}
 {{Techreport
@@ Zeile 37: / Zeile 37: @@
 }}
 {{Forschungsgebiet Auswahl
-|Forschungsgebiet=Komplexitätstheorie
+|Forschungsgebiet=Logik
 }}
 {{Forschungsgebiet Auswahl
-|Forschungsgebiet=Logik
+|Forschungsgebiet=Komplexitätstheorie
 }}