Fuzzy Description Logics have been proposed as formalisms for representing and reasoning about imprecise knowledge by introducing intermediate truth degrees. Unfortunately, it has been shown that reasoning in these logics easily becomes undecidable, when infinitely many truth degrees are considered and conjunction is not idempotent. In this paper, we take those results to the extreme, and show that subsumption in fuzzy EL under Łukasiewicz semantics is undecidable. This provides the first instance of a Horn-style logic with polynomial-time reasoning whose fuzzy extension becomes undecidable.
Introduction
An important problem for practical AI applications is to represent and reason
with imprecise knowledge in a formal way. Fuzzy Description Logics (FDLs) [
9hasDisease:Flu v 9hasSymptom:Headache u 9hasSymptom:Fever;
which may occur in a medical ontology like SNOMED CT.4 The severity of the
symptoms is certainly an indicator for the severity and progression of the disease,
which means that truth degrees can be transferred between concepts. However,
there are different choices of possible semantics for the logical constructors. The
most general semantics are based on triangular norms (t-norms) that are used to
interpret conjunctions [
Unfortunately, reasoning in many FDLs becomes undecidable [
Preliminaries In this section, we briefly recall the extension of EL under Łukasiewicz semantics, denoted by Ł-EL. Let NI, NC, and NR be countable sets of individual, concept, and role names, respectively. Ł-EL concepts are built from these sets through the grammar rule C; D ::= > j A j C u D j 9r:C, where A 2 NC and r 2 NR. That is, the syntax of Ł-EL concepts is the same as for classical EL.
Semantically, Ł-EL differs from EL by considering all the values in the interval [0; 1] as truth degrees. These degrees are managed with the help of the Łukasiewicz t-norm ( Ł) and its residuum ()Ł), which are defined for every x; y 2 [0; 1] by: x Ł y := maxf0; x + y x )Ł y := minf1; 1
1g;
x + yg:
Some important properties of these operators are given the in following
proposition (see [
Proposition 1. For all x; y; x0; y0 2 [0; 1], it holds that (a) x Ł y = 1 iff both x = 1 and y = 1; (b) if x x0 and y y0, then x y x0 y0; (c) if x Ł x x Ł x Ł x, then either x 21 or x = 1; (d) x )Ł y = 1 iff x y; (e) 1 )Ł y = y; (f) x )Ł y = supfz 2 [0; 1] j x Ł z yg. (g) x )Ł 0 = 1 x.
A (fuzzy) interpretation is a pair I = ( I ; I ) where I is a non-empty set, called the domain, and I is a fuzzy interpretation function that assigns – to each individual name a 2 NI an element aI 2 – to each concept name A 2 NC a fuzzy set AI :
I , I ! [0; 1], and – to each role name r 2 NR a fuzzy relation rI :
This function is extended to arbitrary concepts by setting, for all x 2 I , >I (x) := 1; (C u D)I (x) := CI (x) Ł DI (x); (9r:C)I (x) := sup rI (x; y) Ł CI (y):
y2 I Notice that, according to this semantics, the concepts C and C u C are not equivalent. We will exploit this fact in the following sections, and often use the abbreviation Cm, m 1, for the m-ary conjunction; i.e. C1 := C and Cm+1 := Cm u C. We then have that (Cm)I (x) = maxf0; m CI (x) (m 1)g.
Fuzzy interpretations are often restricted to be witnessed [
In FDLs, axioms are usually assigned a minimum degree of truth to which they must be satisfied. Hence, (fuzzy) general concept inclusions (GCIs) are of the form hC v D pi, where C and D are concepts and p 2 (0; 1]. A fuzzy interpretation I satisfies this axiom if CI (x) ) DI (x) p holds for all x 2 I . A TBox is a finite set of GCIs, and a fuzzy interpretation I satisfies a TBox if it satisfies every axiom in it. A crisp GCI is of the form hC v D 1i, and we usually abbreviate such an axiom by hC v Di, which has the semantics that CI (x) DI (x) for all x 2 I (see Proposition 1(d)). We also use hC Di as a short-hand for the two axioms hC v Di and hD v Ci. Our goal is to analyze the computational complexity of deciding subsumption in fuzzy DLs. A concept C is subsumed by a concept D with respect to a TBox T if every fuzzy interpretation I that satisfies T also satisfies the GCI hC v Di.
We show that subsumption in Ł-EL is undecidable, using the framework
from [
In Section 5, we show how to modify this result to apply it to subsumption in Ł-EL (without equality assertions, but with non-crisp GCIs). This is the first instance of undecidability for a fuzzy description logic that does not allow for any negation constructor (and not even ?). Indeed, the required expressivity is a consequence of the properties of the Łukasiewicz t-norm itself. 3
A General Framework for Undecidability
As we will use the framework originally presented in [
The first requirement of the framework is to provide an encoding function enc : 0 ! [0; 1] that allows us to represent words over the alphabet 0 := [f0g as truth degrees. For this encoding function to be valid (see [7, Definition 11]), there must exist two words u"; u+ 2 0 such that every candidate solution 2 f1; : : : ; ng satisfies the following properties: – The word u" uj+j belongs to f"g [ 0, that is, it does not start with 0. – Setting p = enc(v ), q = enc(w ), and m = enc(u" uj+j), we have v 6= w iff minfp ) q; q ) pg m: This means that one can use the encoding of u" uc+ to check the (in)equality of any two words v ; w belonging to a candidate solution of length c. Based on this encoding function, the following canonical model IP of P is used to encode the search tree for a solution of P, as illustrated in Figure 1: – the domain IP := f1; : : : ; ng contains all candidate solutions for P; – we set aIP := " for a distinguished individual name a that denotes the root node of the search tree; – V IP ( ) := enc(v ) and W IP ( ) := enc(w ) represent the words v and w , respectively, of the candidate solution at a node 2 f1; : : : ; ng ; – ViIP ( ) := enc(vi) and WiIP ( ) := enc(wi) for i 2 f1; : : : ; ng encode the words vi and wi, respectively, at every node of the search tree; 5 Without loss of generality, we can restrict to solutions that start with v1 and w1.
V : enc(v1v1), W : enc(w1w1), M : enc(u"u+) . .
.
V : enc(v v1),
W : enc(w w1), M : enc(u" uj+j+1) r1 r1
r2 V : enc(v1v2), W : enc(w1w2), M : enc(u"u+) . .
.
V : enc(v ),
W : enc(w ), M : enc(u" uj+j)
rn rn
V : enc(v1vn), W : enc(w1wn), M : enc(u"u+) . .
.
V : enc(v vn),
W : enc(w wn),
M : enc(u" uj+j+1)
Strictly speaking, this construction is slightly different from the one described
in [
The following property expresses that the logic is capable of constructing the canonical model.
The Canonical Model Property :
There is an ontology OP such that every model I of OP admits a mapping g : IP ! I that satisfies
AIP ( ) = AI (g( )) and
HI (g( )) = h for every A 2 fV; W; M; M+g [ Sin=1fVi; Wig and 2 f1; : : : ; ng .
In other words, the ontology OP required by this property enforces that the canonical model can be embedded into every interpretation satisfying it. As shown in [7, Theorem 12], the canonical model property is implied by the following four simpler properties, which are used, in that order, to initialize the values of the concept names at the root node, to enforce the existence of the ri-successors, to construct the encodings of the next candidate solutions (v i; w i) by concatenation, and to transfer these encodings along the ri-connections to the successors.
The Initialization Property :
Let C be a concept, a 2 NI, and u 2 0. There is an ontology O such that for every model I of O it holds that CI (aI ) = enc(u).
Let r 2 NR. There is an ontology O such that for every model I of O and every x 2 I with HI (x) = h there is a y 2 I with rI (x; y) = 1 and HI (y) = h.
Let u 2 0, and C and Cu be concepts. There is an ontology O and a concept name D such that for every model I of O and every x 2 I , if CuI (x) = enc(u) and CI (x) = enc(u0) for some u0 2 f"g [ 0, then DI (x) = enc(u0u).
Let C; D be concepts and r 2 NR. There is an ontology O such that for every model I of O and every x; y 2 I , if HI (x) = h, rI (x; y) = 1, HI (y) = h, and CI (x) = enc(u) for some u 2 0, then DI (y) = enc(u).
In a logic satisfying these four properties, it is possible to create an ontology OP whose models all embed the search tree for a solution of a PCP instance P. To obtain undecidability, one further needs to guarantee that the existence of such a solution can be decided. We achieve this through the following property, which intuitively states that no node of the search tree is a solution; thus, the ontology is inconsistent if and only if P has a solution [7, Theorem 13]. The Solution Property:
IP can be extended to a model of OP , and there is an ontology O such that: 1. For every model I of OP [ O and every 2 f1; : : : ; ng , min V I (g( )) ) W I (g( )); W I (g( )) ) V I (g( )) We now consider Ł-EL=, and verify that it satisfies all the properties introduced in the previous section. Thus, as explained before, ontology consistency in this logic is undecidable.
Encoding function. To encode the words for the PCP, we use the function enc(u) := 1 12 0: u ; where u is the word u written in reverse and interpreted as a sequence of digits in base s + 1, and 0: u is the number represented by this sequence of digits when written after the decimal point. For example, if s = 9, then we have enc(1) = 0:95 and enc(81) = 0:91. It is an important property of this function that the encoding of every word is always strictly greater than 21 ; that is, enc(u) 2 (0:5; 1] for all words u.
To see that this encoding function is valid, consider an instance P of the PCP, and let k be the maximal length of any word vi; wi appearing in P. Choose u" := 1 0k—that is, the word consisting of the digit 1 followed by k zeros—and u+ := 0k. It can be verified as in [7, Lemma 14] that the two required conditions hold. In particular, if v 6= w , then these words must differ in one of the first K := (j j + 1)k symbols. Thus, either enc(v ) > enc(w ), and hence enc(v ) ) enc(w ) = 1 + 12 0:v or else enc(v ) < enc(w ) and enc(w ) ) enc(v ) enc u" uj+j .
Initialization property. This property follows trivially from the availability of equality assertions in Ł-EL=: we can simply set O := fha:C = enc(u)ig. Successor property. For this, we choose h := 12 as the constant for the concept name H, and consider the ontology fhH G2i; hG v 9r:Gi; h9r:H v Hig. Since we assume that HI (x) = 12 , the first axiom yields that GI (x) = 34 . Then, by the second axiom and the assumption that our interpretations are witnessed, we find an element y 2 I such that 34 rI (x; y) Ł GI (y). By the third axiom, rI (x; y) Ł (G2)I (y) (9r:H)I (x) HI (x) = 21 . Since Ł is monotone (Proposition 1(b)), we get rI (x; y) Ł (G2)I (y) 12 = 34 Ł 4 3 rI (x; y) Ł rI (x; y) Ł (G2)I (y) (1) This implies that rI (x; y) = 1, since otherwise we would have rI (x; y) Ł rI (x; y) Ł (G2)I (y) rI (x; y) Ł 12 = maxf0; rI (x; y) 12 g < 12 ; in contradiction to (1). From this, we obtain HI (y) = (G2)I (y) = 21 , as required. Concatenation property. Consider O := fhC0(s+1)juj Ci; hD C0 u Cuig, where C0 is a fresh auxiliary concept name. Let I be a model of O and x 2 I such that CuI (x) = enc(u) and CI (x) = enc(u0) for some u0 2 f"g[ 0. Suppose first that u0 6= ". Then from the first axiom it follows that both CI (x) and C0I (x) belong to the interval (0; 1), and hence C0I (x) = 1 then (s+1) juj 0:u0 . If u 2= f0g , 2 DI (x) = 1 Otherwise, CuI (x) = 1 and thus DI (x) = C0I (x) = enc(u0u). If u0 = ", then CI(x) = 1 which implies that C0I (x) = 1 by Proposition 1(a), and hence DI(x) = enc(u) = enc("u).
Transfer property. Consider concepts C; D, a role name r, and let C be a fresh concept name. For every model I of hH C u Ci and every x 2 I with HI(x) = 12 and CI(x) = enc(u) 2 ( 12 ; 1], we get
CI(x) + CI(x) 1 = HI (x) = 12 ; and hence CI (x) = 32 CI (x) 2 and CI (x) = 32 CI (x). That is, C simulates an involutive negation of C. Since HI(y) = 21 , we can similarly use the axiom hH D u Di to simulate the involutive negation of D at y, i.e. DI(y) = 32 DI (y).
Consider now the axioms h9r:D v Ci and h9r:D v Ci. The first axiom implies that DI (y) = rI (x; y) Ł DI(y) (9r:D)I (x) CI(x). From the second axiom, we similarly get that 32 DI(y) = DI (y) CI(x) = 23 CI (x), and thus DI (y) = CI(x) = enc(u).
We obtain the required ontology OP by collecting all the axioms introduced for the four properties described above.
Solution property. The first part of this property, namely that IP can be
extended to a model of OP , can easily be verified as in [
X u Xi; hX2 u V v W u M i; hX2 u W v V u M ig (2) (3) (4) Since HI (g( )) = 21 , the canonical model property implies that for every model I of (2) it holds that XI (g( )) 2 f 21 ; 1g and XI (g( )) 2 f 12 ; 1g (see Proposition 1(c)). Furthermore, X and X complement each other, i.e. XI (g( )) = 12 iff XI (g( )) = 1.
Let I be a model of OP [ O and 2 f1; : : : ; ng . If XI(g( )) = 1, then the axiom (3) implies that V I (g( )) W I(g( )) Ł M I (g( )), while (4) is trivially satisfied since (X2)I (g( )) = 0. Consider again K = (j j + 1)k from above. Since jw j K, we have
W I(g( )) Ł M I (g( )) = 1 Since Ł is strictly increasing in that interval, for any z > M I(g( )) we know that W I (g( )) z > V I (g( )). By Proposition 1(f), we obtain
W I (g( )) ) V I(g( )) = supfz 2 [0; 1] j W I (g( )) Ł z
V I(g( ))g inffz 2 [0; 1] j z > M I (g( ))g = M I (g( )): Dually, if XI (g( )) = 12 , then V I (g( )) ) W I (g( )) M I (g( )). Thus, minfV I (g( )) ) W I (g( )); W I (g( )) ) V I (g( ))g
Assume now that minfV IP ( ) ) W IP ( ); W IP ( ) ) V IP ( )g M IP ( ), and let I be an extension of IP that satisfies OP . We show that I can be extended to satisfy O. We only need to provide the adequate interpretation of the concept names X and X on the elements 2 f1; : : : ; ng . If V IP ( ) ) W IP ( ) = 1, we set XI ( ) := 1, which requires XI ( ) := 12 and trivially satisfies (4). We must then have W IP ( ) ) V IP ( ) M IP ( ), which shows that (3) is also satisfied. In the remaining case, setting XI ( ) := 21 yields the desired result.
Undecidability now follows from [7, Theorem 13]; note that in the above constructions we used only crisp GCIs.
Theorem 2. Ontology consistency in Ł-EL= is undecidable. This undecidability result holds even if all GCIs are crisp.
We emphasise here that Theorem 2 improves on previous undecidability results for fuzzy DLs, where the presence of some kind of negation concept constructor was always required. 5
Subsumption is Undecidable We now turn our attention to the problem of deciding subsumption between two concepts. Notice first that we can use the results from the previous section to show directly that subsumption in Ł-EL= is undecidable. Indeed, consider an arbitrary Ł-EL= ontology O and let A be a concept name not appearing in O. Then, > is subsumed by A w.r.t. O iff O is inconsistent. We are interested, however, in the problem of deciding subsumption w.r.t. a TBox, without any assertions.
We now use Theorem 2 to show that subsumption in Ł-EL is also undecidable.
Notice first that in the construction from Section 4, the equality assertions are
only used for the initialization property. In the overall proof of undecidability
from [
Lemma 3. Given a concept C and u 2 0, there exists a TBox T such that for every model I of T [ fha:Y = 21 ig it holds that CI (aI ) = enc(u). Proof. For any model I of T0 := fhY 2 v Y 3i; h> v H 12 i; hH Y u Y ig and ha:Y = 12 i, it holds that 12 HI (aI ) (Y u Y )I (aI ) Y I (aI ) = 12 . In particular, this initializes the concept name H as desired. In addition, we have that Y I (aI ) = 1. To ensure CI (aI ) 2 enc(u), let T := T0 [ fhH A(s+1)juj i, hY 2 u C Y 2 u A u ig, where A is an auxiliary concept name. The first axiom implies that (s+1)juj(AI (aI ) 1)+1 = 12 , and thus AI (aI ) = 1 2(s+11)juj . Since (Y 2)I (aI ) = 1, the second axiom entails that either CI (aI ) and (A u )I (aI ) are both equal to 1, or CI (aI ) = (A u )I (aI ) < 1. If u 2 f0g , then A u is equivalent to >, and hence we get CI (aI ) = 1 = enc(u). Otherwise, we obtain CI (aI ) = (A u )I (aI ) = 1 12 0: u = enc(u).
We have hence re-proven the canonical model property and obtained undecidability of consistency in Ł-EL= with only one equality assertion (ha:Y = 12 i).
We now use this to prove undecidability of subsumption in Ł-EL.6 Consider the ontology OP used in the new proof of undecidability of Ł-EL=, and define = 21 ig. Due to the axioms hY 2 v Y 3i, hH Y u Y i, and TP := OP n12if,htah:eYinterpretation of Y in a model of TP is always in f 12 ; 1g. Hence, h> v H OP is consistent iff > is not subsumed by Y w.r.t. TP (since in the latter case there must be a model I of TP such that Y I (x) = 21 for some domain element x 2 I , i.e. x can serve the function of aI ).
Theorem 4. Subsumption in Ł-EL is undecidable.
Interestingly, this provides the first known instance of a Horn-like logic allowing for polynomial-time reasoning, whose fuzzy extension becomes undecidable. 6
Discussion and Related Work
While the results presented in Theorems 2 and 4 are significant by themselves, it
is possible to generalize their proofs to infinitely many other continuous t-norms.
Specifically, subsumption in -EL is undecidable for every t-norm that contains
the Łukasiewicz t-norm, i.e. is isomorphic to Ł on some interval [a; b] [0; 1],
(see [
These arguments similarly apply to ontology consistency in -EL= with crisp
GCIs; that is, consistency in all these logics is undecidable. Hence, we have
significantly strengthened an undecidability result from [
We now briefly discuss some related work dealing with other semantics for fuzzy DLs.
Product t-norm. In contrast, for the product t-norm defined by x y := x y,
ontology consistency in -NEL with crisp assertions is decidable. It is still unknown,
however, whether equality assertions make consistency in -EL= or -NEL=
undecidable. The same question remains open for t-norms that contain (but
not Ł). As a partial result, we can adapt our undecidability proof to show that
-ELU= becomes undecidable, where the semantics of the additional disjunction
constructor is defined as (C t D)I (x) := 1 (1 CI (x)) (1 DI (x)). This
also slightly strengthens previous results from [
Open problems. The results in this paper show that infinitely-valued fuzzy semantics can make reasoning even in fairly inexpressive logics undecidable. Although the boundaries of decidability and undecidability in fuzzy DLs have been extensively mapped, there are a few remaining open problems. A problem that remains open from this work is whether undecidability in Ł-EL requires fuzzy GCIs. In addition, other inexpressive DLs like FL0 or members of the DL-Lite family may provide examples where reasoning remains decidable, despite the use of intermediate truth degrees. 7 The details of these proofs are in a manuscript currently under review. 20. Mailis, T., Stoilos, G., Simou, N., Stamou, G.B., Kollias, S.: Tractable reasoning with vague knowledge using fuzzy EL++. Journal of Intelligent Information Systems 39(2), 399–440 (2012) 21. Post, E.L.: A variant of a recursively unsolvable problem. Bulletin of the American
Mathematical Society 52(4), 264–268 (1946) 22. Straccia, U.: Reasoning within fuzzy description logics. Journal of Artificial Intelligence Research 14, 137–166 (2001)