How Fuzzy is my Fuzzy Description Logic?

How Fuzzy is my Fuzzy Description Logic?

Stefan Borgwardt ^? , Felix Distel, and Rafael Peñaloza Theoretical Computer Science, TU Dresden, Germany {stefborg,felix,penaloza}@tcs.inf.tu-dresden.de

Abstract. Fuzzy Description Logics (DLs) with t-norm semantics have been studied as a means for representing and reasoning with vague knowl- edge. Recent work has shown that even fairly inexpressive fuzzy DLs be- come undecidable for a wide variety of t-norms. We complement those results by providing a class of t-norms and an expressive fuzzy DL for which ontology consistency is linearly reducible to crisp reasoning, and thus has its same complexity. Surprisingly, in these same logics crisp models are insufficient for deciding fuzzy subsumption.

1 Introduction

Description logics (DLs) [1] are a family of logic-based knowledge representation formalisms, which can be used to represent the knowledge of an application domain in a formal way. In particular, they have been successfully used for the representation of medical knowledge in large-scale ontologies like Snomed CT ¹ and Galen. ² However, in their standard form DLs are not suited for dealing with imprecise or vague knowledge. For example, in the medical domain a high body temperature is often a symptom for a disease. When trying to represent this knowledge, it is not possible to give a precise characterization of the concept HighTemperature: one cannot define a point where a temperature becomes high.

However, 37 ^◦ C should belong “less” to this concept than, say 39 ^◦ C.

Fuzzy variants of description logics have been proposed as a formalism for modeling this kind of imprecise knowledge, by providing a degree of membership of individuals to concepts—typically a number from the interval [0, 1]. One could thus express that 36 ^◦ C and 39 ^◦ C belong to HighTemperature with degrees 0.7 and 0.9, respectively. A more thorough description of the use of fuzzy semantics in medical applications can be found in [20].

A great variety of fuzzy DLs can be found in the literature (for two rele- vant surveys see [18,12]). In fact, fuzzy DLs have several degrees of freedom for defining their expressiveness. In addition to the choice of concept constructors (e.g. conjunction u or existential restriction ∃), and the type of axioms allowed (like acyclic concept definitions or general concept inclusions), which define the

?

Partially supported by the DFG under grant BA 1122/17-1 and in the Collaborative Research Center 912 “Highly Adaptive Energy-Efficient Computing”.

1

http://www.ihtsdo.org/snomed-ct/

2

http://www.opengalen.org/

underlying logical language, one must also decide how to interpret the different constructors, through a choice of functions over the domain of fuzzy values [0, 1].

As in mathematical fuzzy logic [13], these functions are typically determined by a continuous t-norm that interprets conjunction.

Research in fuzzy DLs has focused on three specific t-norms, namely the Gödel, Łukasiewicz, and product t-norms. However, there are uncountably many continuous t-norms, each with different properties. For example, under the prod- uct t-norm semantics, existential restrictions (∃) and value restrictions (∀) are not interdefinable, while under the Łukasiewicz t-norm they are. Even after fixing the t-norm, one can still choose whether to interpret negation by the involutive negation operator, or using the residual negation, which need not be involutive.

An additional level of liberty comes from selecting the class of models over which reasoning is considered: either all models, or so-called witnessed models only [14].

The majority of the reasoning algorithms available have been developed for the Gödel semantics, either by a reduction to crisp reasoning [6], or by a simple adaptation of the known algorithms for crisp DLs [23,24,25,27]. However, meth- ods capable of dealing with other t-norms have also been explored [7,8,9,26,22].

Usually, these algorithms reason w.r.t. witnessed models. ³

Very recently, it was shown that the tableaux-based algorithms for logics with semantics based on t-norms other than the Gödel t-norm and allowing general concept inclusions were incorrect [2,5]. This raised doubts about the decidability of the reasoning problems in these logics, and eventually led to a plethora of undecidability results for fuzzy DLs [2,3,4,11]. These undecidability results were then extended to a wide variety of fuzzy DLs in [10]. In fact, it has been shown that for a large class of t-norms ontology consistency easily becomes undecidable. More precisely, for every t-norm that “starts” with the Łukasiewicz t-norm, consistency of crisp ontologies is undecidable for any fuzzy DL that can express conjunction, existential restrictions and the residual negation.

In this paper we counterbalance these undecidability results by considering continuous t-norms not starting with the Łukasiewicz t-norm—in particular, the Gödel and product t-norms are of this kind. We show that consistency of fuzzy ontologies is again decidable, even for the very expressive DL SHOI, which al- lows for nominals and transitive and inverse roles, if negation is interpreted using residual negation. Moreover, for any of these t-norms, an ontology is consistent w.r.t. fuzzy semantics iff it is consistent w.r.t. to crisp semantics. Thus, ontology consistency in fuzzy SHOI is ExpTime-complete for every t-norm not starting with the Łukasiewicz t-norm; for all other t-norms, or if the involutive negation is used, this problem is undecidable [10].

To some extent, the fact that fuzzy ontology consistency can be reduced to crisp reasoning is not very surprising, since fuzzy logics are not, nor should they be considered to be, a formalism for dealing with inconsistencies. Yet, it shines a negative light on the capacity of fuzzy DLs for dealing with imprecise knowledge:

the decidable fuzzy DLs considered in this paper are not fuzzy, but mere syntactic extensions of classical DLs. However, there are other DL reasoning problems for

3

In fact, witnessed models were introduced in [14] to correct the algorithm from [27].

which this is not true: we show that crisp reasoning is insufficient for deciding subsumption or instance checking. Thus, even for the logics considered in this paper, where satisfiability is “crisp”, reasoning in general is fuzzy.

