Title | ||
---|---|---|
Extending Unification in EL to Disunification: The Case of Dismatching and Local Disunification. |
Abstract | ||
---|---|---|
Unification in Description Logics has been introduced as a means to detectredundancies in ontologies. We try to extend the known decidability results forunification in the Description Logic $mathcal{EL}$ to disunification sincenegative constraints can be used to avoid unwanted unifiers. While decidabilityof the solvability of general $mathcal{EL}$-disunification problems remains anopen problem, we obtain NP-completeness results for two interesting specialcases: dismatching problems, where one side of each negative constraint must beground, and local solvability of disunification problems, where we consideronly solutions that are constructed from terms occurring in the input problem.More precisely, we first show that dismatching can be reduced to localdisunification, and then provide two complementary NP-algorithms for findinglocal solutions of disunification problems. |
Year | Venue | Field |
---|---|---|
2016 | Logical Methods in Computer Science | Ontology (information science),Discrete mathematics,Open problem,Computer science,Unification,Description logic,Decidability |
DocType | Volume | Citations |
Journal | abs/1609.05621 | 1 |
PageRank | References | Authors |
0.35 | 0 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Franz Baader | 1 | 8123 | 646.64 |
Stefan Borgwardt | 2 | 314 | 34.46 |
Barbara Morawska | 3 | 34 | 10.94 |