Article3065: Unterschied zwischen den Versionen
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…“) |
Sru (Diskussion | Beiträge) |
||
| Zeile 19: | Zeile 19: | ||
}} | }} | ||
{{Publikation Details | {{Publikation Details | ||
| − | |Abstract=Description Logics (DLs) have become a prominent paradigm for representing knowledge in a variety of application areas | + | |Abstract=Description Logics (DLs) have become a prominent paradigm for representing knowledge in a variety of application areas, partly due to their ability to achieve a favourable balance between expressivity of the logic and performance of reasoning. Horn description logics are obtained, roughly speaking, by disallowing all forms of disjunctions. They have attracted attention since their (worst-case) data complexities are in general lower than for their non-Horn counterparts, which makes them attractive for reasoning with large sets of instance data (ABoxes). It is therefore natural to ask whether Horn DLs also provide advantages for schema (TBox) reasoning, i.e., whether they also feature lower combined complexities. This paper settles this question for a variety of Horn DLs. An example of a tractable Horn logic is the DL underlying the ontology language OWL RL, which we characterise as the Horn fragment of the description logic SROIQ without existential quantifiers. If existential quantifiers are allowed, however, many Horn DLs become intractable. We find that Horn-ALC already has the same worst-case complexity as ALC, i.e., ExpTime, but we also identify various DLs for which reasoning is PSpace-complete. As a side effect, we derive simplified syntactic definitions of Horn DLs, for which we exploit suitable normal form transformations. |
| + | |Download=KRH12-HornDLs.pdf, | ||
|Projekt=ExpresST | |Projekt=ExpresST | ||
|Forschungsgruppe=Wissensmanagement | |Forschungsgruppe=Wissensmanagement | ||
Version vom 23. Januar 2012, 00:05 Uhr
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
Kurzfassung
Description Logics (DLs) have become a prominent paradigm for representing knowledge in a variety of application areas, partly due to their ability to achieve a favourable balance between expressivity of the logic and performance of reasoning. Horn description logics are obtained, roughly speaking, by disallowing all forms of disjunctions. They have attracted attention since their (worst-case) data complexities are in general lower than for their non-Horn counterparts, which makes them attractive for reasoning with large sets of instance data (ABoxes). It is therefore natural to ask whether Horn DLs also provide advantages for schema (TBox) reasoning, i.e., whether they also feature lower combined complexities. This paper settles this question for a variety of Horn DLs. An example of a tractable Horn logic is the DL underlying the ontology language OWL RL, which we characterise as the Horn fragment of the description logic SROIQ without existential quantifiers. If existential quantifiers are allowed, however, many Horn DLs become intractable. We find that Horn-ALC already has the same worst-case complexity as ALC, i.e., ExpTime, but we also identify various DLs for which reasoning is PSpace-complete. As a side effect, we derive simplified syntactic definitions of Horn DLs, for which we exploit suitable normal form transformations.
Download: Media:KRH12-HornDLs.pdf
Semantische Technologien, Beschreibungslogik, Komplexitätstheorie