In the next section, we introduce some basic notions from t-norms and fuzzy description logics. Section 3 shows some properties of t-norms that do not start with the Łukasiewicz t-norm. In Sections 4 and 5 we prove that consistency and satisfiability w.r.t. these t-norms are essentially crisp reasoning problems. In the end we provide an example that shows that crisp reasoning is insufficient for de- ciding subsumption or instance checking. Specifically, we provide a subsumption relation that holds in every crisp and finite model, but does not hold in general.

2 Preliminaries

We first recall the basic notions of t-norms and mathematical fuzzy logic [17,13], which we then use to define the semantics of fuzzy DLs.

2.1 Mathematical Fuzzy Logic

Mathematical fuzzy logic generalizes classical logic by replacing true and false by a larger set of truth values. Here, we use the real interval [0, 1] as truth values and generalize propositional conjunction ∧ by a t-norm: an associative, commutative, and monotone binary operator on [0, 1] that has 1 as its unit element. Classical implication is then generalized by the residuum ⇒ of the t-norm, if it exists.

The residuum is a binary operator on [0, 1] that satisfies x ⊗ y ≤ z iff y ≤ x ⇒ z for all x, y, z ∈ [0, 1]. A consequence of this definition is that, for all x, y ∈ [0, 1],

– 1 ⇒ x = x and – x ≤ y iff x ⇒ y = 1.

A t-norm is called continuous if it is continuous as a function from [0, 1] ² to [0, 1]. In this paper, we consider only continuous t-norms and often call them simply t-norms. Any continuous t-norm ⊗ has a unique residuum ⇒ given by x ⇒ y = sup{z ∈ [0, 1] | x ⊗ z ≤ y}. Based on the residuum, one can define a unary residual negation by x = x ⇒ 0. To generalize disjunction, the t-conorm

⊕ defined as x ⊕ y = 1 − ((1 − x) ⊗ (1 − y)) can be used. Notice that 0 is the unit of the t-conorm, and hence

x ⊕ y = 0 iff x = 0 and y = 0. (1)

Three important continuous t-norms, together with their t-conorms and residua, are depicted in Table 1. These are fundamental in the sense that every continuous t-norm can be constructed from these three as follows.

Definition 1 (ordinal sum). Let I be a set and for each i ∈ I let ⊗ i be a continuous t-norm and a i , b i ∈ [0, 1] such that a i < b i and the intervals (a i , b i ) are pairwise disjoint. The ordinal sum of the t-norms ⊗ i is the t-norm ⊗ with

x ⊗ y =

( a i + (b i − a i ) 

x−a

b

−a

⊗ i y−a

b

−a



if x, y ∈ [a i , b i ] for some i ∈ I,

min{x, y} otherwise.

Name t-norm (x ⊗ y) t-conorm (x ⊕ y) residuum (x ⇒ y)

Gödel min{x, y} max{x, y}

( 1 if x ≤ y y otherwise

product x · y x + y − x · y

( 1 if x ≤ y y/x otherwise Łukasiewicz max{x + y − 1, 0} min{x + y, 1} min{1 − x + y, 1}

Table 1. The three fundamental continuous t-norms.

The ordinal sum of a class of continuous t-norms is itself a continuous t-norm, and its residuum is given by

x ⇒ y =



 



 



1 if x ≤ y,

a i + (b i − a i ) 

x−a

b

−a

⇒ i y−a

b

−a



if a i ≤ y < x ≤ b i for some i ∈ I,

y otherwise,

where ⇒ i is the residuum of ⊗ i , for each i ∈ I. Intuitively, this means that the t-norm ⊗ and its residuum “behave like” ⊗ i and its residuum in each of the intervals [a i , b i ], and like the Gödel t-norm and residuum everywhere else.

Theorem 2 ([21]). Every continuous t-norm is isomorphic to the ordinal sum of copies of the Łukasiewicz and product t-norms.

Motivated by this representation as an ordinal sum, we say that a continuous t-norm ⊗ starts with the Łukasiewicz t-norm if in its representation as ordinal sum there is an i ∈ I such that a i = 0 and ⊗ i is isomorphic to the Łukasiewicz t-norm.

An element x ∈ (0, 1) is called a zero divisor for ⊗ if there is a z ∈ (0, 1) such that x ⊗ z = 0. Of the three fundamental continuous t-norms, only the Łukasiewicz t-norm has zero divisors. In fact, every element in the interval (0, 1) is a zero divisor for this t-norm. A continuous t-norm can only have zero divisors if it starts with the Łukasiewicz t-norm.

Lemma 3 ([17]). A continuous t-norm has zero divisors iff it starts with the Łukasiewicz t-norm.

2.2 The Fuzzy Description Logic ⊗-SHOI

A fuzzy description logic usually inherits its syntax from the underlying crisp description logic. In this paper, we consider the constructors of SHOI with the addition of →, which in the crisp case can be expressed by t and ¬.

Definition 4 (syntax). Let N C , N R , and N I , be disjoint sets of concept, role, and individual names, respectively, and N ⁺ _R ⊆ N R be a set of transitive role names. The set of (complex) roles is N _R ∪ {r ⁻ | r ∈ N R }. The set of (complex) concepts is defined by the following syntax rule:

C ::= A | > | ⊥ | {a} | ¬C | C u C | C t C | C → C | ∃s.C | ∀s.C,

where A is a concept name, a is an individual name, and s is a complex role.

The inverse of a complex role s (denoted by s) is s ⁻ if s ∈ N _R and r if s = r ⁻ . A role s is transitive if either s or s belongs to N ⁺ _R .

Let now ⊗ be a continuous t-norm. As a generalization of SHOI, where con- cepts are interpreted by subsets of a domain, in the fuzzy DL ⊗-SHOI they are interpreted by fuzzy sets, which are functions specifying the membership degree of each domain element to the concept. The interpretation of the constructors is based on the t-norm ⊗ and the induced operators ⊕, ⇒, and .

Definition 5 (semantics). An interpretation is a pair I = (∆ ^I , · ^I ), where the domain ∆ ^I is a non-empty set and · ^I is a function that assigns to every concept name A a function A ^I : ∆ ^I → [0, 1], to every individual name a an element a ^I ∈ ∆ ^I , and to every role name r a function r ^I : ∆ ^I × ∆ ^I → [0, 1] such that r ^I (x, y) ⊗ r ^I (y, z) ≤ r ^I (x, z) holds for all x, y, z ∈ ∆ ^I if r ∈ N ⁺ _R . The function

· ^I is extended to complex roles and concepts as follows for every x, y ∈ ∆ ^I , – (r ⁻ ) ^I (x, y) = r ^I (y, x),

– > ^I (x) = 1, ⊥ ^I (x) = 0,

– {a} ^I (x) = 1 if a ^I = x and 0 otherwise, – (¬C) ^I (x) = C ^I (x),

– (C 1 u C 2 ) ^I (x) = C ₁ ^I (x) ⊗ C ₂ ^I (x), – (C ₁ t C ₂ ) ^I (x) = C ₁ ^I (x) ⊕ C ₂ ^I (x), – (C 1 → C 2 ) ^I (x) = C ₁ ^I (x) ⇒ C ₂ ^I (x),

– (∃s.C) ^I (x) = sup _z∈∆

s ^I (x, z) ⊗ C ^I (z), and – (∀s.C) ^I (x) = inf _z∈∆

s ^I (x, z) ⇒ C ^I (z).

An interpretation I is called finite if its domain ∆ ^I is finite, and crisp if A ^I (x), r ^I (x, y) ∈ {0, 1} for all A ∈ N _C , r ∈ N _R , and x, y ∈ ∆ ^I .

Knowledge is encoded using DL axioms, which restrict the class of interpreta- tions that are considered. The fuzzy DL ⊗-SHOI extends the axioms of SHOI by specifying a degree to which the restrictions should hold.

Definition 6 (axioms). An axiom is either an assertion of the form ha : C, `i or h(a, b) : s, `i, a general concept inclusion (GCI) of the form hC v D, `i, or a role inclusion of the form hs v t, `i, where C and D are concepts, a, b ∈ N I , s, t are complex roles, and ` ∈ (0, 1]. An axiom is called crisp if ` = 1.

An interpretation I satisfies an assertion ha : C, `i if C <sup>I</sup> (a <sup>I</sup> ) ≥ ` and an assertion h(a, b) : s, `i if s <sup>I</sup> (a <sup>I</sup> , b <sup>I</sup> ) ≥ `. It satisfies the GCI hC v D, `i if C <sup>I</sup> (x) ⇒ D <sup>I</sup> (x) ≥ ` holds for all x ∈ ∆ ^I . It satisfies a role inclusion hs v t, `i if s <sup>I</sup> (x, y) ⇒ t <sup>I</sup> (x, y) ≥ ` holds for all x, y ∈ ∆ ^I .

An ontology (A, T , R) consists of a finite set A of assertions (ABox), a finite set T of GCIs (TBox), and a finite set R of role inclusions (RBox). It is crisp if every axiom in A, T , and R is crisp. An interpretation I is a model of this ontology if it satisfies all its axioms.

The combination of axioms in an ontology may entail some knowledge of the

domain that is not explicitly represented. Reasoning can then be used to make

this knowledge explicit. We consider the standard reasoning problems of crisp

SHOI, extended with a degree to which they hold.

Definition 7 (reasoning problems). Let O be an ontology, C, D be concepts, a an individual, and ` ∈ [0, 1]. O is called consistent if it has a model.

C is `-satisfiable w.r.t. O if there is a model I of O and x ∈ ∆ <sup>I</sup> such that C <sup>I</sup> (x) ≥ `. C is `-subsumed by D w.r.t. O with ` ∈ [0, 1] if every model of O satisfies the GCI hC v D, `i. The individual a is an `-instance of C w.r.t. O if every model of O satisfies the assertion ha : C, `i.

The best satisfiability (subsumption, instance) degree of C (C and D, a and C) w.r.t. O is the supremum of all ` ∈ [0, 1] such that C is `-satisfiable (C is

`-subsumed by D, a is an `-instance of C) w.r.t. O.

Recall that the semantics of the quantifiers require the computation of a supremum or infimum of the membership degrees of a possibly infinite set of elements of the domain. As is standard in the fuzzy DL community, we restrict reasoning to a special kind of models, called witnessed models [14]. For exam- ple, consider the axiom h> v ∃r.>, 1i. There are models where an individual has infinitely many r-successors with role degree smaller than 1, as long as the supremum of the role degrees is 1. Witnessed models prevent these situations and ensure that there actually exists an r-successor with degree 1.

Definition 8 (witnessed). An interpretation I is called witnessed if for every x ∈ ∆ ^I , every role s and every concept C there are y 1 , y 2 ∈ ∆ ^I such that

(∃s.C) ^I (x) = s ^I (x, y ₁ ) ⊗ C ^I (y ₁ ), (∀s.C) ^I (x) = s ^I (x, y ₂ ) ⇒ C ^I (y ₂ ).

We will show that, if the t-norm ⊗ has no zero divisors, then consistency w.r.t.

witnessed models in ⊗-SHOI is effectively the same problem as consistency in crisp SHOI. Moreover, the precise values appearing in the axioms in the ontology are then irrelevant. The same is not true, however, for subsumption or instance checking. To obtain these results, we exploit some properties those t-norms.

3 Properties of t-norms without Zero Divisors

By Lemma 3, continuous t-norms without zero divisors are exactly those that do not start with the Łukasiewicz t-norm. In particular, this includes the two other basic continuous t-norms, the Gödel and product t-norms.

Proposition 9. For any t-norm ⊗ without zero divisors and every x ∈ [0, 1], 1. x ⇒ y = 0 iff x > 0 and y = 0, and

2. x = 0 iff x > 0.

Proof. We prove the if -direction of the first claim. Assume x > 0 and y = 0.

Then x ⇒ y = x ⇒ 0 = sup{z | z ⊗ x = 0}. Since ⊗ has no zero divisors, z ⊗ x > 0 for all z > 0. Therefore {z | z ⊗ x = 0} = {0} and thus x ⇒ y = 0. The only if -direction holds for all t-norms [17]. The second statement follows from

the first one since x = x ⇒ 0. u t

The main result of this paper is based on the function 1 that maps fuzzy truth values to crisp truth values by defining, for all x ∈ [0, 1],

1(x) =

( 1 if x > 0 0 if x = 0.

For a t-norm without zero divisors it follows from Proposition 9 that 1(x) = x for all x ∈ [0, 1]. This function is compatible with negation, the t-norm, the corresponding t-conorm, implication and suprema. It is also compatible with minima, provided that they exist.

Lemma 10. Let ⊗ be a t-norm without zero divisors. For all x, y ∈ [0, 1] and all non-empty sets X ⊆ [0, 1] it holds that

1. 1( x) = 1(x), 2. 1(x ⊗ y) = 1(x) ⊗ 1(y), 3. 1(x ⊕ y) = 1(x) ⊕ 1(y), 4. 1(x ⇒ y) = 1(x) ⇒ 1(y),

5. 1 (sup{x | x ∈ X}) = sup{1(x) | x ∈ X}, and

6. if min{x | x ∈ X} exists then 1 (min{x | x ∈ X}) = min{1(x) | x ∈ X}.

Proof. It holds that 1( x) = x = 1(x) which proves 1. Since ⊗ does not have zero divisors it holds that x ⊗ y = 0 iff x = 0 or y = 0. This yields 1(x ⊗ y) = 0 iff 1(x) = 0 or 1(y) = 0. Because there are no zero divisors, this shows that

1(x ⊗ y) = 0 iff 1(x) ⊗ 1(y) = 0. (2) Both 1(x ⊗ y) and 1(x) ⊗ 1(y) can only have the values 0 or 1. Hence, (2) is sufficient to prove the second statement. Following similar arguments we obtain from (1) that 1(x ⊕ y) = 0 holds iff 1(x) ⊕ 1(y) = 0. This suffices to prove 3. We use Proposition 9 to prove 4:

1(x ⇒ y) =

( 1 iff x = 0 or y > 0 0 iff x > 0 and y = 0 =

( 1 iff 1(x) = 0 or 1(y) = 1 0 iff 1(x) = 1 and 1(y) = 0

= 1(x) ⇒ 1(y).

To prove 5, observe that sup X = 0 iff X = {0}, which yields 1 sup X
= 0 ⇔ sup X = 0 ⇔ X = {0}

⇔ { 1(x) | x ∈ X} = {0} ⇔ sup{1(x) | x ∈ X} = 0.

Assume now that min X = x min exists. Then we have

1(min X) = 0 ⇔ x min = 0 ⇔ 0 ∈ { 1(x) | x ∈ X} ⇔ min{1(x) | x ∈ X} = 0.

This shows that 1(min X) = 0 iff min{1(x) | x ∈ X} = 0, which proves 6. u t

Notice that in general 1 is not compatible with the infimum. Consider for

example the set X = { _n ¹ | n ∈ N}. Then inf X = 0 and hence 1(inf X) = 0,

but inf{ 1( ¹ _n ) | n ∈ N} = inf{1} = 1. This is the main reason why we consider

witnessed models only. In fact, the construction provided in the next section

does not work for general model reasoning.

4 The Crisp Model Property

The existing undecidability results for Fuzzy DLs all rely heavily on the fact that one can design ontologies that allow only models with infinitely many truth val- ues. We shall see that for t-norms without zero divisors one cannot construct such an ontology in ⊗-SHOI. It is even true that all consistent ⊗-SHOI-ontologies have a crisp (and finite) model.

Definition 11. A fuzzy DL L has the crisp model property if every consistent L-ontology has a crisp model.

For the rest of this paper we assume that ⊗ is a continuous t-norm that does not have zero divisors. These t-norms share the useful properties described in Section 3. In particular, Lemma 10 allows us to construct a crisp interpretation from a fuzzy interpretation by simply applying the function 1.

Let I be a witnessed fuzzy interpretation for the concept names N _C and role names N _R . We construct the interpretation J over the domain ∆ ^J := ∆ ^I by defining, for all concept names A ∈ N _C , all role names r ∈ N _R , and all x, y ∈ ∆ ^I ,

A ^J (x) = 1 A ^I (x)

and r ^J (x, y) = 1 r ^I (x, y)
.

To show that J is a valid interpretation, we first verify the transitivity condition for all r ∈ N ⁺ _R and all x, y, z ∈ ∆ ^J . From Lemma 10, we obtain

r ^J (x, y) ⊗ r ^J (y, z) = 1 r ^I (x, y)
⊗ 1 r ^I (y, z)
= 1 r ^I (x, y) ⊗ r ^I (y, z)
. Since I satisfies the transitivity condition and 1 is monotonic, we have

1 r ^I (x, y) ⊗ r ^I (y, z)
≤ 1 r ^I (x, z)
= r ^J (x, z), and thus r ^J (x, y) ⊗ r ^J (y, z) ≤ r ^J (x, z).

Lemma 12. For all complex roles s and x, y ∈ ∆ ^I , s ^J (x, y) = 1(s ^I (x, y)).

Proof. If s is a role name, this follows directly from the definition of J . If s = r ⁻ for some r ∈ N R , then s ^J (x, y) = r ^J (y, x) = 1(r ^I (y, x)) = 1(s ^I (x, y)).

In a similar way, the interpretation J preserves the compatibility of 1 to the different constructors.

Lemma 13. For all complex concepts C and x ∈ ∆ ^I , C ^J (x) = 1 C ^I (x)
. Proof. We use induction over the structure of C. The claim holds trivially for C = ⊥ and C = >. For C = A ∈ N C it follows immediately from the definition of J . It also holds for C = {a}, a ∈ N I , because {a} ^I (x) can only take the values 0 or 1 for all x ∈ ∆ ^I .

Assume now that the concepts D and E satisfy D ^J (x) = 1(D ^I (x)) and E ^J (x) = 1(E ^I (x)) for all x ∈ ∆ ^I . In the case where C = D u E, Lemma 10 yields that for all x ∈ ∆ ^I

C ^J (x) = D ^J (x) ⊗ E ^J (x) = 1 D ^I (x)
⊗ 1 E ^I (x)

= 1 D ^I (x) ⊗ E ^I (x)
= 1 C ^I (x)
.

Likewise, the compatibility of 1 with the t-conorm, the residuum, and the nega- tion entails the result for the cases C = D t E, C = D → E, and C = ¬D.

For C = ∃s.D, where s is a complex role and D is a concept description satisfying D ^J (x) = 1(D ^I (x)) for all x ∈ ∆ ^I , we obtain

1 C ^I (x)
= 1 (∃s.D) ^I (x)
= 1 sup

y∈∆

s ^I (x, y) ⊗ D ^I (y)

= sup

y∈∆

 1 s ^I (x, y)
⊗ 1 D ^I (y)

(3) because 1 is compatible with the supremum and the t-norm. Lemma 12 yields

sup

y∈∆

 1(r ^I (x, y)) ⊗ 1(D ^I (y)) = sup

y∈∆

r ^J (x, y) ⊗ D ^J (y) = (∃r.D) ^J (x). (4)

Equations (3) and (4) prove 1(C ^I (x)) = C ^J (x) for the case where C = ∃r.D. If C = ∀r.D, we have

1 C ^I (x)
= 1 inf

y∈∆

r ^I (x, y) ⇒ D ^I (y)
. (5) Since I is witnessed, there must exist some y 0 ∈ ∆ ^I such that

r ^I (x, y ₀ ) ⇒ D ^I (y ₀ ) = inf

y∈∆

r ^I (x, y) ⇒ D ^I (y) ; that is, min y∈∆

r ^I (x, y) ⇒ D ^I (y)

exists. Thus, Part 6. of Lemma 10 is applicable and 1(C ^I (x)) = C ^J (x) follows in analogy to the case for existential

restrictions. u t

With the help of this lemma we can show that the crisp interpretation J satisfies all the axioms that are satisfied by I.

Lemma 14. Let O = (A, T , R) be a ⊗-SHOI-ontology. If I is a witnessed model of O, then J is also a witnessed model of O.

Proof. We prove that J satisfies all assertions, GCIs, and role inclusions from O. Let ha : C, `i, ` ∈ (0, 1], be a concept assertion from A. Since the assertion is satisfied by I, C ^I (a ^I ) ≥ ` > 0 holds. Lemma 13 yields C <sup>J</sup> (a <sup>J</sup> ) = 1 ≥ `. The same argument can be used for role assertions.

Let now hC v D, `i be a GCI from T . Let x be an element x ∈ ∆ <sup>I</sup> . As the GCI is satisfied by I, we get C <sup>I</sup> (x) ⇒ D <sup>I</sup> (x) ≥ ` > 0. By Lemmata 10 and 13, we obtain

C ^J (x) ⇒ D ^J (x) = 1(C ^I (x)) ⇒ 1(D ^I (x)) = 1(C ^I (x) ⇒ D ^I (x)) = 1 ≥ `, and thus J satisfies the GCI hC v D, `i. A similar argument, using Lemma 12 instead of Lemma 13, shows that J satisfies all role inclusions in R. u t The previous results show that by applying 1 to the truth degrees we obtain a crisp model J from any fuzzy model I of a ⊗-SHOI-ontology O.

Theorem 15. ⊗-SHOI has the crisp model property if ⊗ has no zero divisors.

In the next section we will use this result to show that ontology consistency

and concept satisfiability can be decided in exponential time.

5 Consistency and Satisfiability

For a given ⊗-SHOI-ontology O, we define crisp(O) to be the crisp SHOI- ontology that is obtained from O by replacing all the truth values appearing in the axioms by 1. For example, for the ontology

O = ha:C, 0.2i, h(a, b):r, 0.8i, hC v D, 0.5i, hr v s, 0.1i we obtain

crisp(O) = ha:C, 1i, h(a, b):r, 1i, hC v D, 1i, hr v s, 1i .

Lemma 16. Let O be a ⊗-SHOI-ontology and I be a crisp interpretation.

Then I is a model of O iff it is a model of crisp(O).

Proof. Assume that crisp(O) has a model I. Let hC v D, `i, ` > 0, be an axiom from O. Since I is a model of crisp(O), it must satisfy hC v D, 1i; that is, C ^I (x) ⇒ D ^I (x) ≥ 1 ≥ ` holds for all x ∈ ∆ <sup>I</sup> . Thus I satisfies hC v D, `i. The proof that I satisfies assertions and role inclusions is analogous. Hence I is also a model of O.

For the other direction, assume that I satisfies hC v D, `i. As I is a crisp interpretation it holds that C <sup>I</sup> (x) ⇒ D <sup>I</sup> (x) ∈ {0, 1} for all x ∈ ∆ <sup>I</sup> . Together with C <sup>I</sup> (x) ⇒ D <sup>I</sup> (x) ≥ ` > 0 we obtain C ^I (x) ⇒ D ^I (x) = 1. Thus, I satisfies the GCI hC v D, 1i. The same argument can be used for role inclusions and assertions. Thus, I is also a model of crisp(O). u t In particular, a ⊗-SHOI-ontology O has a crisp model iff crisp(O) has a crisp model. Together with Theorem 15, this shows that a ⊗-SHOI-ontology O is consistent iff crisp(O) has a crisp model. Therefore, one can use reasoning in crisp SHOI to decide consistency of ⊗-SHOI-ontologies. Reasoning in crisp SHOI is known to be ExpTime-complete [15].

Corollary 17. Deciding consistency in ⊗-SHOI is ExpTime-complete.

Similar arguments show that satisfiability is decidable in ⊗-SHOI. Since any concept is 0-satisfiable, we can assume in the following that the concept C is `-satisfiable w.r.t. an ontology O with ` > 0. Then there is a model I of O satisfying C ^I (x) ≥ ` > 0. Thus, the model J of O constructed in Section 4 also satisfies C <sup>J</sup> (x) = 1 ≥ `. This shows that if C is `-satisfiable w.r.t. O for some ` > 0, it is also 1-satisfiable w.r.t. O, and in particular 1-satisfiable w.r.t.

crisp(O). Clearly, the implication in the other direction also holds.

Lemma 18. Deciding `-satisfiability in ⊗-SHOI is ExpTime-complete. Fur- thermore, the best satisfiability degree of a concept C w.r.t. O is either 0 or 1 and can be computed in exponential time.

Lemma 16 and Corollary 15 still hold when we restrict the semantics to the

slightly less expressive logics ⊗-SHO, which does not allow for inverse roles,

or ⊗-SI which does not allow for nominals and role hierarchies. The crisp DLs

SHO and SI are known to have the finite model property [16,19], and ⊗-SI

and ⊗-SHO inherit the finite model property from their crisp ancestors.

Theorem 19. The logics ⊗-SHO and ⊗-SI and their sublogics have the finite model property.

This theorem contradicts a recent result stating that the sublogic Π-ALC of ⊗-SHOI, where ⊗ is the product t-norm, does not have the finite model property [5, Theorem 3.8]. As a matter of fact, the proof from [5] is based on the erroneous claim that every model I of the assertion ha : A, 0.5i must be such that A ^I (a ^I ) = 0.5. The case of an interpretation with A ^I (a ^I ) = 1, which also satisfies this assertion, is not considered in the induction argument.

6 Subsumption and Instance Checking

We now show that, despite the crisp model property, `-subsumption of concepts w.r.t. ⊗-SHOI-ontologies cannot be decided using crisp reasoning. Moreover, this holds even if the ontology is restricted to be crisp itself.

Consider first the ontology O 1 containing only the GCI h> v A, `i for some

` ∈ (0, 1). Since ` > 0, for every crisp model I of O 1 and x ∈ ∆ ^I , A ^I (x) = 1 holds. Thus, > is 1-subsumed by A w.r.t. O 1 when reasoning is restricted to crisp models. However, the interpretation I 1 = ({x}, · ^I ₁ ), where A ^I

(x) = `, is also a model of O 1 , but violates the axiom h> v A, 1i. In fact, the best subsumption degree of > and A w.r.t. O 1 is `, which is smaller than 1. Notice that this example only assumes that the logic can express concept names, the top concept, and fuzzy GCIs. Moreover, it is irrelevant which t-norm ⊗ was chosen for the semantics.

Proposition 20. For every fuzzy DL ⊗-L that allows the top constructor and fuzzy GCIs, `-subsumption cannot be decided over crisp models only.

If the logic uses a t-norm ⊗ without zero divisors and is able to express the residual negation, then this proposition holds even if the ontology is crisp. Take for instance the ontology O ₂ containing the axiom h> v ¬¬A, 1i. As before, it is easy to see that every crisp model of O ₂ also satisfies h> v A, 1i. On the other hand, the best subsumption degree of > and A w.r.t. O ₂ is 0.

To show this, we construct a model I ₂ of O ₂ that violates h> v A, `i for every ` > 0. The interpretation I ₂ = ( N, · ^I

) is given by A ^I

(i) = 1/i for every i ≥ 1. I ₂ is indeed a model of O ₂ since A ^I

(i) > 0 and hence (¬¬A) ^I

(i) = 1 for every i ≥ 1. However, for every ` > 0 there is an i ∈ N such that 0 < 1/i < ` and hence I 2 violates the axiom h> v A, `i. Thus, the best subsumption degree of > and A w.r.t. O 2 is 0.

Proposition 21. Let ⊗ be a t-norm without zero divisors and ⊗-L be a fuzzy DL with residual negation. Then `-subsumption cannot be decided over crisp models only. This holds even for `-subsumption w.r.t. crisp ontologies.

In the special case where ⊗ is the product t-norm, the problem is more

pronounced, since reasoning cannot be restricted to finite models either, as we

1 2 4

A :

A :

A :

r : 1 r : 1

Fig. 1. A model where h> v A, `i does not hold for any ` > 0.

show next. Consider the ontology

O = {h> v ¬¬A, 1i, h> v ∃r.>, 1i, h∃r.A v A u A, 1i}.

We show that every finite model of O also satisfies the GCI h> v A, 1i, but the best subsumption degree of > and A w.r.t. O is 0.

Let first I be a model of O that violates h> v A, 1i. We show that I must be infinite. To do this, we show by induction that for every n ≥ 1 there exist x 1 , . . . , x n ∈ ∆ ^I such that 1 > A ^I (x 1 ) > . . . > A ^I (x n ) > 0; since A ^I (x i ) 6= A ^I (x j ) for every i 6= j, this implies that ∆ ^I must contain infinitely many individuals.

For the induction base, since I violates h> v A, 1i, there must be an x ∈ ∆ ^I such that A ^I (x) < 1. As I satisfies the first axiom of O, it also follows that A ^I (x) > 0. Thus, if we set x 1 = x, then the claim holds for n = 1. Suppose now that it holds for n ≥ 1, we show that it also holds for n + 1. Since I is a witnessed model of O, the second axiom implies that there must exist a y ∈ ∆ ^I such that r ^I (x _n , y) = r ^I (x _n , y) ⊗ >(y) = 1. The third axiom then implies that

A ^I (x n ) > A ^I (x n )
2

≥ (∃r.A) ^I (x n )

≥ r ^I (x _n , y) ⊗ A ^I (y) = A ^I (y).

Since I satisfies the first axiom, it additionally holds that A ^I (y) > 0. Thus, setting x n+1 = y yields the result.

It remains only to show that the best subsumption degree of > and A w.r.t.

O is 0. We build a model I 0 of O that violates h> v A, `i for every ` > 0. Let I 0 = ({2 ⁱ | i ≥ 0}, · ^I

) be given by A ^I

(x) = 2 ^−x , and

r ^I

(x, y) =

( 1 y = 2x 0 y 6= 2x for all x, y ∈ ∆ ^I

(cf. Figure 1).

We verify that I ₀ is a model of O. First, since 2 ⁻ⁱ > 0 for every i ≥ 0, it follows that A ^I

(x) > 0 for all x ∈ ∆ ^I . Thus, I ₀ satisfies the first axiom of O.

For every x ∈ ∆ ^I it also holds that

(∃r.>) ^I

(x) = r ^I

(x, 2x) = 1 and (∃r.A) ^I

(x) = r ^I

(x, 2x) ⊗ A ^I

(2x)

= 2 ^−2x = 2 ^−x · 2 ^−x = A ^I

(x) ⊗ A ^I

(x),

satisfying the remaining two axioms of the ontology. The fact that this model is witnessed is a trivial consequence of the fact that every individual of the domain has exactly one r-successor with degree different from 0.

This all means that > is not `-subsumed by A w.r.t. O for any ` > 0, but >

is subsumed by A with degree 1 in every finite model of O. Notice that all the axioms in O are crisp. We thus have the following result.

Proposition 22. Let ⊗ be the product t-norm and ⊗-L be a fuzzy DL with conjunction, existential restriction, and residual negation. Then `-subsumption cannot be decided over finite models only. This holds even for `-subsumption w.r.t. crisp ontologies.

Notice that the three ontologies O 1 , O ₂ , and O presented in this section contain only GCIs. In this case it follows that a concept C is `-subsumed by D iff any individual a is an `-instance of the concept C → D. Likewise, the best subsumption degree of C and D is equivalent to the best instance degree of a and C → D. Thus, if the fuzzy DL allows for the constructor →, then Propositions 20, 21, and 22 also hold for `-instance checking, i.e. `-instances cannot be checked by a reduction to crisp reasoning. This is true even if the ontology is crisp. Moreover, under product t-norm semantics, finite models are insufficient for instance checking w.r.t. crisp ontologies.

7 Conclusions

We have shown that for every t-norm ⊗ that does not have zero divisors, con- sistency of ⊗-SHOI ontologies is ExpTime-complete. Indeed, to decide this problem it suffices to test consistency of the crisp version of the ontology. For all other t-norms—those having zero divisors—it was previously shown that consis- tency becomes undecidable already for a fairly inexpressive DL, allowing only for conjunction, existential restrictions and residual negation.

It is worth pointing out that the correctness of our reduction to crisp rea- soning strongly depends on the fact that ⊗-SHOI ontologies, as presented in this paper, cannot express upper bounds for the membership degrees. If one ex- tends this logic to allow for these upper bounds, either by the introduction of the involutive negation 1 − x or by axioms of the form hα ≤ `i, then ontology consistency becomes undecidable for every t-norm except the Gödel t-norm.

In crisp DLs, ontology consistency is the “main” decision problem in the sense that all other standard problems—like concept satisfiability, subsumption and instance checking—are polynomially reducible to it. In crisp DLs, a is a (1-)instance of C w.r.t. an ontology O iff the ontology obtained by adding the assertion ha:¬C, 1i to O is inconsistent. However, for any t-norm without zero divisors, this last axiom only states that a ^I (C) = 0 must hold in every model, which is much stronger than the required condition a ^I (C) < 1. Indeed, despite

⊗-SHOI having the crisp model property, crisp reasoning is insufficient for de-

ciding subsumption and instance checking. Moreover, under the product t-norm

semantics, finite models cannot decide these problems, even for those sublogics of ⊗-SHOI that have the finite model property.

These results leave open the decidability status of subsumption and instance checking in fuzzy DLs. This is one of the main problems we intend to examine in future work. In this respect it is worth to point out that, so far, all the existing decision procedures for fuzzy DLs depend on crisp- or finite-model reasoning.

This suggests that if, e.g. subsumption turns out to be decidable in these logics, a different kind of decision procedure would have to be developed.

References

1. Franz Baader, Diego Calvanese, Deborah McGuinness, Daniele Nardi, and Peter F.

Patel-Schneider, editors. The Description Logic Handbook: Theory, Implementa- tion, and Applications. Cambridge University Press, 2003.

2. Franz Baader and Rafael Peñaloza. Are fuzzy description logics with general con- cept inclusion axioms decidable? In Proc. of the 2011 IEEE Int. Conf. on Fuzzy Systems (FUZZ-IEEE’11), pages 1735–1742. IEEE Press, 2011.

3. Franz Baader and Rafael Peñaloza. GCIs make reasoning in fuzzy DLs with the product t-norm undecidable. In Riccardo Rosati, Sebastian Rudolph, and Michael Zakharyaschev, editors, Proc. of the 24th Int. Workshop on Description Logics (DL 2011), volume 745 of CEUR Workshop Proceedings, Barcelona, Spain, 2011.

4. Franz Baader and Rafael Peñaloza. On the undecidability of fuzzy description logics with GCIs and product t-norm. In Cesare Tinelli and Viorica Sofronie- Stokkermans, editors, Proc. of 8th Int. Symp. Frontiers of Combining Systems (FroCoS’11), volume 6989 of Lecture Notes in Artificial Intelligence, pages 55–70.

Springer-Verlag, 2011.

5. Fernando Bobillo, Félix Bou, and Umberto Straccia. On the failure of the fi- nite model property in some fuzzy description logics. Fuzzy Sets and Systems, 172(23):1–12, 2011.

6. Fernando Bobillo, Miguel Delgado, Juan Gómez-Romero, and Umberto Straccia.

Fuzzy description logics under Gödel semantics. International Journal of Approx- imate Reasoning, 50(3):494–514, 2009.

7. Fernando Bobillo and Umberto Straccia. A fuzzy description logic with product t-norm. In Proc. of the 2007 IEEE Int. Conf. on Fuzzy Systems FUZZ-IEEE’07, pages 1–6. IEEE Press, 2007.

8. Fernando Bobillo and Umberto Straccia. On qualified cardinality restrictions in fuzzy description logics under Łukasiewicz semantics. In Proc. of the 12th Int. Conf.

on Information Processing and Management of Uncertainty in Knowledge-Based Systems (IPMU’08), pages 1008–1015, 2008.

9. Fernando Bobillo and Umberto Straccia. Fuzzy description logics with general t-norms and datatypes. Fuzzy Sets and Systems, 160(23):3382–3402, 2009.

10. Stefan Borgwardt and Rafael Peñaloza. Undecidability of fuzzy description logics.

In Proc. of the 13th Int. Conf. on Principles of Knowledge Representation and Reasoning (KR 2012), Rome, Italy, 2012. AAAI Press. To appear.

11. Marco Cerami and Umberto Straccia. On the undecidability of fuzzy description

logics with GCIs with Łukasiewicz t-norm. Technical report, Computing Research

Repository, 2011. arXiv:1107.4212v3 [cs.LO].

12. Ángel García-Cerdaña, Eva Armengol, and Francesc Esteva. Fuzzy description logics and t-norm based fuzzy logics. International Journal of Approximate Rea- soning, 51:632–655, 2010.

13. Petr Hájek. Metamathematics of Fuzzy Logic (Trends in Logic). Springer-Verlag, 2001.

14. Petr Hájek. Making fuzzy description logic more general. Fuzzy Sets and Systems, 154(1):1–15, 2005.

15. Jan Hladik. A tableau system for the description logic SHIO. In Proceedings of the Doctoral Programme of IJCAR 2004, volume 106 of CEUR Worksop Proceedings, pages 21–25, 2004.

16. Ian Horrocks, Ulrike Sattler, and Stephan Tobies. A PSpace-algorithm for deciding ALCN I

-satisfiability. LTCS-Report 98-08, RWTH Aachen, Germany, 1998.

17. Erich Peter Klement, Radko Mesiar, and Endre Pap. Triangular Norms. Springer- Verlag, 2000.

18. Thomas Lukasiewicz and Umberto Straccia. Managing uncertainty and vagueness in description logics for the semantic web. Journal of Web Semantics, 6(4):291–308, 2008.

19. Carsten Lutz, Carlos Areces, Ian Horrocks, and Ulrike Sattler. Keys, nominals, and concrete domains. Journal of Artificial Intelligence Research, 23:667–726, 2004.

20. Ralf Molitor and Christopher B. Tresp. Extending description logics to vague knowledge in medicine. In P. Szczepaniak, P. J. G. Lisboa, and S. Tsumoto, editors, Fuzzy Systems in Medicine, volume 41 of Studies in Fuzziness and Soft Computing, pages 617–635. Springer-Verlag, 2000.

21. P. S. Mostert and A. L. Shields. On the structure of semigroups on a compact manifold with boundary. Annals of Mathematics, 65:117–143, 1957.

22. Giorgos Stoilos and Giorgos B. Stamou. A framework for reasoning with expressive continuous fuzzy description logics. In Bernardo Cuenca Grau, Ian Horrocks, Boris Motik, and Ulrike Sattler, editors, Proc. of the 22nd Int. Workshop on Description Logics (DL 2009), volume 477 of CEUR Workshop Proceedings, 2009.

23. Giorgos Stoilos, Giorgos B. Stamou, Vassilis Tzouvaras, Jeff Z. Pan, and Ian Hor- rocks. The fuzzy description logic f-SHIN . In Proc. of the 1st Int. Workshop on Uncertainty Reasoning for the Semantic Web (URSW’05), pages 67–76, 2005.

24. Giorgos Stoilos, Umberto Straccia, Giorgos B. Stamou, and Jeff Z. Pan. General concept inclusions in fuzzy description logics. In Proc. of the 17th Eur. Conf. on Artificial Intelligence (ECAI’06), volume 141 of Frontiers in Artificial Intelligence and Applications, pages 457–461. IOS Press, 2006.

25. Umberto Straccia. Reasoning within fuzzy description logics. Journal of Artificial Intelligence Research, 14:137–166, 2001.

26. Umberto Straccia and Fernando Bobillo. Mixed integer programming, general concept inclusions and fuzzy description logics. In Proc. of the 5th EUSFLAT Conf. (EUSFLAT’07), pages 213–220. Universitas Ostraviensis, 2007.

27. Christopher B. Tresp and Ralf Molitor. A description logic for vague knowledge. In

Proc. of the 13th Eur. Conf. on Artificial Intelligence (ECAI’98), pages 361–365,

Brighton, UK, 1998. J. Wiley and Sons.