Non-Gödel Negation Makes Unwitnessed Consistency Undecidable? Stefan Borgwardt and Rafael Peñaloza {stefborg,penaloza}@tcs.inf.tu-dresden.de Theoretical Computer Science, TU Dresden, Germany Abstract. Recent results show that ontology consistency is undecid- able for a wide variety of fuzzy Description Logics (DLs). Most notably, undecidability arises for a family of inexpressive fuzzy DLs using only conjunction, existential restrictions, and residual negation, even if the ontology itself is crisp. All those results depend on restricting reasoning to witnessed models. In this paper, we show that ontology consistency for inexpressive fuzzy DLs using any t-norm starting with the Łukasiewicz t-norm is also undecidable w.r.t. general models. 1 Introduction Fuzzy Description Logics (DLs) extend the semantics of classical DLs by allow- ing a set of values, typically the real interval [0, 1], to serve as truth degrees. They were introduced for representing and reasoning with vague or imprecise knowledge in a formal way [14,15]. While several decision procedures for fuzzy DLs exist, they usually rely on a restriction of the expressivity: either by allowing only finitely-valued semantics [5,7] or by limiting the terminological knowledge to be acyclic or unfoldable [11,9,4]. Indeed, the only algorithms for fuzzy ALC with general ontologies are based on the very simple Gödel semantics [13,14,15]. It was recently shown that decision procedures for more expressive fuzzy DLs cannot exist since consistency of fuzzy ALC ontologies becomes undecidable in the presence of GCIs whenever any continuous t-norm different from the Gödel t-norm is used [1,2,3,10,8]. Not all the constructors from ALC are needed for proving undecidability. In particular, it was shown in [8] that for a family of t-norms—those t-norms “starting” with the Łukasiewicz t-norm—consistency is undecidable in the logic NEL, which allows only the constructors conjunction, existential restriction, and (residual) negation, even if all the axioms are crisp. The crux of these undecidability results is that they all depend on restricting reasoning to the class of witnessed models. Since the existing reasoning algo- rithms are based also on witnessed models,1 this semantics was a natural choice. However, it could be the case that witnessed models are the cause of undecid- ability and consistency w.r.t. general models is decidable. ? Partially supported by the DFG under grant BA 1122/17-1 and in the Collaborative Research Center 912 “Highly Adaptive Energy-Efficient Computing”. 1 In fact, witnessed models were introduced in [11] to correct the methods from [15]. Although possible, such a scenario would be very surprising since for first- order fuzzy logic, reasoning w.r.t. general models is typically harder than rea- soning w.r.t. witnessed models [12]. In this paper we show that this is also the case for the logic NEL over any t-norm starting with the Łukasiewicz t-norm: consistency of crisp ontologies w.r.t. general models is undecidable. 2 Preliminaries We briefly introduce the family of t-norms starting with the Łukasiewicz t-norm, which will provide the semantics for the fuzzy DLs Ł(0,b) -NEL. 2.1 The Łukasiewicz t-norm Mathematical fuzzy logic generalizes the classical logical operators to deal with truth degrees from the interval [0, 1]. A t-norm is an associative and commutative binary operator on [0, 1] that has 1 as its unit and is monotonic in both argu- ments. If a t-norm ⊗ is continuous, then there is a unique binary operator ⇒, called the residuum, that satisfies z ≤ x ⇒ y iff x⊗z ≤ y for all x, y, z ∈ [0, 1]. In that case, for all x, y ∈ [0, 1] we have (i) x ⇒ y = 1 iff x ≤ y and (ii) 1 ⇒ y = y. Another useful operator is the unary residual negation x := x ⇒ 0. We focus on the family of t-norms starting with the Łukasiewicz t-norm. The Łukasiewicz t-norm, defined by x ⊗ y = max{0, x + y − 1}, has the residuum x ⇒ y = min{1, 1 − x + y} and residual negation x = 1 − x. A t-norm ⊗ starts with the Łukasiewicz t-norm if there is a b ∈ (0, 1] such that for all x, y ∈ [0, b] we have x ⊗ y = max{0, x + y − b}. Intuitively, such a t-norm behaves like a scaled-down version of the Łukasiewicz t-norm in the interval [0, b]. All continuous t-norms that do not start with the Łukasiewicz t-norm have one characteristic in common: their residual negation is always the Gödel nega- tion that simply maps 0 to 1 and every other truth degree to 0. In contrast, those that do start with the Łukasiewicz t-norm do not have the Gödel negation, but rather a scaled-down version of the Łukasiewicz negation, also known as the in- volutive negation. To be more precise, the residuum and residual negation of a t-norm starting with the Łukasiewicz t-norm satisfy x ⇒ y = b − x + y whenever 0 ≤ y < x ≤ b, and  1  if x = 0 x = b − x if 0 < x ≤ b  0 otherwise.  For the rest of this paper, we assume that ⊗ is a t-norm starting with the Łukasiewicz t-norm in the interval [0, b], for some arbitrary but fixed b ∈ (0, 1], and ⇒, are its residuum and residual negation, respectively. 2.2 The Fuzzy Description Logic Ł(0,b) -NEL Syntactically, Ł(0,b) -NEL extends the DL EL with the unary residual nega- tion constructor . More precisely, concepts are built using the syntactic rule C ::= A | > | C u D | C | ∃r.C. The semantics of Ł(0,b) -NEL is based on interpretations I = (DI , ·I ) consisting of a domain DI and an interpreta- tion function that maps each concept name A to a function AI : DI → [0, 1], each role name r to rI : DI × DI → [0, 1], and each individual name a to an element aI of DI . This function is extended to complex concepts as fol- lows: >I (x) = 1, (C u D)I (x) = C I (x) ⊗ DI (x), ( C)I (x) = C I (x), and (∃r.C)I (x) = supy∈DI rI (x, y) ⊗ C I (y) for all x ∈ DI . In contrast to traditional semantics based on witnessed models, it is possible to have an interpretation I such that (∃r.>)I (x) = 1 but where there is no y ∈ DI with rI (x, y) = 1. It can only be guaranteed that x has r-successors with degrees arbitrarily close to 1. This fact will produce some technical difficulties for our undecidability proof, since we it is not possible to guarantee a specific degree of membership for an r-successor of a given node (see Section 3.5). We will use the following abbreviations: C 0 := >, and C k+1 := C k u C for any k ∈ N; C → D := (C u D); and C  D := (C u D) → D. It can easily be verified that, whenever C I (x), DI (x) ∈ [0, b] for an interpretation I and x ∈ DI , then we have (C k )I (x) = max{0, k(C I (x) − b) + b} for every k > 0, (C → D)I (x) = C I (x) ⇒ DI (x), and (C  D)I (x) = min{C I (x), DI (x)}. An ontology is a finite set of assertions of the form a : C or (a, b) : r and GCIs of the form C v D, where a, b are individual names, and C, D are concepts. An interpretation I satisfies the assertion a : C (resp. (a, b) : r) if C I (aI ) = 1 (resp. rI (aI , bI ) = 1); it satisfies the GCI C v D if C I (x) ≤ DI (x) for every x ∈ DI . The expression C ≡ D abbreviates the two GCIs C v D and D v C. It follows that an interpretation I satisfies C ≡ D iff C I (x) = DI (x) for every x ∈ DI . It is a model of an ontology O if it satisfies all the axioms in O. An ontology is called consistent if it has a model. Notice that we consider only crisp axioms; i.e. they contain no associated fuzzy degree. We will show that reasoning with this restricted form of ontologies, which is the same used for classical (crisp) DLs, is already undecidable. To show the undecidability of ontology consistency in Ł(0,b) -NEL, we will use a reduction from the Post Correspondence Problem (PCP). We first show how to encode an instance of the PCP into an Ł(0,b) -NEL ontology, and then describe how to use ontology consistency to solve the decision problem. 3 Encoding the PCP We reduce a variant of the undecidable PCP to the consistency problem in Ł(0,b) -NEL, using an idea that has been applied before to show undecidability of fuzzy DLs. The goal is to construct an ontology OP whose models contain the complete search tree for a solution to a given instance P of the PCP. Definition 1 (PCP). An instance P of the Post Correspondence Problem is a finite set of pairs {(v1 , w1 ), . . . , (vn , wn )} of words over an alphabet Σ. A solution for P is a sequence i1 · · · ik ∈ N ∗ such that v1 vi1 · · · vik = w1 wi1 · · · wik . We assume w.l.o.g. that the alphabet Σ is of the form {1, . . . , s} for some natural number s ≥ 4, and N denotes the index set {1, . . . , n}. For ν = i1 · · · ik ∈ N ∗ , we denote v1 vi1 · · · vik by vν and w1 wi1 · · · wik by wν . The search tree T of an instance P of the PCP is a tree over the domain N ∗ , in which each node ν ∈ N ∗ is labeled by vν and wν . In order to represent this search tree in an Ł(0,b) -NEL-interpretation, we need an appropriate encoding of words from Σ ∗ into the interval [0, 1]. For technical reasons caused by the use of general semantics, we cannot guarantee that a specific real number will be used at a given node of the tree, but have to allow for a bounded error. Thus, a word can be encoded by any number from a given interval, as described next. For v = α1 · · · αm with α1 , . . . , αm ∈ Σ, ← − v denotes αm · · · α1 . The encoding ← − enc(v) of v is the number 0. v , in base β := s + 2. In particular, enc(ε) := 0. For p ∈ [0, 1), the interval Errn (p) contains all numbers of the form b(p + e) ∈ [0, b) with an error term e with |e| < β −n . The set Enc(v) of bounded-error encodings of a word v ∈ Σ + is defined as the intersection of Err|v|+2 (enc(v)) with [0, b). The idea of these bounded-error encodings is to keep the error small enough to avoid overlapping. This way, we can decide whether two different real numbers are just different encoding of the same word; this is the case whenever they belong to the same error-bounded encoding. Lemma 2. Let v, w ∈ Σ + , p ∈ Enc(v), q ∈ Enc(w), g ∈ Err|v|+4 (β −(|v|+2) ), and h ∈ Err|w|+4 (β −(|w|+2) ). Then v = w iff |p − q| < 3 max{g, h}. Proof. We can assume w.l.o.g. that |v| = l ≤ m = |w|. It then follows that 3 max{g, h} = 3bβ −(l+2) + e with |e| < 3bβ −(l+4) < bβ −(l+3) . Additionally, p = benc(v) + e1 and q = benc(w) + e2 with |e1 | < bβ −(l+2) and |e2 | < bβ −(m+2) , and thus |e1 − e2 | < 2bβ −(l+2) . If v = w, then |p − q| = |e1 − e2 | < 2bβ −(l+2) < 3bβ −(l+2) + e = 3 max{g, h}. If v 6= w, then enc(v) and enc(w) must differ at least in the (l + 1)-th digit. Thus, |enc(v) − enc(w)| ≥ β −(l+1) . This implies that |p − q| ≥ b|enc(v) − enc(w)| − |e1 − e2 | > (β − 2)bβ −(l+2) ≥ 4bβ −(l+2) , and hence |p − q| > 3bβ −(l+2) + e = 3 max{g, h}. t u We now construct an ontology OP whose models encode the search tree of P. More precisely, it ensures that the concept names V and W will have values in Enc(vν ) and Enc(wν ), respectively, at every domain element that encodes the node ν ∈ N ∗ of the search tree T . The concept name G will have a value in Err|vν |+4 (1 − β −(|vν |+2) ), and similarly for H. These values provide a bound on the difference of the encoding of two words of a given length, and will be used to detect whether V and W encode the same word (see Lemma 2). The search tree is encoded in the following way. First, we ensure that at every element of the domain the concepts Vi and Wi are interpreted as the encodings of the words vi , wi , respectively, without any error terms (Section 3.1). They will be used to generate the encodings of the successor words vνi = vν vi from an encoding of vν , for every ν ∈ N ∗ and i ∈ N . We also use similar constants to update the values of G and H, which encode the error bounds introduced by the lack of witnessed models, from each node to its successor. Afterwards, we initialize the interpretation of all the relevant concepts at the root of the tree, identified by the individual name a0 (Section 3.2). We have to ensure, e.g. that V I (aI0 ) is an encoding of the word vε = v1 . We then describe the concatenation of encoded constant words to given encodings (Section 3.3), the creation of successors with large enough role degrees (Section 3.4), and the transfer of the concatenated encodings to these successors (Section 3.5). 3.1 Encoding Global Constants We use some auxiliary values that will be constant along the whole search tree; these are helpful for producing the error-bounded encodings of the words vν and wν . First, we store the encoding of the words v1 , . . . , vn , w1 , . . . , wn using the concept names V1 , . . . , Vn , W1 , . . . , Wn , respectively. More precisely, every model I of OP should satisfy ViI (x) = benc(vi ) and WiI (x) = benc(wi ) for all x ∈ DI and i ∈ N . Let l be the length of the word vi . We use the axioms l l ← − Aβl ≡ Aβl and Vi ≡ A2l vi , where Al is an auxiliary concept name. Let I be a model of these axioms and x ∈ DI . If l = 0, the second axiom implies that ViI (x) = benc(ε) = 0. If l > 0, the first axiom enforces β l (AIl (x)−b)+b = −β l (AIl (x)−b); thus AIl (x) = b(1− 2β1 l ). ← − Using the second axiom, we derive that ViI (x) = max{0, b − 2b vi 2β l }. Since ← v− i βl = 0.← v− < 1, we have V I (x) = benc(v ). i i i We also encode the constant words gi and hi that yield the numbers β |vi | − 1 and β |wi | − 1, respectively, when read in base β = s + 2. That is, gi is the concatenation of the symbol (s + 1) with itself |vi | times, and analogously for hi . We store them in the concept names Gi and Hi , respectively. They will be used to update the values of G and H in the search tree (see Section 3.5). The |vi | |vi | axioms Aβ|vi | ≡ Aβ|vi | and Gi ≡ A2g|vi | force Gi to always be b(1 − β i −|vi | ); an analogous construction can be used for Hi . Using the same idea, we encode the words g0 and h0 represented by the numbers β |v1 |+2 − 1 and β |w1 |+2 − 1 in the concept names G0 and H0 , respectively. 3.2 Initializing the Root At the root of the search tree of P, designated by the individual name a0 , the values of V and W should be benc(v1 ) and benc(w1 ), respectively. The two concept assertions a0 : (V → V1 ) u (V1 → V ) and a0 : (W → W1 ) u (W1 → W ) ensure this. The concept names G and H, storing the error bounds, are initialized to b(1 − β −(|v1 |+2) ) and b(1 − β −(|w1 |+2) ) using a0 : (G → G0 ) u (G0 → G) and a0 : (H → H0 ) u (H0 → H); G0 and H0 were defined in the previous section. 3.3 Concatenating Constants We now describe how to express the concatenation of a given encoding with a constant word vi . Assume that, for a given interpretation I and x ∈ DI , the value V I (x) is an element of Enc(vν ) for some ν ∈ N ∗ . The goal is to ensure that, for a given i ∈ N , the value Vi0I (x) is an element of Enc(vν vi ) = Enc(vνi ). We introduce the axioms l ( Vi00 )β ≡ V and Vi0 ≡ ( Vi00 ) u ( Vi ), where l = |vi |, Vi00 is a new concept name, and ViI (x) = benc(vi ) (see Section 3.1). Let I be an interpretation that satisfies the first axiom. If vν = ε, then V I (x) = 0, and thus Vi00I (x) = 0 = β −l V I (x). If vν 6= ε, then V I (x) ∈ (0, b), which implies that Vi00I (x) ∈ (0, b) and b − V I (x) = β l (−Vi00I (x)) + b, and thus Vi00I (x) = β −l V I (x). In both cases, Vi00I (x) equals V I (x) = b(0.← v− ν + e), shifted l digits to the right. By assumption, the error term e satisfies |e| < β −(|vν |+2) . Let now I also satisfy the second axiom. If either vν or vi is ε, then Vi0I (x) is ViI (x) or V I (x), respectively. In both cases, this expresses the concatenation of vν and vi . If both vν and vi are non-empty words, then V 0I (x) = b max{0, 1 − β −l (0.← i v− + e) − (0.← ν v−)} = b max{0, 1 − (0.← i v− + e0 )} νi 0 −l with |e | = β |e| < β . Thus, 0.← −(|vνi |+2) − + e0 < 1 and V 0I (x) ∈ Enc(v ). vνi i νi The values of the concept names G and H should also be updated. These values also have an error term, which is two orders of magnitude smaller than the encoding of the words from the search tree. Let GI (x) = b(1−β −(|vν |+2) +e) with |e| < β −(|vν |+4) , which corresponds to the word (s+1) · · · (s+1) of length |vν |+2. We have to concatenate this to the word (s + 1) · · · (s + 1) of length l := |vi |, l stored in Gi . As above, the axioms ( G00i )β ≡ G and G0i ≡ ( G00i ) u ( Gi ) ensure that G0I −l i (x) = b − b(1 − β (1 − β −(|vν |+2) + e) − (1 − β −l )) = b(1 − β −(|vνi |+2) + e0 ) with |e0 | < β −(|vνi |+4) . 3.4 Creating Successor Nodes The axioms > v ∃ri .> for each i ∈ N enforce the existence of ri -successors to each node of the search tree. This is the main difference to the proof of unde- cidability for Ł(0,b) -NEL w.r.t. witnessed models in [8]. In fact, in any witnessed model I of these axioms we have for each x ∈ DI a y ∈ DI such that riI (x, y) = 1. In the more general setting considered here, only the following holds. Lemma 3. Let I satisfy > v ∃ri .>. Then for each x ∈ DI and every error bound e > 0 there is a ye ∈ DI such that riI (x, ye ) > 1 − e. This is the main reason why we need to allow for bounded errors in the encodings of the words. If we could always guarantee the existence of ri -successors with degree 1, then the axioms presented in the next section could be used to transfer all values exactly. However, since only Lemma 3 holds, the transfer might lead to an additional error. 3.5 Transferring Values In Section 3.2, we have ensured that every interpretation contains an individual that encodes the root of the search tree. We are also able to compute the values needed in the successors using the constants from Section 3.1 and the concate- nation from Section 3.3. Intuitively, these values should now be transfered to the successors created in the previous section; however, in general this transfer of values from a node of the search tree T to a successor node will incur an error on the transferred value. Thus, we have to make sure that this error does not grow beyond the bounds of our encoding. We consider first the case that b = 1. We need to transfer the value of Vi0 at a node to the value of V at some ri -successor of this node. We show that, if Vi0I (x) = b(enc(vνi ) + e0 ) is a bounded-error encoding of vνi , then the axioms ∃ri .( V ) v Vi0 and ∃ri .V v Vi0 ensure that the value of V is also a bounded-error encoding of this word at all ri -successors with large enough role degree since the incurred error stays below e := b(β −(|vνi |+2) − |e0 |) > 0. Lemma 4. Let I satisfy ∃r.( D) v C and ∃r.D v C, b = 1, and 0 < e < 21 . Then for all x, y ∈ DI with rI (x, y) > 1 − e we have |C I (x) − DI (y)| < e. Proof. Let x and y be as above. The axioms force I to satisfy rI (x, y) ⊗ DI (y) ≤ sup rI (x, y 0 ) ⊗ DI (y 0 ) ≤ C I (x), and y 0 ∈D I rI (x, y) ⊗ DI (y) ≤ sup rI (x, y 0 ) ⊗ DI (y 0 ) ≤ C I (x). y 0 ∈D I This implies that rI (x, y) − DI (y) ≤ max{0, rI (x, y) − DI (y)} ≤ 1 − C I (x) and rI (x, y) + DI (y) − 1 ≤ max{0, rI (x, y) + DI (y) − 1} ≤ C I (x). From the first inequality if follows that C I (x) − DI (y) ≤ 1 − rI (x, y) < e and the second one yields DI (y) − C I (x) ≤ 1 − rI (x, y) < e. This shows that the absolute difference between C I (x) and DI (y) is always smaller than e. t u To transfer the value of G0i along ri to G, we use the axioms ∃ri .( G) v G0i and ∃ri .G v G0i . The error bound e := b(β −(|vνi |+4) − |e0 |) ensures that the additional error to G0Ii (x) = b(1 − β −(|vνi |+2) + e0 ) is small enough. In order to simultaneously satisfy all the above-mentioned restrictions in the ri -successors, we use only those y ∈ DI with riI (x, y) > 1 − e, where e is the minimum of the individual error bounds for Vi0 , Wi0 , G0i , and Hi0 . This is not a problem since Lemma 3 shows that such a successor y always exists. In the case that b < 1, the transfer of values is considerably easier. In fact, no error bounds are necessary in this case since encodings of words can be transferred without additional errors through any ri -successor with degree > b. Lemma 5. Let b < 1 and assume that I satisfies ∃r.( D) v C and ∃r.D v C. If x, y ∈ DI with C I (x) ∈ [0, b) and rI (x, y) > b, then C I (x) = DI (y). Proof. We have rI (x, y) ⊗ DI (y) ≤ C I (x) and rI (x, y) ⊗ DI (y) ≤ C I (x). If C I (x) = 0, then rI (x, y) ⊗ DI (y) = 0, and thus DI (y) = 0. Consider now the case that C I (x) ∈ (0, b). If DI (y) ≥ b, then C I (x) ≥ rI (x, y) ⊗ DI (y) ≥ b, con- tradicting the assumption. Likewise, DI (y) = 0 implies b−C I (x) ≥ rI (x, y) > b, which is also impossible. Thus, we must have DI (y) ∈ (0, b), which implies b − DI (y) ≤ b − C I (x) and DI (y) ≤ C I (x), and hence C I (x) = DI (y). t u As before, Lemma 3 ensures that a successor with degree strictly greater than b always exists, which shows that we can always transfer all desired values exactly. 3.6 Canonical Model From the constructions of Sections 3.1 to 3.5 we obtain the ontology OP : OP := O0 ∪ OG0 :=g0 ∪ OH0 :=h0 [n ∪ OVi :=vi ∪ OWi :=wi ∪ OGi :=gi ∪ OHi :=hi ∪ Ori i=1 ∪ OVi0 =V ◦vi ∪ OWi0 =W ◦wi ∪ OV 0 ri V ∪ OW 0 ri W i i ∪ OG0i =G◦gi ∪ OHi0 =H◦hi ∪ OG0 ri G ∪ OH 0 ri H , where i i O0 := {a0 : (V → V1 ) u (V1 → V ), a0 : (W → W1 ) u (W1 → W )} ∪ {a0 : (G → G0 ) u (G0 → G), a0 : (H → H0 ) u (H0 → H)}, β |u| β |u| 2u← − OC:=u := {C|u| ≡ C|u| , C ≡ C|u| }, |u| OD0 =C◦u := {( D00 )β ≡ C, D0 ≡ ( D00 ) u ( D)}, Or := {> v ∃r.>}, OC r D := {∃r.( D) v C, ∃r.D v C}. A model of this ontology is given by the interpretation IP = (N ∗ , ·IP ), where ·IP is defined as follows: – aI0 P = ε, – V IP (ν) = benc(vν ), ViIP (ν) = benc(vi ), Vi0IP (ν) = benc(vνi ), – W IP (ν) = benc(wν ), WiIP (ν) = benc(wi ), Wi0IP (ν) = benc(wνi ), – GIP (ν) = b(1 − β −(|vν |+2) ), H IP (ν) = b(1 − β −(|wν |+2) ), – GIi P (ν) = b(1 − β −|vi | ), HiIP (ν) = b(1 − β −|wi | ), – riIP (ν, νi) = 1 and riIP (ν, ν 0 ) = 0 if ν 0 6= νi. Notice that the values of all the auxiliary concept names used in the construction are fully determined by these concept names. Intuitively, IP is an encoding of the search tree of P. We now show that every model I of OP encodes the search tree T of P under the following notion of encoding. Definition 6. Let I be an interpretation, x ∈ DI , and ν ∈ N ∗ . We say that I at x encodes T at ν if, for every i ∈ N , a) V I (x) ∈ Enc(vν ), W I (x) ∈ Enc(wν ), b) GI (x) ∈ Err|vν |+4 (1 − β −(|vν |+2) ), H I (x) ∈ Err|wν |+4 (1 − β −(|wν |+2) ). In the following, whenever we talk about these properties, we will only consider V and G since W and H can be treated in an analogous manner. Lemma 7. For every model I of OP there is a function f : N ∗ → DI such that for all ν ∈ N ∗ , I at f (ν) encodes T at ν. Proof. We construct the function f by induction on ν ∈ N ∗ . For ν = ε, observe that the values of V and G at aI0 are forced by O0 to be V1I (ε) = benc(vε ) and GI0 (ε) = b(1 − β −(|vε |+2) ), respectively. Thus, for f (ν) := aI0 the conditions are satisfied even without any error terms. Assume now that I at f (ν) encodes T at ν and let i ∈ N . As described in Sections 3.4 and 3.5, one can find 0 < e < 12 such that the values of Vi0 and G0i are transferred to V and G, respectively, without increasing the error bounds on the encoded values. Specifically, we can choose e := min { 13 , b(β −(|vνi |+2) − |eVi0 |), b(β −(|vνi |+4) − |eG0i |), . . . } i=1,...,n if eVi0 and eG0i are the error terms of Vi0 and G0i , respectively. Lemmata 4 and 5 show that V I (y) is a bounded-error encoding of vνi whenever riI (x, y) > 1 − e, and similarly for GI (y). By Lemma 3, there is a yi ∈ DI such that I at yi encodes T at νi. We can thus define f (νi) := yi to satisfy the condition. t u Thus, in any model of OP we can find an encoding of the search tree T of P. The canonical model IP is the special case in which all error terms are 0. In the next section we use this encoding to solve the instance P of the PCP. 4 Finding a Solution To decide whether P has a solution, we use the additional ontology O6= , consist- ing of the single axiom (V → W ) u (W → V ) v (G  H)3 . Recall that G  H is interpreted as the minimum of the values of G and H in the interval [0, b]. Lemma 8. P has a solution iff OP ∪ O6= is inconsistent. Proof. If this ontology has no model, then in particular the canonical model IP of OP cannot satisfy O6= . We thus have (V → W )IP (ν) ⊗ (W → V )IP (ν) > ((G  H)3 )IP (ν) for some ν ∈ N ∗ . If V IP (ν) = W IP (ν), then vν = wν , i.e. P has a solution. We now assume without loss of generality that V IP (ν) < W IP (ν), and thus b − W IP (ν) + V IP (ν) > ((G  H)3 )IP (ν) = b − 3b max{β −(|vν |+2) , β −(|wν |+2) }. This implies that |enc(wν ) − enc(vν )| < 3b max{β −(|vν |+2) , β −(|wν |+2) }, and by Lemma 2 we again have vν = wν . Assume now that OP ∪ O6= has a model I and let f be the function con- structed in Lemma 7 and ν ∈ N ∗ . In particular, we have ((G  H)3 )I (f (ν)) = b − 3 max{g, h} ∈ (0, b) with g ∈ Err|vν |+4 (β −(|vν |+2) ) and h ∈ Err|wν |+4 (β −(|wν |+2) ). Since I satisfies O6= , it holds that ((V → W ) u (W → V ))I (f (ν)) ≤ ((G  H)3 )I (f (ν)). If we assume w.l.o.g. that V I (f (ν)) ≤ W I (f (ν)), then this implies W I (f (ν)) − V I (f (ν)) ≥ 3 max{g, h}, and by Lemma 2, vν 6= wν . Since this holds for all ν ∈ N ∗ , P has no solution. t u A direct consequence of this lemma is the undecidability of ontology consis- tency in the fuzzy DL Ł(0,b) -NEL. Theorem 9. Consistency of Ł(0,b) -NEL-ontologies is undecidable. In particular, this shows that ontology consistency in Ł-ALC is undecidable w.r.t. general models, even if the ontologies contain only crisp axioms. 5 Conclusions We have shown that ontology consistency w.r.t. general models is undecidable in fuzzy DLs based on t-norms starting with the Łukasiewicz t-norm using only the constructors from EL and residual negation. This was achieved by a modification of the undecidability proofs for these logics w.r.t. witnessed model semantics [8]. The main problem introduced by general semantics is that it is impossible to ensure that values are transferred exactly from a node to its role successors. To simulate the search tree for an instance of the PCP, we allow for a bounded error in the represented value. The bounds are small enough to ensure that different words can still be distinguished. Ontology consistency is a central decision problem for DLs since other reason- ing tasks like concept satisfiability or subsumption can be reduced to it. However, the converse reduction does not hold. It is thus natural to ask whether these other problems are also undecidable. Since our construction uses only crisp assertions that involve only one individual name, it follows that also concept satisfiability in Ł(0,b) -NEL is undecidable w.r.t. general models. Together with the results from [6], this fully characterizes the decidability of consistency and satisfiability w.r.t. general models in all fuzzy DLs between ⊗-NEL and ⊗-SHOI −∀ :2 it is decidable (in ExpTime) iff the t-norm ⊗ does not start with the Łukasiewicz t-norm, i.e. the fuzzy DL has Gödel negation. In future work we plan to extend the study of fuzzy DLs with general se- mantics, aiming towards a full characterization of their complexity properties, as has been done for witnessed models. In particular, we think that the presented approach using error bounds can be applied to modify other undecidability re- sults for fuzzy DLs w.r.t. witnessed models, e.g. for Π-ALC [8]. We also plan to generalize the framework presented in [8] to deal with general models. References 1. Baader, F., Peñaloza, R.: Are fuzzy description logics with general concept in- clusion axioms decidable? In: Proc. FUZZ-IEEE’11. pp. 1735–1742. IEEE Press (2011) 2. Baader, F., Peñaloza, R.: GCIs make reasoning in fuzzy DL with the product t-norm undecidable. In: Proc. DL’11. CEUR-WS, vol. 745, pp. 37–47 (2011) 3. Baader, F., Peñaloza, R.: On the undecidability of fuzzy description logics with GCIs and product t-norm. In: Proc. FroCoS’11, LNCS, vol. 6989, pp. 55–70. Springer (2011) 4. Bobillo, F., Straccia, U.: Fuzzy description logics with general t-norms and datatypes. Fuzzy Set. Syst. 160(23), 3382–3402 (2009) 5. Bobillo, F., Straccia, U.: Reasoning with the finitely many-valued Łukasiewicz fuzzy description logic SROIQ. Inform. Sciences 181, 758–778 (2011) 6. Borgwardt, S., Distel, F., Peñaloza, R.: Gödel negation makes unwitnessed consis- tency crisp. In: Proc. DL’12. CEUR-WS (2012), to appear. 7. Borgwardt, S., Peñaloza, R.: Description logics over lattices with multi-valued on- tologies. In: Walsh, T. (ed.) Proc. IJCAI’11. pp. 768–773. AAAI Press (2011) 8. Borgwardt, S., Peñaloza, R.: Undecidability of fuzzy description logics. In: Proc. KR’12. AAAI Press (2012), to appear. 9. Cerami, M., Esteva, F., Bou, F.: Decidability of a description logic over infinite- valued product logic. In: Proc. KR’10. pp. 203–213. AAAI Press (2010) 10. Cerami, M., Straccia, U.: On the undecidability of fuzzy description logics with GCIs with Łukasiewicz t-norm. Tech. rep., Computing Research Repository (2011), arXiv:1107.4212v3 [cs.LO]. An extended version of this paper has been submit- ted to a journal. 11. Hájek, P.: Making fuzzy description logic more general. FSS 154(1), 1–15 (2005) 12. Hájek, P.: Arithmetical complexity of fuzzy predicate logics—a survey II. Ann. Pure Appl. Logic 161(2), 212–219 (2009) 13. Stoilos, G., Stamou, G.B., Pan, J.Z., Tzouvaras, V., Horrocks, I.: Reasoning with very expressive fuzzy description logics. JAIR 30, 273–320 (2007) 14. Straccia, U.: Reasoning within fuzzy description logics. JAIR 14, 137–166 (2001) 15. Tresp, C.B., Molitor, R.: A description logic for vague knowledge. In: Proc. ECAI’98. pp. 361–365. John Wiley and Sons (1998) 2 ⊗-SHOI −∀ extends ⊗-NEL by the constructors t, →, inverse and transitive roles, fuzzy role hierarchies, and nominals.