Franz Baader ; Barbara Morawska - Unification in the Description Logic EL

lmcs:1106 - Logical Methods in Computer Science, September 4, 2010, Volume 6, Issue 3 - https://doi.org/10.2168/LMCS-6(3:17)2010
Unification in the Description Logic ELArticle

Authors: Franz Baader ORCID; Barbara Morawska ORCID

    The Description Logic EL has recently drawn considerable attention since, on the one hand, important inference problems such as the subsumption problem are polynomial. On the other hand, EL is used to define large biomedical ontologies. Unification in Description Logics has been proposed as a novel inference service that can, for example, be used to detect redundancies in ontologies. The main result of this paper is that unification in EL is decidable. More precisely, EL-unification is NP-complete, and thus has the same complexity as EL-matching. We also show that, w.r.t. the unification type, EL is less well-behaved: it is of type zero, which in particular implies that there are unification problems that have no finite complete set of unifiers.


    Volume: Volume 6, Issue 3
    Published on: September 4, 2010
    Imported on: October 21, 2009
    Keywords: Computer Science - Artificial Intelligence,Computer Science - Logic in Computer Science,cs.LO

    23 Documents citing this article

    Consultation statistics

    This page has been seen 1414 times.
    This article's PDF has been downloaded 399 times.