License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.RTA.2015.40
URN: urn:nbn:de:0030-drops-51884
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5188/
Go to the corresponding LIPIcs Volume Portal

Baader, Franz ; Borgwardt, Stefan ; Morawska, Barbara

Dismatching and Local Disunification in EL

pdf-format:
8.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{baader_et_al:LIPIcs:2015:5188,
  author =	{Franz Baader and Stefan Borgwardt and Barbara Morawska},
  title =	{{Dismatching and Local Disunification in EL}},
  booktitle =	{26th International Conference on Rewriting Techniques and Applications (RTA 2015)},
  pages =	{40--56},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-85-9},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{36},
  editor =	{Maribel Fern{\'a}ndez},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5188},
  URN =		{urn:nbn:de:0030-drops-51884},
  doi =		{10.4230/LIPIcs.RTA.2015.40},
  annote =	{Keywords: Unification, Description Logics, SAT}
}

Keywords: Unification, Description Logics, SAT
Collection: 26th International Conference on Rewriting Techniques and Applications (RTA 2015)
Issue Date: 2015
Date of publication: 18.06.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI