LATPub712: Unterschied zwischen den Versionen
Aus International Center for Computational Logic
Marcel Lippmann (Diskussion | Beiträge) KKeine Bearbeitungszusammenfassung |
Marcel Lippmann (Diskussion | Beiträge) KKeine Bearbeitungszusammenfassung |
||
| (2 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt) | |||
| Zeile 5: | Zeile 5: | ||
}} | }} | ||
{{Techreport | {{Techreport | ||
|Title=Unification in the Description Logic | |Title=Unification in the Description Logic EL Without the Top Concept | ||
|Year=2011 | |Year=2011 | ||
|Month= | |Month= | ||
| Zeile 15: | Zeile 15: | ||
}} | }} | ||
{{Publikation Details | {{Publikation Details | ||
|Abstract=Unification in Description Logics has been proposed as a novel inference | |Abstract=Unification in Description Logics has been proposed as a novel inference service that can, for example, be used to detect redundancies in ontologies. The inexpressive Description Logic EL is of particular interest in this context since, on the one hand, several large biomedical ontologies are defined using EL. On the other hand, unification in EL has recently been shown to be NP-complete, and thus of considerably lower complexity than unification in other DLs of similarly restricted expressive power. | ||
service that can, for example, be used to detect redundancies | However, EL allows the use of the top concept, which represents the whole interpretation domain, whereas the large medical ontology SNOMED CT makes no use of this feature. Surprisingly, removing the top concept from EL makes the unification problem considerably harder. More precisely, we will show in this paper that unification in EL without the top concept is PSpace-complete. | ||
in ontologies. The inexpressive Description Logic EL is of particular | |||
interest in this context since, on the one hand, several large biomedical | |||
ontologies are defined using EL. On the other hand, unification | |||
in EL has recently been shown to be NP-complete, and thus | |||
of considerably lower complexity than unification in other DLs of similarly | |||
restricted expressive power. | |||
However, EL allows the use of the top concept, | |||
which represents the whole interpretation domain, whereas the large medical | |||
ontology SNOMED CT makes no use of this feature. Surprisingly, removing | |||
the top concept from EL makes the unification problem considerably | |||
harder. More precisely, we will show in this paper that unification | |||
in EL without the top concept is PSpace-complete. | |||
|ISBN= | |ISBN= | ||
|ISSN= | |ISSN= | ||
| Zeile 49: | Zeile 35: | ||
year = {2011}, | year = {2011}, | ||
} | } | ||
}} | }} | ||
Aktuelle Version vom 25. März 2015, 16:34 Uhr
Unification in the Description Logic EL Without the Top Concept
Franz BaaderFranz Baader, Nguyen Thanh BinhNguyen Thanh Binh, Stefan BorgwardtStefan Borgwardt, Barbara MorawskaBarbara Morawska
Franz Baader, Nguyen Thanh Binh, Stefan Borgwardt, Barbara Morawska
Unification in the Description Logic EL Without the Top Concept
Technical Report, Chair of Automata Theory, Institute of Theoretical Computer Science, Technische Universität Dresden, volume 11-01, 2011. LTCS-Report
Unification in the Description Logic EL Without the Top Concept
Technical Report, Chair of Automata Theory, Institute of Theoretical Computer Science, Technische Universität Dresden, volume 11-01, 2011. LTCS-Report
- KurzfassungAbstract
Unification in Description Logics has been proposed as a novel inference service that can, for example, be used to detect redundancies in ontologies. The inexpressive Description Logic EL is of particular interest in this context since, on the one hand, several large biomedical ontologies are defined using EL. On the other hand, unification in EL has recently been shown to be NP-complete, and thus of considerably lower complexity than unification in other DLs of similarly restricted expressive power. However, EL allows the use of the top concept, which represents the whole interpretation domain, whereas the large medical ontology SNOMED CT makes no use of this feature. Surprisingly, removing the top concept from EL makes the unification problem considerably harder. More precisely, we will show in this paper that unification in EL without the top concept is PSpace-complete. - Bemerkung: Note: See http://lat.inf.tu-dresden.de/research/reports.html.
- Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory
@techreport{ BBBM-LTCS-11-01,
address = {Dresden, Germany},
author = {Franz {Baader} and Nguyen Thanh {Binh} and Stefan {Borgwardt} and Barbara {Morawska}},
institution = {Chair of Automata Theory, Institute of Theoretical Computer Science, Technische Universit{\"a}t Dresden},
note = {See http://lat.inf.tu-dresden.de/research/reports.html.},
number = {11-01},
title = {Unification in the Description Logic {$\mathcal{EL}$} Without the Top Concept},
type = {LTCS-Report},
year = {2011},
}
