LATPub738: Unterschied zwischen den Versionen
Aus International Center for Computational Logic
Marcel Lippmann (Diskussion | Beiträge) KKeine Bearbeitungszusammenfassung |
Marcel Lippmann (Diskussion | Beiträge) KKeine Bearbeitungszusammenfassung |
||
| Zeile 15: | Zeile 15: | ||
}} | }} | ||
{{Publikation Details | {{Publikation Details | ||
|Abstract=Unification in Description Logics has been introduced as a means to detect | |Abstract=Unification in Description Logics has been introduced as a means to detect redundancies in ontologies. We try to extend the known decidability results for unification in the Description Logic EL to disunification since negative constraints on unifiers can be used to avoid unwanted unifiers. While decidability of the solvability of general EL-disunification problems remains an open problem, we obtain NP-completeness results for two interesting special cases: dismatching problems, where one side of each negative constraint must be ground, and local solvability of disunification problems, where we restrict the attention to solutions that are built from so-called atoms occurring in the input problem. More precisely, we first show that dismatching can be reduced to local disunification, and then provide two complementary NP-algorithms for finding local solutions of (general) disunification problems. | ||
redundancies in ontologies. We try to extend the known decidability results for | |||
unification in the Description Logic EL to disunification since negative | |||
constraints on unifiers can be used to avoid unwanted unifiers. While | |||
decidability of the solvability of general EL-disunification problems remains | |||
an open problem, we obtain NP-completeness results for two interesting special | |||
cases: dismatching problems, where one side of each negative constraint must be | |||
ground, and local solvability of disunification problems, where we restrict the | |||
attention to solutions that are built from so-called atoms occurring in the | |||
input problem. More precisely, we first show that dismatching can be reduced to | |||
local disunification, and then provide two complementary NP-algorithms for | |||
finding local solutions of (general) disunification problems. | |||
|ISBN= | |ISBN= | ||
|ISSN= | |ISSN= | ||
| Zeile 46: | Zeile 34: | ||
year = {2015}, | year = {2015}, | ||
} | } | ||
}} | }} | ||
Version vom 23. März 2015, 12:24 Uhr
Dismatching and Local Disunification in EL
Franz BaaderFranz Baader, Stefan BorgwardtStefan Borgwardt, Barbara MorawskaBarbara Morawska
Franz Baader, Stefan Borgwardt, Barbara Morawska
Dismatching and Local Disunification in EL
Technical Report, Chair for Automata Theory, Institute for Theoretical Computer Science, Technische Universität Dresden, volume 15-03, 2015. LTCS-Report
Dismatching and Local Disunification in EL
Technical Report, Chair for Automata Theory, Institute for Theoretical Computer Science, Technische Universität Dresden, volume 15-03, 2015. LTCS-Report
- KurzfassungAbstract
Unification in Description Logics has been introduced as a means to detect redundancies in ontologies. We try to extend the known decidability results for unification in the Description Logic EL to disunification since negative constraints on unifiers can be used to avoid unwanted unifiers. While decidability of the solvability of general EL-disunification problems remains an open problem, we obtain NP-completeness results for two interesting special cases: dismatching problems, where one side of each negative constraint must be ground, and local solvability of disunification problems, where we restrict the attention to solutions that are built from so-called atoms occurring in the input problem. More precisely, we first show that dismatching can be reduced to local disunification, and then provide two complementary NP-algorithms for finding local solutions of (general) disunification problems. - Bemerkung: Note: See http://lat.inf.tu-dresden.de/research/reports.html.
- Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory
@techreport{ BaBM-LTCS-15-03,
address = {Dresden, Germany},
author = {Franz {Baader} and Stefan {Borgwardt} and Barbara {Morawska}},
institution = {Chair for Automata Theory, Institute for Theoretical Computer Science, Technische Universit{\"a}t Dresden},
note = {See http://lat.inf.tu-dresden.de/research/reports.html.},
number = {15-03},
title = {Dismatching and Local Disunification in {$\mathcal{EL}$}},
type = {LTCS-Report},
year = {2015},
}
