Baader, Franz and Borgwardt, Stefan and Morawska, Barbara - Extending Unification in $\mathcal{EL}$ to Disunification: The Case of Dismatching and Local Disunification

lmcs:2063 - Logical Methods in Computer Science, April 27, 2017, Volume 12, Issue 4
Extending Unification in $\mathcal{EL}$ to Disunification: The Case of Dismatching and Local Disunification

Authors: Baader, Franz and Borgwardt, Stefan and Morawska, Barbara

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 $\mathcal{EL}$ to disunification since negative constraints can be used to avoid unwanted unifiers. While decidability of the solvability of general $\mathcal{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 consider only solutions that are constructed from terms 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 disunification problems.


Source : oai:arXiv.org:1609.05621
DOI : 10.2168/LMCS-12(4:1)2016
Volume: Volume 12, Issue 4
Published on: April 27, 2017
Submitted on: April 20, 2016
Keywords: Computer Science - Logic in Computer Science,Computer Science - Artificial Intelligence,F.4.1,I.2.3,I.2.4


Share

Consultation statistics

This page has been seen 245 times.
This article's PDF has been downloaded 90 times.