Stage-oe-small.jpg

Techreport1432

Aus Aifbportal
Version vom 7. August 2009, 11:07 Uhr von Nicole Arlt (Diskussion | Beiträge) (Added from ontology)
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)
Wechseln zu:Navigation, Suche


Complexity of Horn Description Logics




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

BibTeX



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