Stage-oe-small.jpg

Article3065

Aus Aifbportal
Version vom 17. Januar 2012, 16:50 Uhr von Sru (Diskussion | Beiträge) (Die Seite wurde neu angelegt: „{{Publikation Erster Autor |ErsterAutorNachname=Krötzsch |ErsterAutorVorname=Markus }} {{Publikation Author |Rank=2 |Author=Sebastian Rudolph }} {{Publikation Au…“)
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)
Wechseln zu:Navigation, Suche


Complexities of Horn Description Logics


Complexities of Horn Description Logics



Veröffentlicht: 2012

Journal: ACM Transactions on Computational Logic



Bemerkung: to appear

Referierte Veröffentlichung

BibTeX




Kurzfassung
Description Logics (DLs) have become a prominent paradigm for representing knowledge in a variety of application areas. An important factor for this practical success is the ability of DLs to achieve a favourable balance between the expressivity of the logic and the performance of reasoning. Horn description logics (Horn DLs) have attracted attention since their (worst-case) data complexities are in general lower than their overall (i.e., combined) complexities, which makes them attractive for reasoning with large sets of instance data (ABoxes). However, the natural question whether Horn DLs also provide advantages for schema (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 studied herein turns out to be the same as for their non-Horn counterparts, we identify subboolean DLs where Hornness simplifies reasoning. We also provide convenient normal forms for defining Horn DLs syntactically.


Projekt

ExpresST



Forschungsgruppe

Wissensmanagement


Forschungsgebiet

Semantische Technologien, Beschreibungslogik, Komplexitätstheorie