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 threeweek-old belongs to this period only with degree 0:3. In Mathematical Fuzzy Logic, the interpretation of the logical constructors, such as conjunction, disjunction, 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].
Introduction ? 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’
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 subsumption 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 [
Let ((ai; bi))i2I be a (possibly infinite) family of non-empty, disjoint open subintervals of [0; 1] and ( i)i2I be a family of continuous t-norms over the same index set I. The ordinal sum of (((ai; bi); i))i2I is the t-norm , where x y := ai + (bi
x ai ai) bi ai
y ai i bi ai if x; y 2 [ai; bi] for some i 2 I, and x y := minfx; yg otherwise. This yields a continuous t-norm, whose residuum x ) y is given by 8 >1 > < > >:y ai + (bi
y ai
ai) bxi aaii )i bi ai
if x
if ai
otherwise,
y,
y < x
bi,
where )i is the residuum of i, for each i 2 I [
Let be a continuous t-norm and (((ai; bi); i))i2I be its representation as ordinal sum given by Theorem 1.3 We call (((ai; bi); i))i2I 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 2 [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 2 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 (9r:C). Cn denotes the n-ary conjunction of a -EL-concept C with itself; Cn := uin=1C. A -EL-TBox is a finite set of general concept inclusion axioms (GCIs) of the form hC v D qi, where C; D are -EL-concepts and q 2 [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 2 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 2 , >I ( ) := 1, (C1 u C2)I ( ) := C1I ( ) C2I ( ), and (9r:C)I ( ) := sup 2 I rI ( ; ) CI ( ): An interpretation I satisfies the GCI hC v D qi iff (CI ( ) ) DI ( )) q for all 2 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 ( ) 2 f0; 1g and rI ( ; ) 2 f0; 1g hold for every concept name A, role name r, and ; 2 I .
Example 2. The concept of perinatal cyanotic attacks (PCA) can be described
using the GCI
hPCA v CardiovascDisorder u 9occur:PerinatalPeriod u 9manif: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
describe 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 9occur:PerinatalPeriod
hPCA v 9manif:Cyanosis 1i:
1i;
In fuzzy DLs, reasoning is sometimes restricted to witnessed interpretations [
As in classical EL, every -EL-TBox has the trivial model I = (f g; I ) where AI ( ) = 1 for every concept name A and rI ( ; ) = 1 for every role name r. Thus, 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 2 (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 vT>0 D) if every model I of T and every 2 I satisfies CI ( ) ) DI ( ) > 0. The best subsumption degree of p Dg.
C v D w.r.t. T is bsdT (C v D) := supfp 2 [0; 1] j C vT Clearly, if bsdT (C v D) > 0, then C vT>0 D. However, the converse does not necessarily hold, as evidenced by the following example.
Example 4. Consider the product t-norm and A 2 NC. For every interpretation I and 2 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 = (f g; 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 [
Definition 5. Let V = fv1; : : : ; vmg 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 2 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 equivalently ask for a vertex cover of size exactly k. We assume without loss of generality 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 = jV j, i.e. we have a concept name Vi for every vi 2 V , and an additional concept name V0. For each i; 1 i m, we set Ti := fhVim k v Vim k+1 1i; h> v Vi m k 1 m k ig and T0 := fh> v V0 mm kk 1 ig. Every model I of Sim=0 Ti and that V0I ( ) mm kk 1 and ViI ( ) 2 f mm kk 1 ; 1g for 1 i
m. We now define m TV := [ Ti [ fhA v V0m k 1 i=0 1i; hV1 u : : : u Vm v B 1ig [ fhV0 v Vj1 u Vj2 1i j fvj1 ; vj2 g 2 Eg: (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 = fvi1; : : : ; vikg be a vertex cover of size k. Build the interpretation IS := (f g; IS ) with AIS ( ) := 1=m k, BIS ( ) := 0, V0IS ( ) := m k m k 1 , and for i; 1 i m,
ViIS ( ) := (1 m k 1 m k if vi 2 S otherwise.
It is easy to verify that IS is a model of TV and AIS ( ) ) BIS ( ) = mm kk 1 < 1.
Conversely, let I be a model of TV and 2 I with AI ( ) > BI ( ). In particular, AI ( ) 1=m k, since otherwise, BI ( ) = 1. We can now define SI := fvi j ViI ( ) = 1; 1 i mg: Since V1I ( ) : : : must be at least m k concept names Vj such that VjI ( )V=mI (mm) k<k 11=,mankd, htehnecree SI has at most k elements. Moreover, since I satisfies the axioms in (1), for every fvj1 ; vj2 g 2 E, at least one of VjI1 ( ); VjI2 ( ) is 1. Thus, SI is a vertex cover. tu 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 ([
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 ([
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 -EL is co-NP-hard.
contains the Łukasiewicz t-norm, then p-subsumption in 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 [
T >0 := fhC v D 1i j hC v D qi 2 T ; q > 0g that describes all positive subsumption relations.
Theorem 11 ([
The latter condition in this theorem is equivalent to subsumption between C0
and D0 in classical EL, which can be decided in polynomial time [
A Completion Algorithm for 1-Subsumption
We now develop a completion algorithm in the style of [
R(A; r; C). (CR3) If q1 xnA 2 R(A; r; B), q2 xBm 2 S(B; C), and h9r:C v D add (p q1m q2) xnAm to S(A; D).
pi 2 T , then add (p q)
xnA to pi 2 T , then Given such a TBox T , we compute for every A; B 2 N>, and r 2 NR sets C 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 2 [0; 1]. The idea is that, whenever the value of A is p 2 [0; 1], then q xnA 2 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 2 R(A; r; B), then the value of 9r: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 9r:B).
We define an order on such monomials as follows. Given p; q 2 [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 2 [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) := fxAg, and S(A; >) := S(>; >) := f1g for all A 2 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 [
Note that the sets S(>; B) for B 2 NC> 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 2 N>, and vice versa, by applying the same
C 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 2 NC>. If at some point during the run of the algorithm a monomial q xnA is 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 q0 xAm, where either q0 > q or m < n, can be added to S(A; B). Since q0 also has to be a combination of values occurring in T , there are only finitely many values q0 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 q0 there can only be one m such that q0 xAm 2 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 q0 with this property, and this q0 can only be increased. As mentioned before, there are only finitely many possibilities for q0 inside the same component, and once a new q0 has been computed that lies in another component, there are again only finitely many possible values exceeding q0 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 2 NC>, r 2 NR, I be a model of T , and 2
I . – If q – If q xnA 2 S(A; B) and AI ( ) > 0, then q xnA 2 R(A; r; B) and AI ( ) > 0, then q (AI ( ))n (AI ( ))n
BI ( ).
(9r: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 2 S(A; B1), q2 xAm 2 S(A; B2), hB1 u B2 v C pi 2 T , and AI ( ) > 0. We thus have q1 (AI ( ))n B1I ( ), q2 (AI ( ))m B2I ( ), and p B1I ( ) B2I ( ) CI ( ). It follows that p q1 q2 (AI ( ))n+m p
B1I ( )
B2I ( )
CI ( ); and thus we can add (p q1 q2) xnA+m to S(A; C) without violating the claim.
For (CR2), let q xnA 2 S(A; B), hB v 9r:C pi 2 T , and AI ( ) > 0. By assumption, we have q (AI ( ))n BI ( ) and p BI ( ) (9r:C)I ( ), and thus p q (AI ( ))n (9r:C)I ( ) as required. h9r:FCinvallDy, forpith2e Tca,saenodf (ACI R(3))>,le0t, wq1hichxnAyi2eldRs(qA1; r; B(A)I, (q2))nxBm (29rS:B(B)I;(C))., We first consider the case that m = 0. Since q1 > 0 and does not start with Łukasiewicz, we have (9r:B)I ( ) > 0. Thus, there is a 2 I with rI ( ; ) = 1 and BI ( ) > 0. The assumption yields that q2 CI ( ), and thus (9r:B)I ( ) m = q2 sup rI ( ; ) 2 I sup rI ( ; ) (BI ( ))m 2 I BI( )>0
BI ( ) m sup rI ( ; ) 2 I BI( )>0 This implies that p q1m q2 (AI ( ))nm p q2
(9r:B)I ( ) m Hence, the claim is still satisfied after adding (p q1m We now show that this algorithm is complete for deciding 1-subsumptions. CI ( )
(9r:C)I ( ): p (9r:C)I ( )
DI ( ): q2) xnAm to S(A; D). tu Lemma 14. For every A; B 2 NC> with A v1T B and all p 2 [0; 1], it holds that p
max q xnA2S(A;B) q pn: Proof. We construct a canonical model I of T from which we can read off all r1-2suNbsRu,mAp;tBion2s.NIC>ts, adnodmapi;np0is2 [0I; 1:=], wfAepsejtAC2I(NAC>p); :=p2m[a0x; q1]gx:nAG2Siv(Aen;C)Cq 2 NpnC,, where the empty maximum is 0, and rI (Ap; Bp0 ) := ( 1 if p0 = maxq xnA2R(A;r;B) q 0 otherwise.
pn; Observe that it also holds that >I (Ap) = maxq xnA2S(A;>) q pn since S(A; >) is always f1g. Furthermore, for any A 2 NC> and p 2 [0; 1] we have AI (Ap) =
max q xnA2S(A;A) q pn = maxfS(>; A); pg: 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 2 I . By (CR1), we have p
B1I (Ap0 )
B2I (Ap0 ) = q1 q2
(p0)n+m max max q1 xnA2S(A;B1) q2 xAm2S(A;B2)
p max q xnA2S(A;C) q (p0)n = CI (Ap0 ):
pi 2 T , let p00 := maxq xnA2R(A;r;C) q (p0)n. We get p
BI (Ap0 ) =
max q xnA2S(A;B)
sup Dp000 2 I maxfS(>; C); p00g = CI (Cp00 ) = rI (Ap0 ; Cp00 )
CI (Cp00 ) rI (Ap0 ; Dp000 )
CI (Dp000 ) = (9r:C)I (Ap0 ): p q (p0)n
max q xnA2R(A;r;C) q (p0)n = p00 Finally, for an axiom h9r:C v Di 2 T , let pB := maxq1 xnA2R(A;r;B) q1 for every B 2 NC>. By (CR3), we have (p0)n p (9r:C)I (Ap0 ) =
sup p Bp00 2 I rI (Ap0 ; Bp00 )
CI (Bp00 ) = max p
B2NC>
CI (BpB ) = max max
B2NC> q2 xBm2S(B;C)
p = max max max
B2NC> q1 xnA2R(A;r;B) q2 xBm2S(B;C)
p q2
pBm max max B2NC> q xnA2S(A;D) q (p0)n = DI (Ap0 ): q2 qm 1 (p0)nm p maxfS(>; A); pg = ACI (Ap) BI (1ApB) ,=amndaxaqnyxnAp2S2(A;[B0;)1q]. Tphne.n we havtue Consider now A; B 2 N> with A vT 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 2 [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 Theorem 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 .
C 1 B iff either (i) fxA; 1g\S(A; B) 6= ;, Theorem 15. Let A; B 2 N>. Then A vT or (ii) fq; xnAg S(A; B) for q b and n 2.
Proof. [if] Let I be a model of T and 2 I . We show that AI ( ) BI ( ). If AI ( ) = 0, then this obviously holds. If AI ( ) > 0, then Lemma 13 yields AI ( ) BI ( ), AI ( ) 1 BI ( ), or q BI ( ) and (AI ( ))n BI ( ), depending on S(A; B). In the last case, we have either AI ( ) < b BI ( ), or AI ( ) b and then AI ( ) = (AI ( ))n BI ( ). [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 q0 xnA with q0 < 1. For all these monomials, it holds that q0 qn = q0 q < q. By Lemma 14, 1 B. Otherwise, if S(A; B) contains a constant q, then it must this implies A 6vT satisfy q < b. For all monomials q0 xnA 2 S(A; B) it then holds that q0 < 1 or n 2. If q0 < 1, then we have q0 pn q0 p < p for all p 2 (0; 1]. If n 2, then q0 pn pn < p holds for all idempotent elements p 2 (0; b). Thus, we have p > maxq0 xnA2S(A;B) q0 pn for all p 2 (q; b), where we set q := 0 if S(A; B) does not contain any constant. Again, Lemma 14 yields A 6v1T B. tu 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 q0 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 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 q0 xA with q0 = 1, 1-subsumptions can also be decided in polynomial time if b < 1. Corollary 16. If does not start with Łukasiewicz, then 1-subsumption between concept names in -EL w.r.t. normalized TBoxes and crisp roles is decidable 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 [
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 classifying TBoxes that are not in normal form. As future work, we plan to further understand the cases where reasoning becomes intractable, and develop algorithms that match the theoretical complexity of these problems. 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 Intelligence 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 fuzzyEL+ 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)