=Paper=
{{Paper
|id=Vol-1350/paper-20
|storemode=property
|title=Adding
Threshold Concepts to the Description Logic EL
|pdfUrl=https://ceur-ws.org/Vol-1350/paper-20.pdf
|volume=Vol-1350
|dblpUrl=https://dblp.org/rec/conf/dlog/GilBB15
}}
==Adding
Threshold Concepts to the Description Logic EL==
https://ceur-ws.org/Vol-1350/paper-20.pdf
Adding Threshold Concepts to the Description
Logic EL
Franz Baader1 , Gerhard Brewka2 , and Oliver Fernández Gil2?
baader@tcs.inf.tu-dresden.de
{brewka,fernandez}@informatik.uni-leipzig.de
1
Theoretical Computer Science, TU Dresden, Germany
2
Department of Computer Science, University of Leipzig, Germany
The description logic (DL) EL, in which concepts can be built using concept
names as well as the concept constructors conjunction (u), existential restric-
tion (∃r.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 de ne biomedical ontologies, such as the large medical ontology
SNOMED CT.3 In EL we can, for example, de ne 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
∃spouse.(Rich u Intelligent u Female) u (1)
∃child.Male u ∃child.Female u ∃friend.>
For an individual to belong to this concept, all the stated properties need to
be satis ed. However, maybe we would still want to call a man happy if most,
though not all, of the properties hold. It might be su cient 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 de ne con-
cepts 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 member-
ship 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 ∈ [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 [5] for two reasons. First, in fuzzy
DLs the semantics is extended to fuzzy interpretations where concept and role
names are interpreted as fuzzy sets and relations, respectively. The membership
degree of an individual to belong to a complex concept is then computed using
fuzzy interpretations of the concept constructors. In our setting, we consider
crisp interpretations of concept and role names, and directly de ne membership
degrees for complex concepts based on them. Second, we use membership degrees
to obtain new concept constructors, but the threshold concepts obtained by
applying these constructors are again crisp rather than fuzzy.
We name our new logic τ EL(m), where the membership degree function m
is a parameter in de ning the logic. In [2], we propose one speci c such function
deg , but we do not claim this is the only reasonable way to de ne such a function.
Nevertheless, membership functions are not arbitrary. There are two properties
we require such functions to satisfy:
De nition 1. A graded membership function m is a family of functions that
contains for every interpretation I a function mI : ∆I → [0, 1] satisfying the
following conditions:
M1 : d ∈ C I ⇔ mI (d, C) = 1
M2 : C ≡ D ⇔ for all d ∈ ∆I : mI (d, C) = mI (d, D).
Property M2 expresses the intuition that the membership value should not de-
pend on the syntactic form of a concept, but only on its semantics.
The set of τ EL(m) concept descriptions is de ned inductively, starting from
nite sets of concept names NC and role names NR , as follows:
C,
b Db ::= > | A | C
buD
b | ∃r.C
b | E∼q
where A ∈ NC , r ∈ NR , ∼ ∈ {<, ≤, >, ≥}, q ∈ [0, 1] ∩ Q, E is an EL concept de-
scription, and C,b Db are τ EL(m) concept descriptions. For a given interpretation
I = (∆I , .I ), the semantics of the new threshold concepts is de ned as follows:
[E∼q ]I := {d ∈ ∆I | mI (d, E) ∼ q}.
The extension of .I to more complex concepts is de ned as for EL by additionally
considering the semantics of the newly introduced threshold concepts.
To make things more concrete, we introduce in [2] a speci c membership
function, denoted deg , which satis es properties M1 and M2. Given an interpre-
tation I , an element d ∈ ∆I , and an EL concept description C , this function
measures to which degree d satis es the conditions for membership expressed by
C . To come up with such a function, we use the homomorphism characterization
of crisp membership in EL. In EL, concept descriptions and interpretations can
be translated into EL description trees and EL description graphs, respectively
(see [4,1]). Then, homomorphisms between EL description trees can be used
to characterized subsumption in EL [4]. The proof of this result can be easily
adapted to obtain the following characterization of element-hood in EL.
Theorem 1. Let I be an interpretation, d ∈ ∆I and C an EL concept descrip-
tion. Then, d ∈ C I i there exists a homomorphism ϕ from TC to GI such that
ϕ(v0 ) = d.
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 satis es 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 de ne the weighted homomorphism induced by h as a
function hw : dom(h) → [0, 1]. Basically, in the de nition 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 [2] for the precise de nition).
In [2], we describe an algorithm that, given a nite interpretation I , computes
deg I (d, C) in polynomial time. This polynomial time algorithm is inspired by
the polynomial time algorithm for checking the existence of a homomorphism
between EL description trees [3,4], and similar to the algorithm for computing
the similarity degree between EL concept descriptions introduced in [9].
The main technical contribution of this work is, however, the investigation
of the complexity of terminological (subsumption, satis ability) and assertional
(consistency, instance) reasoning in τ EL(deg). To provide lower bounds, we show
NP-hardness of the satis ability problem by a simple reduction from the well-
known NP-complete problem ALL-POS ONE-IN-THREE 3SAT [8]. The corre-
sponding NP upper bound for satis ability is an immediate consequence of the
following polynomial bounded model property.
Lemma 1. Let Cb be a τ EL(deg) concept description of size m. If Cb is satis -
able, then there exists an interpretation J such that CbJ 6= ∅ and |∆J | ≤ m.
A coNP-upper bound for subsumption cannot directly be obtained from the
fact that satis ability is in NP. In fact, though we have Cb v D b i C
b u ¬Db is
unsatis able, this equivalence cannot be used directly since ¬D need not be a
b
τ EL(deg) concept description. Nevertheless, we can extend the ideas used in the
proof of Lemma 1 to obtain a polynomial bounded model property for satis a-
bility 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 expo-
nential w.r.t. combined complexity, but fortunately still polynomial w.r.t. data
complexity (in the sense of [7]).
Overall, we thus obtain the following complexity results for reasoning in
τ EL(deg).
Theorem 2. In the DL τ EL(deg), satis ability 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 [2].
References
1. Baader, F.: Terminological cycles in a description logic with existential restrictions.
In: Gottlob, G., Walsh, T. (eds.) IJCAI. pp. 325330. Morgan Kaufmann (2003)
2. Baader, F., Brewka, G., Fernández Gil, O.: Adding threshold concepts to the de-
scription logic EL. LTCS-Report 15-09, Chair for Automata Theory, Institute for
Theoretical Computer Science, Technische Universität Dresden, Dresden, Germany
(2015), see http://lat.inf.tu-dresden.de/research/reports.html.
3. Baader, F., Küsters, R., Molitor, R.: Computing least common subsumers in de-
scription logics with existential restrictions. LTCS-Report LTCS-98-09, LuFG The-
oretical Computer Science, RWTH Aachen, Germany (1998), see http://lat.inf.tu-
dresden.de/research/reports.html.
4. Baader, F., Küsters, R., Molitor, R.: Computing least common subsumers in de-
scription logics with existential restrictions. In: Dean, T. (ed.) IJCAI. pp. 96103.
Morgan Kaufmann (1999)
5. Borgwardt, S., Distel, F., Peñaloza, R.: The limits of decidability in fuzzy description
logics with general concept inclusions. Arti cial Intelligence 218, 2355 (2015)
6. Brandt, S.: Polynomial time reasoning in a description logic with existential re-
strictions, GCI axioms, and - what else? In: de Mántaras, R.L., Saitta, L. (eds.)
Proceedings of the 16th Eureopean Conference on Arti cial Intelligence, ECAI'2004,
including Prestigious Applicants of Intelligent Systems, PAIS 2004, Valencia, Spain,
August 22-27, 2004. pp. 298302. IOS Press (2004)
7. Donini, F.M., Lenzerini, M., Nardi, D., Schaerf, A.: Deduction in concept languages:
From subsumption to instance checking. J. Log. Comput. 4(4), 423452 (1994),
http://dx.doi.org/10.1093/logcom/4.4.423
8. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory
of NP-Completeness. W. H. Freeman (1979)
9. Suntisrivaraporn, B.: A similarity measure for the description logic EL with unfold-
able terminologies. In: 2013 5th International Conference on Intelligent Networking
and Collaborative Systems, Xi'an city, Shaanxi province, China, September 9-11,
2013. pp. 408413. IEEE (2013), http://dx.doi.org/10.1109/INCoS.2013.77