=Paper=
{{Paper
|id=None
|storemode=property
|title=About Subsumption in Fuzzy EL
|pdfUrl=https://ceur-ws.org/Vol-1014/paper_48.pdf
|volume=Vol-1014
|dblpUrl=https://dblp.org/rec/conf/dlog/BorgwardtP13
}}
==About Subsumption in Fuzzy EL==
https://ceur-ws.org/Vol-1014/paper_48.pdf
About Subsumption in Fuzzy EL?
Stefan Borgwardt1 and Rafael Peñaloza1,2
1
Theoretical Computer Science, TU Dresden, Germany
2
Center for Advancing Electronics Dresden
{stefborg,penaloza}@tcs.inf.tu-dresden.de
1 Introduction
Classical Description Logics (DLs) [2] cannot properly deal with the endemic
imprecision of biomedical knowledge. For example, the current version of the
SNOMED CT ontology defines a “Perinatal Cyanotic Attack” as a cardiovascular
disorder occurring in the perinatal period and manifested through cyanosis. This
definition depends on two vague notions, namely the perinatal period —the period
of time around birth—and cyanosis—a bluish discoloration of the skin. While
it is possible to say that one year after birth is not perinatal, and a few hours
from birth is, there is no precise threshold on the end of the perinatal period.
However, it makes sense to say that every child is less in its perinatal period as
time goes by. A similar consideration can be made for skin turning from red to
blue in cases of cyanosis. The use of several degrees of truth has been proposed
for dealing with these gradual changes, as well as other kinds of imprecisions.
Mathematical Fuzzy Logic [12] generalizes classical logic by allowing real
numbers from the interval [0, 1] to act as truth degrees. It allows to express,
e.g. that a newborn child is in the perinatal period with degree 1, but a three-
week-old belongs to this period only with degree 0.3. In Mathematical Fuzzy
Logic, the interpretation of the logical constructors, such as conjunction, dis-
junction, and implication, is determined by the choice of a binary triangular
norm (or t-norm). Fuzzy Description Logics combine DLs with Mathematical
Fuzzy Logic as a means to formally represent and reason with vague conceptual
knowledge [18,19]. So far, research on fuzzy DLs was mainly focused on fuzzy
extensions of propositionally closed DLs. Unfortunately, in fuzzy DLs a negation
constructor often leads to undecidability [7,11].
To the best of our knowledge, the only fuzzy extensions of EL studied so
far are based on the Gödel t-norm [16,20]. In these logics, fuzzy subsumption
between concepts can be decided in polynomial time. Beyond this tractable case,
very little is known about the complexity of subsumption with general t-norms.
If we restrict the set of membership degrees to be finite, subsumption can be
decided in exponential time [3,8], but for the interval [0, 1] nothing is known,
even for expressive fuzzy DLs in which consistency is decidable [5].
?
Partially supported by the DFG under grant BA 1122/17-1, in the research training
group 1763 (QuantLA), and in the Cluster of Excellence ‘cfAED’
Table 1. The three fundamental continuous t-norms.
Name t-norm (x ⊗ y) residuum (x ⇒ y)
(
1 if x ≤ y
Gödel min{x, y}
y otherwise
(
1 if x ≤ y
Product x·y
y/x otherwise
Łukasiewicz max{x + y − 1, 0} min{1 − x + y, 1}
We consider fuzzy extensions of EL with general t-norm semantics, and study
their complexity. As for the classical case, we are interested in deciding subsump-
tion between concepts. We study the problem of 1-subsumption, which can be
seen as deciding classical subsumption between fuzzy concepts. We show that
this problem is co-NP-hard in general for a wide variety of t-norms. However,
if we restrict to normalized TBoxes, then under some additional assumptions
this problem can be solved in polynomial time. To show this, we provide a
completion-based algorithm that classifies the TBox w.r.t. 1-subsumption.
2 Preliminaries
We introduce the fuzzy DL ⊗-EL and its reasoning tasks, along with some of
the properties that will be used throughout the paper. The semantics of ⊗-EL
depends on the choice of a t-norm ⊗. A t-norm is an associative, commutative,
and monotone binary operator ⊗ : [0, 1] × [0, 1] → [0, 1] that has unit 1 [15]. We
consider only continuous t-normsNn throughout this paper. Given a t-norm ⊗ and
x ∈ [0, 1], we define xn := i=1 x. Every continuous t-norm defines a unique
residuum ⇒ : [0, 1] × [0, 1] → [0, 1] where x ⇒ y := sup{z | x ⊗ z ≤ y}. From
this it follows that (i) x ⇒ y = 1 iff x ≤ y, and (ii) 1 ⇒ y = y hold for all
x, y ∈ [0, 1]. Table 1 lists three important continuous t-norms and their residua.
All other continuous t-norms can be built as the ordinal sums of copies of these
t-norms, as follows.
Let ((ai , bi ))i∈I be a (possibly infinite) family of non-empty, disjoint open
subintervals of [0, 1] and (⊗i )i∈I be a family of continuous t-norms over the
same index set I. The ordinal sum of (((ai , bi ), ⊗i ))i∈I is the t-norm ⊗, where
x−ai y−ai
x ⊗ y := ai + (bi − ai ) bi −ai ⊗i bi −ai
if x, y ∈ [ai , bi ] for some i ∈ I, and x ⊗ y := min{x, y} otherwise. This yields a
continuous t-norm, whose residuum x ⇒ y is given by
1 if x ≤ y,
x−ai y−ai
ai + (bi − ai ) bi −ai ⇒i bi −ai if ai ≤ y < x ≤ bi ,
y otherwise,
where ⇒i is the residuum of ⊗i , for each i ∈ I [15]. Intuitively, this means that
the t-norm ⊗ and its residuum “behave like” ⊗i and its residuum in each of the
intervals [ai , bi ], and like the Gödel t-norm and residuum everywhere else.
Theorem 1 ([17]). Every continuous t-norm is isomorphic to the ordinal sum
of copies of the Łukasiewicz and product t-norms.
Let ⊗ be a continuous t-norm and (((ai , bi ), ⊗i ))i∈I be its representation as ordi-
nal sum given by Theorem 1.3 We call (((ai , bi ), ⊗i ))i∈I the components of ⊗. We
say that ⊗ contains a t-norm ⊗0 if it has a component of the form ((ai , bi ), ⊗0 ).
It starts with Łukasiewicz if it has a component of the form ((0, b), ⊗Ł ), where
⊗Ł is the Łukasiewicz t-norm, and analogously for ends with Łukasiewicz. The
only elements x ∈ [0, 1] that are idempotent w.r.t. ⊗, i.e. that satisfy x ⊗ x = x,
are those that are not in (ai , bi ) for any i ∈ I. Every continuous t-norm except
the Gödel t-norm has infinitely many non-idempotent elements.
Every continuous t-norm ⊗ defines a fuzzy DL ⊗-EL. If ⊗ is the Gödel or
Łukasiewicz t-norm, we write G-EL or Ł-EL, respectively. The syntax of ⊗-EL
is the same as in classical EL. Concepts are built from two disjoint sets NC
and NR of concept and role names, respectively, using the constructors top (>),
conjunction (C1 u C2 ), and existential restriction (∃r.C). C n denotes the n-ary
conjunction of a ⊗-EL-concept C with itself; C n := ui=1 C. A ⊗-EL-TBox is a
n
finite set of general concept inclusion axioms (GCIs) of the form hC v D ≥ qi,
where C, D are ⊗-EL-concepts and q ∈ [0, 1]. A ⊗-EL-TBox is crisp all its GCIs
are of the form hC v D ≥ 1i. We often drop the prefix ⊗-EL and speak simply
of, e.g. concepts and TBoxes.
The semantics of this logic extends the classical DL semantics by interpreting
concepts and roles as fuzzy sets and fuzzy binary relations, respectively, over an
interpretation domain. Given a domain ∆, a fuzzy set is a function F : ∆ → [0, 1].
Intuitively, an element δ ∈ ∆ belongs to the fuzzy set F with degree F (δ). An
interpretation is a pair I = (∆I , ·I ) where ∆I is a non-empty domain, and the
interpretation function ·I maps concept names A and role names r to functions
AI : ∆I → [0, 1] and rI : ∆I × ∆I → [0, 1], respectively. The interpretation
function is extended to ⊗-EL-concepts by setting, for every δ ∈ ∆, >I (δ) := 1,
(C1 u C2 )I (δ) := C1I (δ) ⊗ C2I (δ), and (∃r.C)I (δ) := supγ∈∆I rI (δ, γ) ⊗ C I (γ).
An interpretation I satisfies the GCI hC v D ≥ qi iff (C I (δ) ⇒ DI (δ)) ≥ q
for all δ ∈ ∆I . It is a model of the TBox T if it satisfies all the GCIs in T . An
interpretation I is called crisp if AI (δ) ∈ {0, 1} and rI (δ, γ) ∈ {0, 1} hold for
every concept name A, role name r, and δ, γ ∈ ∆I .
Example 2. The concept of perinatal cyanotic attacks (PCA) can be described
using the GCI
hPCA v CardiovascDisorder u ∃occur.PerinatalPeriod u ∃manif.Cyanosis ≥ 1i,
which is very close to the definition found in SNOMED CT. With the Łukasiewicz
t-norm, an element that belongs to each of the concepts on the right-hand side
3
For ease of presentation, we treat the isomorphism as equality.
with degree 0.7 will belong to PCA with degree at most 0.7 + 0.7 + 0.7 − 2 = 0.1.
While this makes sense from a diagnostic point of view—lesser symptomatic
manifestations should yield a weaker diagnosis—SNOMED CT is meant to de-
scribe clinical terms, rather than diagnose them. It thus makes sense to divide
the previous GCI into the three axioms
hPCA v CardiovascDisorder ≥ 1i, hPCA v ∃occur.PerinatalPeriod ≥ 1i,
hPCA v ∃manif.Cyanosis ≥ 1i.
In fuzzy DLs, reasoning is sometimes restricted to witnessed interpretations [13]:
interpretations I in which there is a γ ∈ ∆I with (∃r.C)I (δ) = rI (δ, γ) ⊗ C I (γ).
This restriction was introduced in [13] to correct the existing algorithm for fuzzy
ALC in [19]. In this paper we do not need this additional assumption; all our
results are valid w.r.t. general and witnessed semantics.
As in classical EL, every ⊗-EL-TBox has the trivial model I = ({δ}, ·I ) where
A (δ) = 1 for every concept name A and rI (δ, δ) = 1 for every role name r. Thus,
I
TBox consistency is trivial in this logic. We are therefore interested in deciding
subsumption between two concepts, and other related problems.
Definition 3. Let T be a TBox, C, D be two concepts, and p ∈ (0, 1]. C is
p-subsumed by D w.r.t. T (C vpT D) if every model of T satisfies hC v D ≥ pi.
C is positively subsumed by D w.r.t. T (C v>0T D) if every model I of T and
every δ ∈ ∆I satisfies C I (δ) ⇒ DI (δ) > 0. The best subsumption degree of
C v D w.r.t. T is bsdT (C v D) := sup{p ∈ [0, 1] | C vpT D}.
Clearly, if bsdT (C v D) > 0, then C v>0 T D. However, the converse does not
necessarily hold, as evidenced by the following example.
Example 4. Consider the product t-norm and A ∈ NC . For every interpretation
I and δ ∈ ∆I , if AI (δ) > 0, then AI (δ) ⇒ (A2 )I (δ) = AI (δ) > 0. Thus A is
positively subsumed by A2 . However, for every p > 0 there is an interpretation
I = ({δ}, ·I ) with AI (δ) = p/2. Then, AI (δ) ⇒ (A2 )I (δ) = AI (δ) = p/2 < p. As
this holds for every p > 0, it follows that bsd∅ (A v A2 ) = 0.
3 Hardness Results
In this section we show several hardness results for the decision problems that
we have defined before. In particular, we describe families of t-norms for which
deciding positive subsumption and 1-subsumption, as well as computing the
best subsumption degree is not tractable (unless P = NP). We first show
that 1-subsumption is co-NP-hard for the Łukasiewicz t-norm, by reducing the
NP-hard vertex cover problem [14] to its complement.
Definition 5. Let V = {v1 , . . . , vm } be a finite set, and E a set of subsets of V
of cardinality 2. A vertex cover is a set S ⊆ V such that S ∩ E 6= ∅ holds for all
E ∈ E. The vertex cover problem consists in deciding, given a natural number
k ≤ m, whether there is a vertex cover of cardinality ≤ k.
Every superset of a vertex cover is also a vertex cover, and thus one can equiva-
lently ask for a vertex cover of size exactly k. We assume without loss of gener-
ality that the graph (V, E) has no isolated nodes since such nodes are irrelevant
for vertex covers. Given an instance V := (V, E, k) of the vertex cover problem,
we construct an Ł-EL-TBox TV and two concept names A, B such that A is not
1-subsumed by B w.r.t. TV iff there is a vertex cover of size k. Let Vi , 0 ≤ i ≤ m,
be concept names, where m = |V |, i.e. we have a concept name Vi for every
vi ∈ V , and an additional concept name V0 . For each i, 1 ≤ i ≤ m, we set
Ti := {hVim−k v Vim−k+1 ≥ 1i, h> v Vi ≥ m−k−1
m−k i}
m I
and T0 := {h> v V0 ≥ m−k−1
S
m−k i}. Every model I of i=0 Ti and δ ∈ ∆ satisfies
I m−k−1 I m−k−1
that V0 (δ) ≥ m−k and Vi (δ) ∈ { m−k , 1} for 1 ≤ i ≤ m. We now define
m
[
TV := Ti ∪ {hA v V0m−k−1 ≥ 1i, hV1 u . . . u Vm v B ≥ 1i} ∪
i=0
{hV0 v Vj1 u Vj2 ≥ 1i | {vj1 , vj2 } ∈ E}. (1)
Theorem 6. There is a vertex cover of V, E of size k iff A is not 1-subsumed
by B w.r.t. TV .
Proof. Let S = {vi1 , . . . , vik } be a vertex cover of size k. Build the interpretation
IS := ({δ}, ·IS ) with AIS (δ) := 1/m−k, B IS (δ) := 0, V0IS (δ) := m−k−1 m−k , and for
i, 1 ≤ i ≤ m, (
1 if vi ∈ S
ViIS (δ) := m−k−1
m−k otherwise.
It is easy to verify that IS is a model of TV and AIS (δ) ⇒ B IS (δ) = m−k−1 m−k < 1.
Conversely, let I be a model of TV and δ ∈ ∆ with A (δ) > B I (δ). In
I I
particular, AI (δ) ≤ 1/m−k, since otherwise, B I (δ) = 1. We can now define
SI := {vi | ViI (δ) = 1, 1 ≤ i ≤ m}. Since V1I (δ) ⊗ . . . ⊗ VmI (δ) < 1/m−k, there
must be at least m − k concept names Vj such that VjI (δ) = m−k−1 m−k , and hence
SI has at most k elements. Moreover, since I satisfies the axioms in (1), for every
{vj1 , vj2 } ∈ E, at least one of VjI1 (δ), VjI2 (δ) is 1. Thus, SI is a vertex cover. t
u
Corollary 7. 1-subsumption in Ł-EL is co-NP-hard.
Since TV does not use any roles, hardness holds already in the sublogic of Ł-EL
without roles. We can extend this result with the help of the following theorem.
Theorem 8 ([9]). Let ⊗1 , ⊗2 be continuous t-norms, b ∈ (0, 1), and ⊗ be the
ordinal sum of ((0, b), ⊗1 ), ((b, 1), ⊗2 ). Then p-subsumption in ⊗-EL is at least
as hard as p-subsumption in ⊗2 -EL.
A direct consequence of this theorem is that 1-subsumption is co-NP-hard in
⊗-EL, for any continuous t-norm ⊗ that ends with the Łukasiewicz t-norm.
Using similar reductions to the vertex cover problem, it was previously shown
that other subsumption problems are intractable for t-norms that start with
Łukasiewicz. The proofs are similar to the one of Theorem 6.
Proposition 9 ([9]). If ⊗ starts with Łukasiewicz, then positive subsumption
and p-subsumption in ⊗-EL are co-NP-hard.
Every t-norm that contains the Łukasiewicz t-norm can be expressed as the
ordinal sum of two components ((0, b), ⊗1 ), ((b, 1), ⊗2 ), where ⊗2 starts with
Łukasiewicz. Thus, Proposition 9 and Theorem 8 yield the following.
Corollary 10. If ⊗ contains the Łukasiewicz t-norm, then p-subsumption in
⊗-EL is co-NP-hard.
This shows that the best subsumption degree in ⊗-EL cannot be computed in
polynomial time if ⊗ contains the Łukasiewicz t-norm (unless P = NP).
For positive subsumption there is also a matching tractability result: if the
underlying t-norm ⊗ does not start with the Łukasiewicz t-norm, then positive
subsumption is decidable in polynomial time, as in the crisp case [1,10]. This
can be shown by a reduction similar to the one from [5], where consistency in
expressive fuzzy DLs is reduced to the corresponding crisp DLs. This reduction
transforms a ⊗-EL-TBox T into the crisp TBox
T >0 := {hC v D ≥ 1i | hC v D ≥ qi ∈ T , q > 0}
that describes all positive subsumption relations.
Theorem 11 ([9]). Let T be a TBox and C0 , D0 two concepts. Then C0 is
positively subsumed by D0 w.r.t. T iff for every crisp model J of T >0 and
δ ∈ ∆J it holds that C0J (δ) ≤ D0J (δ).
The latter condition in this theorem is equivalent to subsumption between C0
and D0 in classical EL, which can be decided in polynomial time [10].
Corollary 12. If ⊗ does not start with Łukasiewicz, then positive subsumption
in ⊗-EL is decidable in polynomial time.
4 A Completion Algorithm for 1-Subsumption
We now develop a completion algorithm in the style of [1,16] that allows us to
decide 1-subsumption under the following restrictions. As in Corollary 12, the
underlying t-norm ⊗ must not start with Łukasiewicz. Furthermore, all roles are
restricted to be crisp, i.e. they are always interpreted by fuzzy binary relations
using only the values 0 and 1. The third and last restriction is that the underlying
TBox T is restricted to be normalized, i.e. all GCIs in T are of the form
hA1 u A2 v B ≥ pi, hA v ∃r.B ≥ pi, h∃r.A v B ≥ pi
for A1 , A1 , A, B ∈ N> 4
C := NC ∪ {>} and p ∈ [0, 1]. Contrary to the classical case,
⊗-EL-TBoxes cannot be transformed into equivalent normalized ones in general;
hence, this restriction does affect the expressivity of the logic.
4
Notice that hA v B ≥ pi is equivalent to h> u A v B ≥ pi.
(CR1) If q1 ⊗ xn m
A ∈ S(A, B1 ), q2 ⊗ xA ∈ S(A, B2 ), and hB1 u B2 v C ≥ pi ∈ T , then
n+m
add (p ⊗ q1 ⊗ q2 ) ⊗ xA to S(A, C).
(CR2) If q ⊗ xnA ∈ S(A, B) and hB v ∃r.C ≥ pi ∈ T , then add (p ⊗ q) ⊗ xn A to
R(A, r, C).
(CR3) If q1 ⊗ xn m
A ∈ R(A, r, B), q2 ⊗ xB ∈ S(B, C), and h∃r.C v D ≥ pi ∈ T , then
m nm
add (p ⊗ q1 ⊗ q2 ) ⊗ xA to S(A, D).
Fig. 1. The completion rules
Given such a TBox T , we compute for every A, B ∈ N> C , and r ∈ NR sets
S(A, B) and R(A, r, B) containing monomials of the form q ⊗ xnA , where xA is a
variable, n ≥ 0 is a natural number, and q ∈ [0, 1]. The idea is that, whenever the
value of A is p ∈ [0, 1], then q⊗xnA ∈ S(A, B) implies that the value of B is at least
q ⊗ pn , and thus An is q-subsumed by B. Similarly, if q ⊗ xnA ∈ R(A, r, B), then
the value of ∃r.B is greater or equal q ⊗ pn . In this way, S(A, B) (or R(A, r, B))
describes subsumption relationships between (powers of) A and B (or ∃r.B).
We define an order on such monomials as follows. Given p, q ∈ [0, 1] and
n, m ≥ 0, we define q⊗xn p⊗xm iff n ≤ m and q ≥ p. Note that q⊗xn p⊗xm
implies that the value of the first monomial for x ∈ [0, 1] is always greater or equal
that of the second monomial. Since these monomials represent lower bounds for
the best subsumption degree, it is clear that we only need to add a monomial to
S(A, B) or R(A, r, B) if this set does not already contain a larger one. We also
never add the trivial monomial 0.
We initialize these sets as S(A, A) := {xA }, and S(A, >) := S(>, >) := {1}
for all A ∈ NC . All other sets S(A, B) and R(A, r, B) are initially empty. We then
exhaustively apply the rules from Figure 1. As mentioned before, a monomial is
only added to a set if it does not already contain a larger monomial w.r.t. .
The completion rules in Figure 1 generalize those for classical EL [10] and
for G-EL [16]. The difference to the rules for the Gödel t-norm are caused by the
existence of non-idempotent elements in general t-norms. For the Gödel t-norm,
the subsumption degree of An by B is independent of n, and thus only monomials
of the form q or q ⊗ xA , i.e. constants or linear terms, can occur in S(A, B).
Note that the sets S(>, B) for B ∈ N> C can only contain constants, which is
why we will often treat S(>, B) as a value from [0, 1], which is 0 if the set is
empty. Furthermore, it is easy to show that any constant added to S(>, B) is
also added to every S(A, B) for A ∈ N> C , and vice versa, by applying the same
rules with different left-hand sides. Similar arguments apply to R(>, r, B).
We now argue that the algorithm described above terminates. Consider any
A, B ∈ N> C . If at some point during the run of the algorithm a monomial q ⊗xA is
n
added to S(A, B) by a rule application, then q must be of the form p1 ⊗. . .⊗pm for
values p1 , . . . , pm occurring in T . Once S(A, B) contains q ⊗ xnA , only monomials
of the form q 0 ⊗xm 0
A , where either q > q or m < n, can be added to S(A, B). Since
0
q also has to be a combination of values occurring in T , there are only finitely
many values q 0 that satisfy the first condition and are contained in the same
component of ⊗ as q. Obviously, there are also only finitely many numbers m
satisfying the second condition. Furthermore, for each q 0 there can only be one m
such that q 0 ⊗xm
A ∈ S(A, B), and once there is such an m, it can only be decreased
by the following rule applications. Similarly, for each m there can only be one q 0
with this property, and this q 0 can only be increased. As mentioned before, there
are only finitely many possibilities for q 0 inside the same component, and once a
new q 0 has been computed that lies in another component, there are again only
finitely many possible values exceeding q 0 in the same component. Since from
the values in T one can only compute values in finitely many components of ⊗,
this shows that the algorithm can add only finitely many elements to S(A, B)
(or R(A, r, B)), and hence it always terminates.
Lemma 13. Let A, B ∈ N> I
C , r ∈ NR , I be a model of T , and δ ∈ ∆ .
– If q ⊗ xnA ∈ S(A, B) and AI (δ) > 0, then q ⊗ (AI (δ))n ≤ B I (δ).
– If q ⊗ xnA ∈ R(A, r, B) and AI (δ) > 0, then q ⊗ (AI (δ))n ≤ (∃r.B)I (δ).
Proof. The claim is obviously true after initializing S and R. Assume that it
holds after applying several rules and consider the next rule that is applied.
In the case of (CR1), consider q1 ⊗ xnA ∈ S(A, B1 ), q2 ⊗ xm A ∈ S(A, B2 ),
hB1 u B2 v C ≥ pi ∈ T , and AI (δ) > 0. We thus have q1 ⊗ (AI (δ))n ≤ B1I (δ),
q2 ⊗ (AI (δ))m ≤ B2I (δ), and p ⊗ B1I (δ) ⊗ B2I (δ) ≤ C I (δ). It follows that
p ⊗ q1 ⊗ q2 ⊗ (AI (δ))n+m ≤ p ⊗ B1I (δ) ⊗ B2I (δ) ≤ C I (δ),
n+m
and thus we can add (p ⊗ q1 ⊗ q2 ) ⊗ xA to S(A, C) without violating the claim.
For (CR2), let q ⊗ xA ∈ S(A, B), hB v ∃r.C ≥ pi ∈ T , and AI (δ) > 0. By
n
assumption, we have q ⊗ (AI (δ))n ≤ B I (δ) and p ⊗ B I (δ) ≤ (∃r.C)I (δ), and
thus p ⊗ q ⊗ (AI (δ))n ≤ (∃r.C)I (δ) as required.
Finally, for the case of (CR3), let q1 ⊗ xnA ∈ R(A, r, B), q2 ⊗ xm
B ∈ S(B, C),
h∃r.C v D ≥ pi ∈ T , and AI (δ) > 0, which yields q1 ⊗ (AI (δ))n ≤ (∃r.B)I (δ).
We first consider the case that m = 0. Since q1 > 0 and ⊗ does not start with
Łukasiewicz, we have (∃r.B)I (δ) > 0. Thus, there is a γ ∈ ∆I with rI (δ, γ) = 1
and B I (γ) > 0. The assumption yields that q2 ≤ C I (γ), and thus
p ⊗ q10 ⊗ q2 ⊗ (AI (δ))0 = p ⊗ q2 ≤ p ⊗ rI (δ, γ) ⊗ C I (γ) ≤ p ⊗ (∃r.C)I (δ) ≤ DI (δ).
For the case of m ≥ 1, since r is crisp we get
m m
q2 ⊗ (∃r.B)I (δ) = q2 ⊗ sup rI (δ, γ) ⊗ B I (γ)
γ∈∆I
= q2 ⊗ sup r (δ, γ) ⊗ (B I (γ))m ≤
I
sup rI (δ, γ) ⊗ C I (γ) ≤ (∃r.C)I (δ).
I I
γ∈∆ γ∈∆
B I (γ)>0 B I (γ)>0
This implies that
m
p ⊗ q1m ⊗ q2 ⊗ (AI (δ))nm ≤ p ⊗ q2 ⊗ (∃r.B)I (δ) ≤ p ⊗ (∃r.C)I (δ) ≤ DI (δ).
Hence, the claim is still satisfied after adding (p ⊗ q1m ⊗ q2 ) ⊗ xnm
A to S(A, D). t
u
We now show that this algorithm is complete for deciding 1-subsumptions.
Lemma 14. For every A, B ∈ N> 1
C with A vT B and all p ∈ [0, 1], it holds that
p≤ max q ⊗ pn .
q⊗xn
A ∈S(A,B)
Proof. We construct a canonical model I of T from which we can read off all
1-subsumptions. Its domain is ∆I := {Ap | A ∈ N> C , p ∈ [0, 1]}. Given C ∈ NC ,
r ∈ NR , A, B ∈ N>C , and p, p0
∈ [0, 1], we set C I
(A p ) := maxq⊗xnA ∈S(A,C)
q ⊗ pn ,
where the empty maximum is 0, and
(
1 if p0 = maxq⊗xnA ∈R(A,r,B) q ⊗ pn ,
rI (Ap , Bp0 ) :=
0 otherwise.
Observe that it also holds that >I (Ap ) = maxq⊗xnA ∈S(A,>) q ⊗ pn since S(A, >)
is always {1}. Furthermore, for any A ∈ N> C and p ∈ [0, 1] we have
AI (Ap ) = max q ⊗ pn = max{S(>, A), p}.
q⊗xn
A ∈S(A,A)
To show that I is actually a model of T , consider first an axiom of the form
hB1 u B2 v C ≥ pi in T and a domain element Ap0 ∈ ∆I . By (CR1), we have
p ⊗ B1I (Ap0 ) ⊗ B2I (Ap0 ) = max max p ⊗ q1 ⊗ q2 ⊗ (p0 )n+m
q1 ⊗xn m
A ∈S(A,B1 ) q2 ⊗xA ∈S(A,B2 )
≤ max q ⊗ (p0 )n = C I (Ap0 ).
q⊗xn
A ∈S(A,C)
For an axiom hB v ∃r.C ≥ pi ∈ T , let p00 := maxq⊗xnA ∈R(A,r,C) q ⊗ (p0 )n . We get
p ⊗ B I (Ap0 ) = max p ⊗ q ⊗ (p0 )n ≤ max q ⊗ (p0 )n = p00
q⊗xn
A ∈S(A,B) q⊗xn
A ∈R(A,r,C)
≤ max{S(>, C), p00 } = C I (Cp00 ) = rI (Ap0 , Cp00 ) ⊗ C I (Cp00 )
≤ sup rI (Ap0 , Dp000 ) ⊗ C I (Dp000 ) = (∃r.C)I (Ap0 ).
Dp000 ∈∆I
Finally, for an axiom h∃r.C v Di ∈ T , let pB := maxq1 ⊗xnA ∈R(A,r,B) q1 ⊗ (p0 )n
for every B ∈ N> C . By (CR3), we have
p ⊗ (∃r.C)I (Ap0 ) = sup p ⊗ rI (Ap0 , Bp00 ) ⊗ C I (Bp00 ) = max p ⊗ C I (BpB )
Bp00 ∈∆I B∈N>
C
= max max p ⊗ q2 ⊗ pm
B
B∈N>
C
q2 ⊗xm
B ∈S(B,C)
= max max max p ⊗ q2 ⊗ q1m ⊗ (p0 )nm
B∈N>
C
q1 ⊗xn m
A ∈R(A,r,B) q2 ⊗xB ∈S(B,C)
≤ max max q ⊗ (p0 )n = DI (Ap0 ).
B∈N>
C
q⊗xn
A ∈S(A,D)
Consider now A, B ∈ N> 1
C with A vT B, and any p ∈ [0, 1]. Then we have
I I
p ≤ max{S(>, A), p} = A (Ap ) ≤ B (Ap ) = maxq⊗xnA ∈S(A,B) q ⊗ pn . t
u
We now show how to employ the algorithm to decide 1-subsumptions between
concept names in ⊗-EL. The actual decision procedure depends on the structure
of ⊗. More precisely, we consider the smallest b ∈ [0, 1] such that all elements
in [b, 1] are idempotent w.r.t. ⊗. This means that ⊗ is isomorphic to the Gödel
t-norm on [b, 1], or equivalently, that the representation of ⊗ according to The-
orem 1 has no component overlapping [b, 1]. Since ⊗ is fixed, we assume in the
following that b is known or easily computable from the representation of ⊗.
Theorem 15. Let A, B ∈ N> 1
C . Then A vT B iff either (i) {xA , 1}∩S(A, B) 6= ∅,
n
or (ii) {q, xA } ⊆ S(A, B) for q ≥ b and n ≥ 2.
Proof. [if] Let I be a model of T and δ ∈ ∆I . We show that AI (δ) ≤ B I (δ).
If AI (δ) = 0, then this obviously holds. If AI (δ) > 0, then Lemma 13 yields
AI (δ) ≤ B I (δ), AI (δ) ≤ 1 ≤ B I (δ), or q ≤ B I (δ) and (AI (δ))n ≤ B I (δ),
depending on S(A, B). In the last case, we have either AI (δ) < b ≤ B I (δ), or
AI (δ) ≥ b and then AI (δ) = (AI (δ))n ≤ B I (δ).
[only if] Assume first that S(A, B) contains a constant q with b ≤ q < 1. In
this case, every monomial in S(A, B) must be of the form q 0 ⊗ xnA with q 0 < 1.
For all these monomials, it holds that q 0 ⊗ q n = q 0 ⊗ q < q. By Lemma 14,
this implies A 6v1T B. Otherwise, if S(A, B) contains a constant q, then it must
satisfy q < b. For all monomials q 0 ⊗ xnA ∈ S(A, B) it then holds that q 0 < 1 or
n ≥ 2. If q 0 < 1, then we have q 0 ⊗ pn ≤ q 0 ⊗ p < p for all p ∈ (0, 1]. If n ≥ 2, then
q 0 ⊗ pn ≤ pn < p holds for all idempotent elements p ∈ (0, b). Thus, we have
p > maxq0 ⊗xnA ∈S(A,B) q 0 ⊗ pn for all p ∈ (q, b), where we set q := 0 if S(A, B)
does not contain any constant. Again, Lemma 14 yields A 6v1T B. t
u
For t-norms with b = 1, this means that we can restrict the completion algorithm
to consider only 1 and xA for the sets S(A, B). Once a smaller constant or a larger
exponent for xA is introduced, it can never lead to another entry of the form 1 or
xA , and is thus not necessary to decide 1-subsumption. A special case is the rule
(CR3) for m = 0, since then also a smaller monomial in R(A, r, B) can cause 1
to be added to S(A, D). However, this does not depend on the actual monomial
in R(A, r, B), but only on its existence. Since entries in R(A, r, B) can only be
produced by (CR2), retaining the information whether S(A, B) or R(A, r, B)
contain some non-zero monomial is sufficient. As there are only polynomially
many sets S(A, B) and R(A, r, B), and for each set we need to retain 3 bits of
information, 1-subsumptions can be decided in polynomial time if b = 1.
For t-norms with b < 1, deciding 1-subsumption additionally depends on
the constants in S(A, B). However, as above, we can compute all constants for
S(A, B) and R(A, r, B) while only retaining those constants and the information
whether the sets contain a non-constant monomial. Furthermore, we can stop the
computation of larger constants for S(A, B) once we have exceeded b. Once we
have computed these constants, we can proceed as follows. For the sets S(A, B)
containing no constant greater or equal b, we simply have to decide whether they
contain 1 or xA as above. For the other sets, the exponents of the monomials
q 0 ⊗ xnA are irrelevant since either the value of A is below b, and thus below the
value of B, or the value of A is above b, and then multiplying it with itself does
Table 2. A summary of the complexity results
positive subs. p-subs. 1-subs. 1-subs. w.r.t. crisp roles,
normalized TBoxes
in PTime not ((0, b)⊗Ł ) — — not ((0, b), ⊗Ł )
co-NP-hard ((0, b), ⊗Ł ) ((a, b), ⊗Ł ) ((a, 1), ⊗Ł ) —
not change it. Thus, we can apply (CR1)–(CR3) while treating all non-zero
exponents n as 1. Since again it suffices to restrict to those monomials q 0 ⊗ xA
with q 0 = 1, 1-subsumptions can also be decided in polynomial time if b < 1.
Corollary 16. If ⊗ does not start with Łukasiewicz, then 1-subsumption be-
tween concept names in ⊗-EL w.r.t. normalized TBoxes and crisp roles is decid-
able in polynomial time.
Consider in particular any t-norm ⊗ that ends with (but does not start with) the
Łukasiewicz t-norm. From Corollary 16, we know that 1-subsumption of concept
names in ⊗-EL is decidable in polynomial time, if the TBox is normalized, and
reasoning is restricted to crisp roles. On the other hand, by Corollary 7 and
Theorem 8, we know that 1-subsumption w.r.t. general TBoxes is co-NP-hard
in this logic. Moreover, the constructions used for these results do not use any
roles, and hence the restriction to crisp roles does not affect the hardness. This
means that general TBoxes are strictly more expressive than normalized ones.
5 Conclusions
We have analyzed subsumption problems in fuzzy EL with t-norm semantics. For
the complexity of deciding positive subsumption, there is a dichotomy between
co-NP-hard for t-norms that start with Łukasiewicz and polynomial for t-norms
that do not. For the latter case, positive subsumption is linearly reducible to
subsumption in classical EL. This dichotomy is akin the complexity of deciding
TBox consistency in expressive fuzzy DLs: for t-norms starting with Łukasiewicz,
the problem is undecidable [6,7,11], but linearly reducible to classical reasoning
for all other t-norms [4,5].
Deciding p-subsumption exhibits a different complexity pattern. There, the
co-NP lower bound holds for any t-norm containing Łukasiewicz. We have not
been able to obtain complexity results for other t-norms, beyond the previously
known case of the Gödel t-norm. For 1-subsumption we have shown intractability
for any t-norm ending with Łukasiewicz. These results are summarized in Table 2.
We have also presented a completion algorithm for deciding 1-subsumption
w.r.t. normalized TBoxes, if the semantics is restricted to crisp roles and the
t-norm does not start with Łukasiewicz. This is only a first step towards an
algorithm capable of deciding p-subsumption in general. Due to our hardness
results, we cannot expect to find a polynomial-time algorithm capable of classi-
fying TBoxes that are not in normal form. As future work, we plan to further
understand the cases where reasoning becomes intractable, and develop algo-
rithms that match the theoretical complexity of these problems.
References
1. Baader, F., Brandt, S., Lutz, C.: Pushing the EL envelope. In: Kaelbling, L.P.,
Saffiotti, A. (eds.) Proc. of the 19th Int. Joint Conf. on Artificial Intelligence (IJ-
CAI’05). pp. 364–369 (2005)
2. Baader, F., Calvanese, D., McGuinness, D.L., Nardi, D., Patel-Schneider, P.F.
(eds.): The Description Logic Handbook: Theory, Implementation, and Applica-
tions. Cambridge University Press, 2nd edn. (2007)
3. Bobillo, F., Straccia, U.: Finite fuzzy description logics and crisp representations.
In: Bobillo, F., da Costa, P.C.G., d’Amato, C., Fanizzi, N., Laskey, K., Laskey,
K., Lukasiewicz, T., Nickles, M., Pool, M. (eds.) Uncertainty Reasoning for the
Semantic Web II, Lecture Notes in Computer Science, vol. 7123, pp. 102–121.
Springer-Verlag (2013)
4. Borgwardt, S., Distel, F., Peñaloza, R.: Gödel negation makes unwitnessed consis-
tency crisp. In: Kazakov, Y., Lembo, D., Wolter, F. (eds.) Proc. of the 25th Int.
Workshop on Description Logics (DL’12). CEUR Workshop Proceedings, vol. 846,
pp. 103–113 (2012)
5. Borgwardt, S., Distel, F., Peñaloza, R.: How fuzzy is my fuzzy description logic?
In: Gramlich, B., Miller, D., Sattler, U. (eds.) Proc. of the 6th Int. Joint Conf.
on Automated Reasoning (IJCAR’12). Lecture Notes in Artificial Intelligence, vol.
7364, pp. 82–96. Springer-Verlag (2012)
6. Borgwardt, S., Peñaloza, R.: Non Gödel negation makes unwitnessed consistency
undecidable. In: Kazakov, Y., Lembo, D., Wolter, F. (eds.) Proc. of the 25th Int.
Workshop on Description Logics (DL’12). CEUR Workshop Proceedings, vol. 846,
pp. 411–421 (2012)
7. Borgwardt, S., Peñaloza, R.: Undecidability of fuzzy description logics. In: Brewka,
G., Eiter, T., McIlraith, S.A. (eds.) Proc. of the 13th Int. Conf. on Principles
of Knowledge Representation and Reasoning (KR’12). pp. 232–242. AAAI Press
(2012)
8. Borgwardt, S., Peñaloza, R.: The complexity of lattice-based fuzzy description
logics. Journal on Data Semantics 2(1), 1–19 (2013)
9. Borgwardt, S., Peñaloza, R.: Positive subsumption in fuzzy EL with general t-
norms. In: Proc. of the 23rd Int. Joint Conf. on Artificial Intelligence (IJCAI’13).
AAAI Press (2013), to appear.
10. 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.)
Proc. of the 16th Eur. Conf. on Artificial Intelligence (ECAI’04). pp. 298–302. IOS
Press (2004)
11. Cerami, M., Straccia, U.: On the (un)decidability of fuzzy description logics under
Łukasiewicz t-norm. Information Sciences 227, 1–21 (2013)
12. Hájek, P.: Metamathematics of Fuzzy Logic (Trends in Logic). Springer-Verlag
(2001)
13. Hájek, P.: Making fuzzy description logic more general. Fuzzy Sets and Systems
154(1), 1–15 (2005)
14. Karp, R.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher,
J.W. (eds.) Proc. of a Symp. on the Complexity of Computer Computations, pp.
85–103. Plenum Press (1972)
15. Klement, E.P., Mesiar, R., Pap, E.: Triangular Norms. Trends in Logic, Studia
Logica Library, Springer-Verlag (2000)
16. Mailis, T., Stoilos, G., Simou, N., Stamou, G., Kollias, S.: Tractable reasoning with
vague knowledge using fuzzy EL++ . Journal of Intelligent Information Systems 39,
399–440 (2012)
17. Mostert, P.S., Shields, A.L.: On the structure of semigroups on a compact manifold
with boundary. Annals of Mathematics 65(1), 117–143 (1957)
18. Straccia, U.: Reasoning within fuzzy description logics. Journal of Artificial Intel-
ligence Research 14, 137–166 (2001)
19. Tresp, C.B., Molitor, R.: A description logic for vague knowledge. In: Prade, H.
(ed.) Proc. of the 13th Eur. Conf. on Artificial Intelligence (ECAI’98). pp. 361–365.
John Wiley and Sons (1998)
20. Zhou, Z., Qi, G., Liu, C., Hitzler, P., Mutharaju, R.: Reasoning with fuzzy-
EL+ ontologies using mapreduce. In: Luc De Raedt, Christian Bessiere,
D.D.P.D.P.F.F.H.P.L. (ed.) Proc. of the 20th Eur. Conf. on Artificial Intelligence
(ECAI’12). Frontiers in Artificial Intelligence and Applications, vol. 242, pp. 933–
934. IOS Press (2012)