Recent results show that ontology consistency is undecidable 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.
Fuzzy Description Logics (DLs) extend the semantics of classical DLs by
allowing 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 [
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 [
The crux of these undecidability results is that they all depend on restricting reasoning to the class of witnessed models. Since the existing reasoning algorithms 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 undecidability 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 [
Although possible, such a scenario would be very surprising since for
firstorder fuzzy logic, reasoning w.r.t. general models is typically harder than
reasoning w.r.t. witnessed models [
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)-NE L. 2.1
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 arguments. 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 2 [0; 1]. In that case, for all x; y 2 [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 = maxf0; x + y 1g, has the residuum x ) y = minf1; 1 x + yg and residual negation x = 1 x. A t-norm starts with the Łukasiewicz t-norm if there is a b 2 (0; 1] such that for all x; y 2 [0; b] we have x y = maxf0; x + y bg. 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 negation 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 involutive 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 x = 81 > <
b >:0
if x = 0 x if 0 < x
b 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 2 (0; 1], and ), are its residuum and residual negation, respectively. 2.2
The Fuzzy Description Logic Ł(0;b)-NEL Syntactically, Ł(0;b)-NE L extends the DL E L with the unary residual negation constructor . More precisely, concepts are built using the syntactic rule C ::= A j > j C u D j C j 9r:C: The semantics of Ł(0;b)-NE L is based on interpretations I = (DI ; I ) consisting of a domain DI and an interpretation 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 follows: >I (x) = 1, (C u D)I (x) = CI (x) DI (x), ( C)I (x) = CI (x), and (9r:C)I (x) = supy2DI rI (x; y) CI (y) for all x 2 DI .
In contrast to traditional semantics based on witnessed models, it is possible to have an interpretation I such that (9r:>)I (x) = 1 but where there is no y 2 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: C0 := >, and Ck+1 := Ck u C for any k 2 N; C ! D := (C u D); and C D := (C u D) ! D. It can easily be verified that, whenever CI (x); DI (x) 2 [0; b] for an interpretation I and x 2 DI , then we have (Ck)I (x) = maxf0; k(CI (x) b) + bg for every k > 0, (C ! D)I (x) = CI (x) ) DI (x), and (C D)I (x) = minfCI (x); DI (x)g.
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 CI (aI ) = 1 (resp. rI (aI ; bI ) = 1); it satisfies the GCI C v D if CI (x) DI (x) for every x 2 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 CI (x) = DI (x) for every x 2 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)-NE L, 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)-NE L ontology, and then describe how to use ontology consistency to solve the decision problem. 3
We reduce a variant of the undecidable PCP to the consistency problem in Ł(0;b)-NE L, 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 f(v1; w1); : : : ; (vn; wn)g of words over an alphabet . A solution for P is a sequence i1 ik 2 N such that v1vi1 vik = w1wi1 wik . We assume w.l.o.g. that the alphabet is of the form f1; : : : ; sg for some natural number s 4, and N denotes the index set f1; : : : ; ng. For = i1 ik 2 N , we denote v1vi1 vik by v and w1wi1 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 2 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 2 , 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 2 [0; 1), the interval Errn(p) contains all numbers of the form b(p + e) 2 [0; b) with an error term e with jej < n. The set Enc(v) of bounded-error encodings of a word v 2 + is defined as the intersection of Errjvj+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 2 +, p 2 Enc(v), q 2 Enc(w), g 2 Errjvj+4( h 2 Errjwj+4( (jwj+2)). Then v = w iff jp qj < 3 maxfg; hg. (jvj+2)), and Proof. We can assume w.l.o.g. that jvj = l 3 maxfg; hg = 3b (l+2) + e with jej < 3b p = benc(v) + e1 and q = benc(w) + e2 with je1j < b and thus je1 e2j < 2b (l+2). If v = w, then m = jwj. It then follows that (l+4) < b (l+3). Additionally, (l+2) and je2j < b (m+2), jp qj = je1 e2j < 2b (l+2) < 3b (l+2) + e = 3 maxfg; hg: If v 6= w, then enc(v) and enc(w) must differ at least in the (l + 1)-th digit. Thus, jenc(v) enc(w)j (l+1). This implies that jp qj bjenc(v) enc(w)j je1 e2j > ( 2)b (l+2) 4b (l+2); and hence jp qj > 3b (l+2) + e = 3 maxfg; hg. tu
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 2 N of the search tree T . The concept name G will have a value in Errjv j+4(1 (jv j+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 2 N and i 2 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 (a0I ) 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
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 2 DI and i 2 N .
Let l be the length of the word vi. We use the axioms
Al l
l Al and
Vi
Al2vi ; where Al is an auxiliary concept name. Let I be a model of these axioms and x 2 DI . If l = 0, the second axiom implies that ViI (x) = benc(") = 0. If l > 0, the first axiom enforces l(AlI (x) b) + b = l(AlI (x) b); thus AlI (x) = b(1 21 l ). Using the second axiom, we derive that vil = 0:vi < 1, we have ViI (x) = benc(vi).
We also encode the constant words gi and hi that yield the numbers jvij 1 and jwij 1, respectively, when read in base = s + 2. That is, gi is the concatenation of the symbol (s + 1) with itself jvij 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 axioms Ajvjivjij Ajvjivjij and Gi Aj2vgiij force Gi to always be b(1 jvij); an analogous construction can be used for Hi. Using the same idea, we encode the words g0 and h0 represented by the numbers jv1j+2 1 and jw1j+2 1 in the concept names G0 and H0, respectively.
ViI (x) = maxf0; b 22bvli g. Since 3.2
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 (jv1j+2)) and b(1 (jw1j+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
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 2 DI , the value V I (x) is an element of Enc(v ) for some 2 N . The goal is to ensure that, for a given i 2 N , the value Vi0I (x) is an element of Enc(v vi) = Enc(v i). We introduce the axioms ( Vi00) l
V and
Vi0 ( Vi00) u ( Vi); where l = jvij, 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 = lV I (x). If v 6= ", then V I (x) 2 (0; b), which implies that Vi00I (x) 2 (0; b) and b V I (x) = l( Vi00I (x)) + b, and thus Vi00I (x) = lV 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 jej < (jv j+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
Vi0I (x) = b maxf0; 1 l(0:v + e) (0:vi )g = b maxf0; 1 (0:v i + e0)g with je0j = ljej < (jv ij+2). Thus, 0:v i + e0 < 1 and Vi0I (x) 2 Enc(v 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 (jv j+2) +e) with jej < (jv j+4), which corresponds to the word (s+1) (s+1) of length jv j+2. We have to concatenate this to the word (s + 1) (s + 1) of length l := jvij, stored in Gi. As above, the axioms ( G0i0) l G and G0i ( G0i0) u ( Gi) ensure that G0iI (x) = b b(1 with je0j <
(jv ij+4). 3.4
l(1
(jv j+2) + e) (1
l)) = b(1
(jv ij+2) + e0)
The axioms > v 9ri:> for each i 2 N enforce the existence of ri-successors to
each node of the search tree. This is the main difference to the proof of
undecidability for Ł(0;b)-NEL w.r.t. witnessed models in [
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. 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 concatenation 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 9ri:( V ) v
Vi0 and 9ri: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( (jv ij+2) je0j) > 0.
C and 9r:D v C, b = 1, and 0 < e < 21 .
e we have jCI (x) DI (y)j < e.
Proof. Let x and y be as above. The axioms force I to satisfy rI (x; y)
DI (y) rI (x; y)
DI (y) sup rI (x; y0) y02DI sup rI (x; y0) y02DI
DI (y0)
CI (x), and DI (y0)
CI (x): This implies that rI (x; y) DI (y) maxf0; rI (x; y) DI (y)g 1 CI (x) and rI (x; y) + DI (y) 1 maxf0; rI (x; y) + DI (y) 1g CI (x). From the first inequality if follows that CI (x) DI (y) 1 rI (x; y) < e and the second one yields DI (y) CI (x) 1 rI (x; y) < e. This shows that the absolute difference between CI (x) and DI (y) is always smaller than e. tu To transfer the value of G0i along ri to G, we use the axioms 9ri:( G) v G0i and 9ri:G v G0i. The error bound e := b( (jv ij+4) je0j) ensures that the additional error to G0iI (x) = b(1 (jv ij+2) + e0) is small enough.
In order to simultaneously satisfy all the above-mentioned restrictions in the ri-successors, we use only those y 2 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 9r:( D) v C and 9r:D v C. If x; y 2 DI with CI (x) 2 [0; b) and rI (x; y) > b, then CI (x) = DI (y). Proof. We have rI (x; y) DI (y) CI (x) and rI (x; y) DI (y) CI (x). If CI (x) = 0, then rI (x; y) DI (y) = 0, and thus DI (y) = 0. Consider now the case that CI (x) 2 (0; b). If DI (y) b, then CI (x) rI (x; y) DI (y) b, contradicting the assumption. Likewise, DI (y) = 0 implies b CI (x) rI (x; y) > b, which is also impossible. Thus, we must have DI (y) 2 (0; b), which implies b DI (y) b CI (x) and DI (y) CI (x), and hence CI (x) = DI (y). tu 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
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 [ OVi0 ri V [ OWi0 ri W [ OG0i=G gi [ OHi0=H hi [ OG0i ri G [ OHi0 ri H , where O0 := fa0 : (V ! V1) u (V1 ! V ); a0 : (W ! W1) u (W1 ! W )g [ fa0 : (G ! G0) u (G0 ! G); a0 : (H ! H0) u (H0 ! H)g;
OC:=u := fCjujjuj OD0=C u := f( D00) juj
Or := f> v 9r:>g;
C ujuj ; j j
C
Cj2uuj g; C;
D0
( D00) u ( D)g; OC r D := f9r:( D) v
C; 9r:D v Cg: A model of this ontology is given by the interpretation IP = (N ; IP ), where IP is defined as follows: – a0IP = ", – V IP ( ) = benc(v ), ViIP ( ) = benc(vi), – W IP ( ) = benc(w ), WiIP ( ) = benc(wi), – GIP ( ) = b(1 (jv j+2)), HIP ( ) = b(1 – GiIP ( ) = b(1 jvij), HiIP ( ) = b(1 – riIP ( ; i) = 1 and riIP ( ; 0) = 0 if 0 6= i.
Vi0IP ( ) = benc(v i),
Wi0IP ( ) = benc(w i),
(jw j+2)), jwij), 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 2 DI , and at x encodes T at if, for every i 2 N ,
a) V I (x) 2 Enc(v ), b) GI (x) 2 Errjv j+4(1
W I (x) 2 Enc(w ), (jv j+2)), HI (x) 2 Errjw j+4(1 (jw j+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 for all 2 N , I at f ( ) encodes T at . ! DI such that Proof. We construct the function f by induction on 2 N . For = ", observe that the values of V and G at a0I are forced by O0 to be V1I (") = benc(v") and G0I (") = b(1 (jv"j+2)), respectively. Thus, for f ( ) := a0I the conditions are satisfied even without any error terms.
SectAiosnsusm3.e4naonwd t3h.5a,t oIneatcafn( fi)nednc0o<dees <T 12atsuch that the values of Vi0 and G0 and let i 2 N . As described in i are transferred to V and G, respectively, without increasing the error bounds on the encoded values. Specifically, we can choose e := i=m1;i:n::;nf 31 ; b( (jv ij+2) jeVi0 j); b( (jv ij+4) jeG0i j); : : : g 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 2 DI such that I at yi encodes T at i. We can thus define f ( i) := yi to satisfy the condition. tu 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
To decide whether P has a solution, we use the additional ontology O6=, consisting 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 2 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 and by Lemma 2, v 6= w . Since this holds for all 2 N , P has no solution.
tu
A direct consequence of this lemma is the undecidability of ontology consistency in the fuzzy DL Ł(0;b)-NE L.
Theorem 9. Consistency of Ł(0;b)-NE L-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
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 E L and residual negation. This was achieved by a modification
of the undecidability proofs for these logics w.r.t. witnessed model semantics [
Ontology consistency is a central decision problem for DLs since other reasoning 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)-NE L is undecidable w.r.t. general models.
Together with the results from [
In future work we plan to extend the study of fuzzy DLs with general
semantics, 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
results for fuzzy DLs w.r.t. witnessed models, e.g. for -ALC [
-SHOI 8 extends -NEL by the constructors t, !, inverse and transitive roles, fuzzy role hierarchies, and nominals.