The description logic (DL) EL, in which concepts can be built using concept names as well as the concept constructors conjunction ( u), existential restriction (9r:C), and the top concept (>), has drawn considerable attention in the last decade since, on the one hand, important inference problems such as the subsumption problem are polynomial in EL, even with respect to expressive terminological axioms [6]. On the other hand, though quite inexpressive, EL can be used to dene biomedical ontologies, such as the large medical ontology SNOMED CT.3 In EL we can, for example, dene the concept of a happy man as a male human that is healthy and handsome, has a rich and intelligent wife, a son and a daughter, and a friend: Human u Male u Healthy u Handsome u 9spouse:(Rich u Intelligent u Female) u 9child:Male u 9child:Female u 9friend:>
(1) For an individual to belong to this concept, all the stated properties need to be satised. However, maybe we would still want to call a man happy if most, though not all, of the properties hold. It might be sucient to have just a daughter without a son, or a wife that is only intelligent but not rich, or maybe an intelligent and rich spouse of a dierent gender. But still, not too many of the properties should be violated.
In this paper, we introduce a DL extending EL that allows us to dene concepts in such an approximate way. The main idea is to use a graded membership function, which instead of a Boolean membership value 0 or 1 yields a membership degree from the interval [0; 1]. We can then require a happy man to belong to the EL concept (1) with degree at least :8. More generally, if C is an EL concept, then the threshold concept C t for t 2 [0; 1] collects all the individuals that belong to C with degree at least t. In addition to such upper threshold concepts, we will also consider lower threshold concepts C t and allow the use of strict inequalities in both. For example, an unhappy man could be required to belong to the EL concept (1) with a degree less than :2. ? Supported by DFG Graduiertenkolleg 1763 (QuantLA). 3 see http://www.ihtsdo.org/snomed-ct/
The use of membership degree functions with values in the interval [0; 1]
may remind the reader of fuzzy logics. However, there is no strong relationship
between this work and the work on fuzzy DLs [
We name our new logic E L(m), where the membership degree function m
is a parameter in dening the logic. In [
M1 : d 2 CI , mI (d; C) = 1 M2 : C
D , for all d 2
I : mI (d; C) = mI (d; D): Property M2 expresses the intuition that the membership value should not depend on the syntactic form of a concept, but only on its semantics.
The set of E L(m) concept descriptions is dened inductively, starting from nite sets of concept names NC and role names NR, as follows:
Cb; Db ::= > j A j Cb u Db j 9r:Cb j E q where A 2 NC, r 2 NR, 2 f<; ; >; g, q 2 [0; 1] \ Q, E is an E L concept description, and Cb; Db are E L(m) concept descriptions. For a given interpretation I = ( I ; :I ), the semantics of the new threshold concepts is dened as follows: [E q]I := fd 2
I j mI (d; E) qg: The extension of :I to more complex concepts is dened as for E L by additionally considering the semantics of the newly introduced threshold concepts.
To make things more concrete, we introduce in [
Using Theorem 1 as a starting point, we consider all partial mappings h from
TC to GI that map the root of TC to d and respect the edge structure of TC .
For each of these mappings we then calculate to which degree it satises the
homomorphism conditions, and take the degree of the best such mapping as the
membership degree deg I (d; C). Intuitively, to compute the degree associated to
a partial mapping h, we dene the weighted homomorphism induced by h as a
function hw : dom(h) ! [0; 1]. Basically, in the denition of this function, the
individual d is punished (in the sense that its membership degree is lowered)
for each missing property (i.e., required element-hood in a concept name or an
existential restriction) in a uniform way (see [
In [
The main technical contribution of this work is, however, the investigation
of the complexity of terminological (subsumption, satisability) and assertional
(consistency, instance) reasoning in E L(deg ). To provide lower bounds, we show
NP-hardness of the satisability problem by a simple reduction from the
wellknown NP-complete problem ALL-POS ONE-IN-THREE 3SAT [
Lemma 1. Let Cb be a E L(deg ) concept description of size m. If Cb is satisable, then there exists an interpretation J such that CbJ 6= ; and j J j m.
A coNP-upper bound for subsumption cannot directly be obtained from the fact that satisability is in NP. In fact, though we have Cb v Db i Cb u :Db is unsatisable, this equivalence cannot be used directly since :Db need not be a
E L(deg ) concept description. Nevertheless, we can extend the ideas used in the
proof of Lemma 1 to obtain a polynomial bounded model property for
satisability of concepts of the form Cb u :Db . The same is true for ABox consistency.
Regarding instance checking, the bound on the size of counter models is
exponential w.r.t. combined complexity, but fortunately still polynomial w.r.t. data
complexity (in the sense of [
Overall, we thus obtain the following complexity results for reasoning in E L(deg ).
Theorem 2. In the DL E L(deg ), satisability is NP-complete, subsumption is coNP-complete, and ABox consistency is NP-complete. Moreover, instance checking is coNP-complete w.r.t. data complexity.
Due to the space constraints, we could not provide technical details and
proofs in this extended abstract. They can be found in the technical report [