General Concept Inclusion Absorptions for Fuzzy Description Logics: A First Step Fernando Bobillo1 and Umberto Straccia2 1 Dpt. of Computer Science & Systems Engineering, University of Zaragoza, Spain 2 Istituto di Scienza e Tecnologie dell’Informazione (ISTI - CNR), Pisa, Italy Email: fbobillo@unizar.es, straccia@isti.cnr.it Abstract. General Concept Inclusion (GCIs) absorption algorithms have shown to play an important role in classical Description Logics (DLs) reasoners, as they allow to transform GCIs into simpler forms to which apply specialised inference rules, resulting in an important performance gain. In this work, we develop a first absorption algorithm for fuzzy DLs, and evaluate it over some ontologies. 1 Introduction GCI Absorption is a technique that allows to transform General Concept In- clusion axioms (GCIs) into simpler forms to which apply specialised inference rules [1, 11, 12, 18–20, 24], such as the so-called lazy unfolding rules. While absorption algorithms have shown to provide an important perfor- mance gain for classical DLs reasoners, no such algorithms have been developed so far in the context of fuzzy DLs [14], i.e., DLs in which the truth of axioms may not be bivalent, but graded instead, e.g., a truth value in [0, 1]. Another benefit may consist in the posssibility to transform a non acyclic knowledge base into an acyclic one. This is important from a computational point of view, as e.g., the satisfiability problem under Lukasiewicz logic is correct and complete for acyclic TBoxes, while the general GCIs case is undecidable [5] (see [4] for more undecidability results). Also note that the absorption method holds for the case of finite linearly-ordered truth space as well, for which the satisfiability problem is decidable if the same problem for the corresponding classical DL is. Therefore, the absorptions can be beneficial for finitely-valued DLs as well. The aim of this paper is to work out an absorption algorithm for fuzzy DLs, and evaluate it over some ontologies using the fuzzyDL reasoner [2]3 . In the following, we first recap some basic fuzzy DLs definitions, then in Section 3 we illustrate our GCI absorption algorithm, while Section 4 provides an evaluation of it. Eventually, Section 5 concludes and illustrates some future research directions. 2 Fuzzy DLs Basics We recap here some basic definitions we rely on. We refer the reader to e.g., [14], for a more in depth presentation. 3 http://www.straccia.info/software/fuzzyDL/fuzzyDL.html 1 1 1 1 0 0 0 0 a b c d x a b c x a b x a b x (a) (b) (c) (d) Fig. 1. (a) Trapezoidal function trz (a, b, c, d), (b) triangular function tri(a, b, c), (c) left shoulder function ls(a, b), and (d) right shoulder function rs(a, b). Mathematical Fuzzy Logic. Fuzzy Logic is the logic of fuzzy sets. A fuzzy set R over a countable crisp set X is a function R : X → [0, 1]. The trapezoidal (Fig. 1 (a)), the triangular (Fig. 1 (b)), the L-function (left-shoulder function, Fig. 1 (c)), and the R-function (right-shoulder function, Fig. 1 (d)) are frequently used to specify membership functions of fuzzy sets. Although fuzzy sets have a far greater expressive power than classical crisp sets, its usefulness depends critically on the capability to construct appropri- ate membership functions for various given concepts in different contexts. The problem of constructing meaningful membership functions is a difficult one and we refer the interested reader to, e.g., [13, Chapter 10]. However, one easy and typically satisfactory method to define the membership functions is to uniformly partition the range of, e.g., salary values (bounded by a minimum and maximum value), into 5 or 7 fuzzy sets using either trapezoidal functions (e.g., as illustrated on the left in Figure 2), or using triangular functions (as illustrated on the right in Figure 2). The latter is the more used one, as it has less parameters. Fig. 2. Fuzzy sets over salaries using trapezoidal or triangular functions. In Mathematical Fuzzy Logic [9], the convention prescribing that a statement is either true or false is changed and is a matter of degree measured on an ordered scale that is no longer {0, 1}, but e.g., [0, 1]. This degree is called degree of truth of the logical statement φ in the interpretation I. For us, fuzzy statements have the form hφ, αi, where α ∈ (0, 1] and φ is a statement, encoding that the degree of truth of φ is greater or equal α. Usually, the truth space is L = [0, 1]. Another 1 n−2 popular truth space is the finite truth space Ln = {0, n−1 , . . . , n−1 , 1} for some natural number n > 1. Of course, L2 is the usual classical two-valued case. A fuzzy interpretation I maps each atomic statement pi into [0, 1] and is then extended inductively to all statements: I(φ ∧ ψ) = I(φ) ⊗ I(ψ), I(φ ∨ ψ) = I(φ) ⊕ I(ψ), I(φ → ψ) = I(φ) ⇒ I(ψ), I(¬φ) = I(φ), I(∃x.φ(x)) = supy∈∆I I(φ(y)), I(∀x.φ(x)) = inf y∈∆I I(φ(y)), where ∆I is the domain of I, and ⊗, ⊕, ⇒, and are so-called t-norms, t-conorms, implication functions, and negation functions, respectively, which extend the Boolean conjunction, disjunc- tion, implication, and negation, respectively, to the fuzzy case. One usually distinguishes three different logics, namely Lukasiewicz, Gödel, and Product logics [9]4 , with the following combination functions: Lukasiewicz logic Gödel logic Product logic Zadeh logic α ⊗ β max(α + β − 1, 0) min(α, β) α·β min(α, β) α⊕β min(α + β, 1) ( max(α, β) α+β−α·β max(α, β) 1 if α ≤ β α ⇒ β min(1 − α + β, 1) min(1, β/α) max(1 − α, β) β otherwise ( ( 1 if α = 0 1 if α = 0 α 1−α 1−α 0 otherwise 0 otherwise We will also use an optional subscript X ∈ {l, g, p} to identify the logic they refer to (e.g., α ⊗g β refers to Gödel conjunction). Note that the operators for Zadeh logic, namely α ⊗ β = min(α, β), α ⊕ β = max(α, β), α = 1 − α and α ⇒ β = max(1 − α, β), can be expressed in Lukasiewicz logic. More precisely, min(α, β) = α ⊗l (α ⇒l β), max(α, β) = 1 − min(1 − α, 1 − β). Furthermore, the implication α ⇒kd β = max(1 − α, b) is called Kleene-Dienes implication (denoted ⇒kd ), while Zadeh implication (denoted ⇒z ) is the implication α ⇒z β = 1 if α ≤ β; 0 otherwise. An r-implication is an implication function obtained as the residuum of a continuous t-norm ⊗ i.e., α ⇒ β = max{γ | α ⊗ γ ≤ β}. Note that Lukasiewicz, Gödel and Product implications are r-implications, while Kleene-Dienes impli- cation is not. Note also, that given an r-implication ⇒r , we may also define its related negation r α by means of α ⇒r 0 for every α ∈ [0, 1]. Some additional properties of truth combination functions are the following: Property Lukasiewicz logic Gödel Product Zadeh [23] α⊗ α=0 • • • α⊕ α=1 • α⊗α=α • • α⊕α=α • • α=α • • α⇒β = α⊕β • • α⇒β= β⇒ α • • (α ⇒ β) = α ⊗ β • • (α ⊗ β) = α ⊕ β • • • • (α ⊕ β) = α ⊗ β • • • • α ⊗ (β ⊕ γ) = (α ⊗ β) ⊕ (α ⊗ γ) • • α ⊕ (β ⊗ γ) = (α ⊕ β) ⊗ (α ⊕ γ) • • The notions of satisfiability and logical consequence are defined in the stan- dard way, where a fuzzy interpretation I satisfies a fuzzy statement hφ, αi or I is a model of hφ, αi, denoted as I |= hφ, αi, iff I(φ) ≥ α. Fuzzy ALC(D) basics. We recap here the fuzzy variant of the DL ALC(D) [17]. A fuzzy concrete domain or fuzzy datatype theory D = h∆D , · D i consists of a datatype domain ∆D and a mapping · D that assigns to each data value an element of ∆D , and to every n-ary datatype predicate d an n-ary fuzzy relation over ∆D . We will restrict to unary datatypes as usual in fuzzy DLs. Therefore, · D maps indeed each datatype predicate into a function from ∆D to [0, 1]. Typical examples of datatype predicates d are the well known membership functions 4 The main reason is that any other t-norm can be obtained as a combination of them. d := ls(a, b) | rs(a, b) | tri(a, b, c) | trz(a, b, c, d) | ≥v | ≤v | =v , where e.g., ls(a, b) is the left-shoulder membership function and ≥v corresponds to the crisp set of data values that are greater or equal than the value v. Now, let A be a set of concept names (also called atomic concepts), R be a set of role names. Each role is either an object property or a datatype prop- erty. The set of concepts are built from concept names A using connectives and quantification constructs over object properties R and datatype properties T , as described by the following syntactic rules: C → > | ⊥ | A | C1 u C2 | C1 t C2 | ¬C | C1 → C2 | ∃R.C | ∀R.C | ∃T.d | ∀T.d . Each of the connectives u and t may also have a subscript X ∈ {g, l, p}, → may have a subscript X ∈ {kd, g, l, p, z} and, ¬ may have a subscript Y ∈ {g, l}. The subscript indicates the fuzzy logic the connectives refers to (see Section 2). For instance, C u (D →l ∀R.¬g E) is a concept (if a subscript is missing, then we assume that a a priori selected fuzzy logic X ∈ {g, l, p, z} has been selected). An ABox A consists of a finite set of assertions of the forms ha:C, αi (meaning that a is an instance of C to degree at least α), or h(a, b):R, αi (meaning that a and b are related via R with degree degree at least α), where a, b are individual names, C is a concept, R is a role name and α ∈ (0, 1] is a truth value. A Terminological Box or TBox T is a finite set of GCIs and constraints. A General Concept Inclusion (GCI) axiom is of the form hC1 v C2 , αi (C1 is a sub-concept of C2 to degree at least α), where Ci is a concept and α ∈ (0, 1]. A primitive GCI is one of the form hA v C, αi, where A is a concept name and C is a concept. In both cases above, v may also have a subscript X ∈ {g, l, p, z}. · Note that vkd is not allowed. A definitional GCI is one of the form A = C. A is called the head of a primitive/definitional axiom, and C is the body. A synonym · GCI is of the form A = B, where both A and B are concept names. A generalised · definitional GCI is of the form C = D, where both C and D are concepts. A constraint axiom has one of the following form (R is an object property): (i) domain(R, C), called domain restriction, that restricts the domain of role R to be concept C; (ii) range(R, C), called range restriction, that restricts the range of role R to be concept C; and (iii) disjoint(A, B), called disjoint restriction, that restricts the concept names A and B to be disjoint. We may omit the truth degree α of an axiom; in this case α = 1 is assumed. A knowledge base is a pair K = hA, T i, where A is an ABox and T is a TBox. Let T be a TBox consisting of definitional GCIs only. Concept name A directly uses concept name B w.r.t. T , if A is the head of some axiom τ ∈ T such that B occurs in the body of τ . Let uses be the transitive closure of the relation directly uses. T is acyclic if no concept name A is the head of more than one definitional axiom in T and there is no concept name A such that A uses A. Concerning the semantics, let us fix a fuzzy logic X ∈ {l, g, p, z}. Unlike classical DLs in which an interpretation I maps e.g., a concept C into a set of individuals C I ⊆ ∆I , i.e., I maps C into a function C I : ∆I → {0, 1} (either an individual belongs to the extension of C or does not belong to it), in fuzzy DLs, I maps C into a function C I : ∆I → [0, 1] and, thus, an individual belongs to the extension of C to some degree in [0, 1], i.e., C I is a fuzzy set. Specifically, a fuzzy interpretation is a pair I = (∆I , ·I ) consisting of a nonempty (crisp) set ∆I (the domain) and of a fuzzy interpretation function ·I that assigns: (i) to each atomic concept A a function AI : ∆I → [0, 1]; (ii) to each object property R a function RI : ∆I ×∆I → [0, 1]; (iii) to each data type property T a function T I : ∆I × ∆D → [0, 1]; (iv) to each individual a an element aI ∈ ∆I ; and (v) to each concrete value v an element v I ∈ ∆D . Now, a fuzzy interpretation function is extended to concepts as specified below (where x, y ∈ ∆I are elements of the domain), so for every concept C we get a function C I : ∆I → [0, 1]: ⊥I (x) = 0, >I (x) = 1, (C u D)I (x) = C I (x) ⊗ DI (x), (C uX D)I (x) = C I (x) ⊗X DI (x), (C t D)I (x) = C I (x) ⊕ DI (x), (C tX D)I (x) = C I (x) ⊕X DI (x), (¬C)I (x) = C I (x), (¬X C)I (x) = X C I (x), (C → D)I (x) = C I (x) ⇒ DI (x), (C →X D)I (x) = C I (x) ⇒X DI (x), (∀R.C)I (x) = inf y∈∆I {RI (x, y) ⇒ C I (y)}, (∃R.C)I (x) = supy∈∆I {RI (x, y) ⊗ C I (y)}, (∀T.d)I (x) = inf y∈∆I {T I (x, y) ⇒ dD (y)}, (∃T.d)I (x) = supy∈∆I {T I (x, y) ⊗ dD (y)} . The satisfiability of axioms is then defined by the following conditions: (i) I satisfies an axiom ha:C, αi if C I (aI ) ≥ α; (ii) I satisfies an axiom h(a, b):R, αi I if RI (aI , bI ) ≥ α; (iii) I satisfies an axiom hC v D, αi if (C v D) ≥ α where5 I (C v D) = inf x∈∆I {C I (x) ⇒ DI (x)}; (iv) I satisfies an axiom hC vX D, αi I I if (C vX D) ≥ α where (C vX D) = inf x∈∆I {C I (x) ⇒X DI (x)}; (v) I satisfies an axiom domain(R, C) if I satisfies ∃R.> v C; (vi) I satisfies an axiom range(R, C) if I satisfies > v ∀R.C; and (vii) I satisfies an axiom disjoint(A, B) if I satisfies A u B v⊥. I is a model of a K = hA, T i iff I satisfies each axiom in K. We say that K entails and axiom α, denoted K |= α, if any model of K satisfies α. Two TBoxes T , T 0 are equivalent (denoted T ≡ T 0 ) iff they entail the same set of axioms. Example 1. We have built a fuzzy wine ontology6 , according the FuzzyOWL 2 proposal7 . One of the GCIs in there is of the form SparklingW ineu(∃hasSugar. tri(32, 41, 50)) v DemiSecSparklingW ine where hasSugar is a datatype prop- erty whose values are measured in g/L. Example 2. fuzzyDL-Learner 8 is a system that illustrates how one may learn graded GCIs. For instance, consider the case of hotel finding in a possible tourism application, where an ontology is used to describe the meaningful entities of the domain. Now, one may fix a city, say Pisa, extract the characteristic of the hotels from Web sites and the graded hotel judgements of the users, e.g., from Trip 5 However, note that under Zadeh logic v is interpreted as ⇒z and not as ⇒kd . 6 http://www.straccia.info/software/FuzzyOWL/ontologies/FuzzyWine.1.0.owl 7 http://www.straccia.info/software/FuzzyOWL 8 http://straccia.info/software/FuzzyDL-Learner Advisor9 and asks about what characterises good hotels. Then one may learn that, e.g., h∃hasP rice.High v GoodHotel, 0.569i where hasP rice is a datatype property whose values are measured in euros and the price concrete domain has been automatically fuzzified as illustrated below. Now, it can be verified that for hotel verdi, whose room price is 105 euro, i.e., we have the assertion verdi:∃hasP rice. =105 in the KB, we infer under Product logic that K |= hverdi:GoodHotel, 0.18i (note that 0.18 = 0.318 · 0.569, where 0.318 = tri(90, 112, 136)(105)). 3 GCI Absorptions for Fuzzy DLs The aim of our GCI absorption algorithm is to build from a TBox T an equivalent TBox T 0 , which is the union of two disjoint sets of axioms Tg and Tu , where: 1. Tg is a set of GCIs of the form h> v C, αi, 2. Tu = Tdef ∪ Tinc ∪ Tdr ∪ Tdisj ∪ Tsyn is the disjoint union of (a) Tdef , which is acyclic and contains definitional GCIs only; (b) Tinc , which contains primitive GCIs only; (c) Tdr , which contains domain and range restrictions only; (d) Tdisj , which contains disjoint restrictions only; (e) Tsyn , which contains synonym GCIs only; and 3. there cannot be a concept name A that is a head of axioms in Tdef and Tinc . This partitioning makes it possible to apply lazy unfolding rules to axioms in Tu only. Now, we explain now how to compute it: Sections 3.1–3.4 present some auxiliary steps and then Section 3.5 describes the partitioning algorithm. The transformations, if left unspecified, hold always, i.e., for connectives taken from the same logic; for the other cases, the semantics under which they hold is specified explicitly. The transformations are semantics preserving in the sense that they transform a TBox T into an equivalent TBox T 0 . 3.1 Concept Simplifications The procedure Simplif y(C) performs the following concept simplifications, re- placing the left-hand part with the right-hand part. The simplifications are ap- plied recursively considering that u, t are n-ary, commutative and associative: 9 http://www.tripadvisor.com 1. C u ⊥ 7→ ⊥ 2. C u > 7→ C 3. C uG C 7→ C, and for classical logic 4. C tG C 7→ C, and for classical logic 5. C t ⊥ 7→ C 6. C t > 7→ > 7. ∃R.⊥ 7→ ⊥ 8. ∀R.> 7→ > 9. ¬> 7→ ⊥ 10. ¬⊥ 7→ >, and for classical logic 11. ¬l ¬l C 7→ C, and for classical logic 12. ¬(C u D) 7→ ¬C t ¬D 13. ¬(C t D) 7→ ¬C u ¬D 14. ¬∀R.C 7→ ∃R.¬C, for Zadeh, Lukasiewicz, and classical logic 15. ¬∃R.C 7→ ∀R.¬C, for Zadeh, Lukasiewicz, and classical logic 16. C1 → C2 7→ ¬C1 t C2 , for Zadeh, Lukasiewicz, and classical logic 17. ¬(C1 → C2 ) 7→ C1 u ¬C2 , for Zadeh, Lukasiewicz, and classical logic 18. C u ¬C 7→ ⊥, for Lukasiewicz, Gödel , Product and classical logic 19. C t ¬C 7→ >, for Lukasiewicz, and classical logic 20. C u (C t D) 7→ C, for Gödel, Zadeh, and for classical logic 21. C t (C u D) 7→ C, for Gödel, Zadeh, and for classical logic 22. C u (¬C t D) 7→ C u D, for Gödel, and for classical logic 23. C t (¬C u D) 7→ C t D, for Gödel, and for classical logic 24. ∀R.C uG ∀R.D 7→ ∀R.(C uG D), and for classical logic 25. ∃R.C t ∃R.D 7→ ∃R.(C t D), for Gödel, Zadeh, and for classical logic 26. (C tG D) → E 7→ (C → E) uG (D → E), and for classical logic 27. C tG (D uG E) 7→ (C tG D) uG (C tG E), and for classical logic 28. ∃R.C uG ∃R.> 7→ ∃R.C, and for classical logic 29. C u (D u E) 7→ C u D u E 30. C t (D t E) 7→ C t D t E 31. C u (D tG E) 7→ (C u D) tG (C u E) 32. C t (D uG E) = (C u D) uG (C u E) 33. C → > 7→ > 34. > → C 7→ C 35. ⊥ → C 7→ > 36. C →r ⊥ 7→ ¬r C, where →r is an r-implication 3.2 Redundant GCIs Elimination The following axioms can safely be removed, since they are trivially satisfied: 1. h⊥ v C, αi, hC v >, αi and C = C 2. hC v C, αi, for any r-implication and Zadeh implication 3. hun i=1 Ci v A, li, if some Ci is A and v is an r-implication or Zadeh implication. 4. hA v tni=1 Ci , li, if some Ci is A and v is an r-implication or Zadeh implication. 3.3 Role Absorptions Basic Role Absorption. As in the classical case, > v ∀R.C and ∃R.> v C are equivalent to range(R, C) and domain(R, C), respectively, so we have the following rules [18] to transform these GCIs into domain and range restrictions: (RB1) Replace any GCI ∃R.> v C ∈ T with domain(R, C) (RB2) Replace any GCI > v ∀R.C ∈ T with range(R, C) Extended Role Absorptions. In the classical case, ∃R.C v D can be replaced with domain(R, ∃R.C → D) and D v ∀R.C can be replaced with domain(R, ∃R.¬C → ¬D), where C → D is ¬C t D. In the fuzzy case we have the following rules: (RE1) Replace any GCI ∃R.C v D ∈ T with domain(R, ∃R.C →G D) (RE2) Replace any GCI D v ∀R.C ∈ T with domain(R, ∃R.¬C →G ¬D), for Lukasiewicz and Zadeh logics. 3.4 Concept Absorption In the following, C, Ci are concepts, A, Aj are atomic concepts. Classical Case. For classical DLs we have the following definitions: GCI transformation rules. (CT1) Replace C v uni=1 Ci with C v Ci , for i ≤ n; (CT2) Replace tn i=1 Ci v C with Ci v C, for i ≤ n. Primitive concept absorption. (CA0) A v C is a possible absorbable GCI, A is the defined atom and A v C is its rewriting; (CA1) C v ¬A is a possible absorbable GCI, A is the defined atom and A v ¬C; is its rewriting (CA2) If some Cj is a negated atomic concept ¬A, then C v tn i=1 Ci is a possible absorbable GCI, A is the defined atom and A v ¬C t tn i=1,i6=j Ci is its rewriting; (CA3) If some Cj is an atomic concept A, then un i=1 Ci v C is a possible absorbable GCI, A is the defined atom and A v C t tn i=1,i6=j ¬Ci is its rewriting. Fuzzy Case. For fuzzy DLs we have the following definitions instead: GCI transformation rules. (FT1) Replace hC v C1 uG . . . uG Cn , αi with hC v Ci , αi, for i ≤ n; (FT2) Replace hC1 tG . . . tG Cn v C, αi with hCi v C, αi, for i ≤ n. Primitive concept absorption. (FA0) hA v C, αi is a possible absorbable GCI, A is the defined atom and hA v C, αi is its rewriting; (FA1) C v ¬l A is a possible absorbable GCI, A is the defined atom and A v ¬l C is its rewriting; (FA2.1) If some Cj is an atomic concept ¬A, then hC v tn i=1 Ci , αi is a possible ab- sorbable GCI, A is the defined atom and hA v ¬C t tn i=1,i6=j Ci , αi is its rewriting (for Lukasiewicz or Zadeh implication and Lukasiewicz t-conorm); (FA2.2) hC v A → D, αi is a possible absorbable GCI, A is the defined atom and hA v C → D, αi is its rewriting (if v and → are interpreted as the same r-implication); (FA3) If some Cj is an atomic concept A, then hun i=1 Ci v C, αi is a possible absorbable GCI, A is the defined atom and hA v (un i=1,i6=j Ci ) → C, αi is its rewriting (for v and → interpreted as the residuum of u, or for the triple hvz , ug , →g i, or hu, →i is the pair hug , →g i, α = 1 and v is any r-implication or Zadeh implication). (FA4) If some Cj is an atomic concept A, then htn i=1 Ci v C, αi is a possible absorbable GCI, A is the defined atom and hA v (un i=1,i6=j ¬Ci ) → C, αi is its rewriting (for Lukasiewicz logic). 3.5 GCI Absorption Algorithm Our algorithm has 3 phases: Phase A, a looping Phase B and a final Phase C. Phase A: This phase has the following steps: 1. Simplify the GCIs in T using the concept simplifications in Section 3.1 2. Remove redundant GCIs (Section 3.2) 3. Initialise Tg = Tdef = Tinc = Tdr = Tdisj = Tsyn = ∅ 4. Remove any range and domain axiom in T and add it to Tdr 5. Remove any disjointness axiom in T and add it to Tdisj 6. Remove any synonym axiom in T and add it to Tsyn 7. For any axiom τ ∈ T do (a) if τ is of the form hC v D, αi then add τ to Tg · (b) if τ is of the form C = D then add C v D and D v C to Tg Phase B: Apply iteratively the following steps to axioms τ ∈ Tg , in the order specified below, until none of these steps can be applied to any axiom in Tg . As soon as one step is applied once, we restart Phase B. Redundant GCIs removal. Remove redundant GCIs (Section 3.2). GCI transformations. If a GCI transformation rule can be applied to an axiom τ ∈ Tg , remove τ from Tg and add the obtained GCIs to Tg (see Section 3.4). Synonym absorption. If for τ ∈ Tg there is τ 0 ∈ Tg ∪ Tinc such that {τ, τ 0 } is {A v B, B v A} with A, B atomic, then remove τ, τ 0 from the sets they are · in and add A = B to Tsyn . Primitive concept absorption. If there is a possible absorbable GCI τ ∈ Tg , with defined atom A, A not defined in Tdef , then remove τ from Tg and add the rewriting of τ to Tinc (see Section 3.4). Definition absorption. If for some τ ∈ Tg there is τ 0 ∈ Tg ∪Tinc such that {τ, τ 0 } is {A v C, C v A} with A atomic, C non-atomic, A not defined in Tdef or · Tinc \ {τ 0 }, and Tdef ∪ {A = C} acyclic, then remove τ, τ 0 from the sets they · are in and add A = C to Tdef . Role absorption. If for some τ ∈ Tg a role absorption rule can be applied (Sec- tion 3.3), then remove τ from Tg and move the obtained restriction to Tdr . Phase C: Once none of the above steps in Phase B can be applied anymore, replace any axiom hC v D, αi ∈ Tg with an equivalent axiom h> v E, αi where E is the simplification of C → D using the rules in Section 3.1, and return the TBox partitioning hTu , Tg i, where Tu = Tdef ∪ Tinc ∪ Tdr ∪ Tdisj ∪ Tsyn . Example 3. Consider the TBox T = {A = B t C, A v D}. Then, it can be verified that under classical and Zadeh logic, the absorbed TBox is given by Tinc = {C v A, B v A, A v D, A v B t C} and Tg = Tdef = Tdisj = Tsyn = Tdr = ∅, while under Lukasiewicz logic the absorbed TBox is given by Tinc = {A v D, A v B t C, B v (¬C u A)} and Tg = Tdef = Tdisj = Tsyn = Tdr = ∅. Note that Example 3 also illustrates the usefulness of giving less priority to the “definition absorption” step. Usually, this step has highest priority. In that case Example 3 will not be absorbed completely. Also, the example shows that a non acyclic KB may be transformed into an acyclic one and, thus, avoiding the undecidability problem mentioned in the introduction. 4 Evaluation We have implemented the fuzzy GCI absorption algorithm in our fuzzyDL rea- soner, under Zadeh, Lukasiewicz, and classical logics. To evaluate our algorithm, we have selected 7 well-known classical ontologies: Economy, LUBM, FBbt XP, GALEN doctored (or GALEN-d), NCI, process and Transportation. We also have considered the fuzzy wine ontology, FuzzyWine. Table 1 shows some information for each ontology:the expressivity (column expressivity) and the number of classes (classes), primitive GCIs (subsCls), definitional GCIs (equivCls), domain restrictions (domain), range restrictions (range), disjoint restrictions, (disjoint) and general concept inclusions (GCIs). Table 1. Statistics of the considered ontologies. ontology expressivity classes subsCls equivCls domain range disjoint GCIs Economy ALCH(D) 337 409 0 47 41 142 0 FBbt XP SHI 7225 12043 1028 8 6 126 0 FuzzyWine SHIF (D) 177 212 57 12 8 2 9 GALEN-d ALEHIF + 2748 2881 681 0 0 0 357 LUBM ALEHI+(D) 43 36 6 25 18 0 0 NCI ALE 27652 46800 0 70 70 0 0 process SHOIN (D) 2294 2746 12 176 159 2 0 Transportation ALCH(D) 444 452 0 81 72 634 0 These ontologies were loaded in fuzzyDL using a parser translating from OWL 2 into fuzzyDL syntax [3], discarding the elements that fuzzyDL is not able to pro- cess, such as nominals. For this reason, the number of axioms in Table 1 may be smaller than in the original ontologies. The evaluation dataset can be downloaded from http://nmis.isti.cnr.it/~straccia/ftp/DL13.testonotologies.zip. Table 2 shows the same values after running the absorption algorithm for each of the three fuzzy logics considered. We include the semantics of the reasoner (column semantics with values z for Zadeh, l for Lukasiewicz and c for classical), the number of classes (classes), the sizes of Tinc , Tdef , Tsyn , Tdr , Tdisj , Tg and the running time (in seconds) of the absorption algorithm. The tests run under Mac OS X, 10.7.5, Mac Pro 2 x 3 GHz Dual-Core Intel Xeon, 9GB Ram. Note that that the number of disjoint constraints is constant, as our absorp- tion algorithm does not create new restrictions of these type. yet The results are similar for the 3 semantics. In terms of running time, the al- gorithm behaves similarly in the 3 cases. In terms of number of absorbed axioms, the semantics is not significant in Economy, NCI and Transportation, there are small differences in FBbt XP, GALEN-d, LUBM, FuzzyWine and process. In all the considered ontologies Tg is empty, which is important from a rea- soning effectiveness point of view. For instance, the reasoner gets out of memory when solving a simple query in some ontologies such as GALEN-d, but using the absorbed one our preliminary subsumption tests perform in a fraction of second. Table 2. Results of the absorption algorithm. semantics ontology Tinc Tdef Tsyn Tdr Tdisj Tg time c Economy 409 0 0 88 142 0 0.069 l Economy 409 0 0 88 142 0 0.069 z Economy 409 0 0 88 142 0 0.068 c FBbt XP 15187 0 0 14 126 0 1.959 l FBbt XP 14099 0 0 14 126 0 1.809 z FBbt XP 15187 0 0 14 126 0 1.678 l FuzzyWine 328 0 0 27 2 0 0.079 z FuzzyWine 392 0 0 27 2 0 0.092 c GALEN-D 5507 0 18 0 0 0 1.601 l GALEN-D 4600 0 18 0 0 0 1.295 z GALEN-D 5507 0 18 0 0 0 1.315 c LUBM 54 0 0 43 0 0 0.02 l LUBM 48 0 0 43 0 0 0.017 z LUBM 54 0 0 43 0 0 0.02 c NCI 46800 0 0 140 0 0 2.177 l NCI 46800 0 0 140 0 0 2.174 z NCI 46800 0 0 140 0 0 2.187 c process 2785 1 235 338 2 0 1.18 l process 2769 1 235 338 2 0 1.214 z process 2785 1 235 338 2 0 1.214 c Transportation 452 0 0 153 634 0 0.075 l Transportation 452 0 0 153 634 0 0.075 z Transportation 452 0 0 153 634 0 0.074 5 Conclusions We have worked out a first absorption algorithm for fuzzy DLs. We implemented it into the fuzzyDL reasoner and evaluated it over some ontologies, and our preliminary results seem to be very encouraging. There are several directions for future research related to optimised fuzzy DL reasoning that need to be addressed: Absorption. We plan to investigate and evaluate more deeply our absorption algorithm considering more ontologies and several heuristics (e.g., which atom to select for absorption and concept name unfolding) such as those reported in the literature [1, 11, 12, 18–20, 24]. Classification. While we already have implemented in fuzzyDL all fuzzy lazy unfolding rules related to absorbed TBoxes and preliminary subsumption tests perform in a fraction of second, a non trivial optimised fuzzy classifica- tion algorithm in the style of e.g., [6] has still to be worked out. It seems that classification is more involved in the fuzzy case (if concrete domains are in- volved or GCIs are graded) because, contrary to the crisp case, one may have T |= hA v B, n1 i, T |= hB v A, β2 i, T |= hB v C, β3 i, T |= hA v C, β4 i, with 0 < β1 6= β2 ≤ 1 and 0 < β1 ⊗ β3 < β4 ≤ 1. Instance retrieval. Other important tasks to optimise are instance check- ing, i.e., determining the best entailment degree bed(K, a:C) = sup{α | K |= ha:C, αi}, and instance retrieval, i.e., determining the set ans(K, C) = {ha, αi | α = bed(K, a:C)} [7, 8, 10, 16, 21, 22]. In that direction, fuzzyDL already implements a fuzzy variant of anywhere blocking [15]. References 1. F. Baader, D. Calvanese, D. McGuinness, D. Nardi, and P. F. Patel-Schneider, edi- tors. The Description Logic Handbook: Theory, Implementation, and Applications. Cambridge University Press, 2003. 2. F. Bobillo and U. Straccia. fuzzyDL: An expressive fuzzy description logic reasoner. In 2008 International Conference on Fuzzy Systems (FUZZ-IEEE 2008), pp. 923– 930. IEEE Computer Society, 2008. 3. F. Bobillo and U. Straccia. Fuzzy ontology representation using OWL 2. Interna- tional Journal of Approximate Reasoning, 52:1073–1094, 2011. 4. S. Borgwardt and R. Peñaloza. Undecidability of fuzzy description logics. In Proceedings of the 13th International Conference on Principles of Knowledge Rep- resentation and Reasoning (KR 2012), pp. 232–242, 2012. AAAI Press. 5. M. Cerami and U. Straccia. On the (un)decidability of fuzzy description logics under lukasiewicz t-norm. Information Sciences, 227:1–21, 2013. 6. B. Glimm, I. Horrocks, B. Motik, R. Shearer, and G. Stoilos. A novel approach to ontology classification. Journal of Web Semantics, 14:84–101, 2012. 7. V. Haarslev and R. Möller. On the scalability of description logic instance retrieval. Journal of Automated Reasoning, 41(2):99–142, 2008. 8. V. Haarslev, H.-I. Pai, and N. Shiri. Optimizing tableau reasoning in alc extended with uncertainty. In Proceedings of the 2007 International Workshop on Descrip- tion Logics (DL 2007), 2007. 9. P. Hájek. Metamathematics of Fuzzy Logic. Kluwer, 1998. 10. I. Horrocks, L. Li, D. Turi, and S. Bechhofer. The instance store: DL reasoning with large numbers of individuals. In Proceedings of the 2004 Description Logic Workshop (DL 2004), pp. 31–40, 2004. 11. I. Horrocks and S. Tobies. Reasoning with axioms: Theory and practice. In Proceed- ings of the 7th International Conference on Principles of Knowledge Representation and Reasoning (KR 2000), pp. 285–296. Morgan Kaufman, 2000. 12. A. K. Hudek and G. E. Weddell. Binary absorption in tableaux-based reason- ing for description logics. In Proceedings of the 2006 International Workshop on Description Logics (DL 2006), volume 189 of CEUR Workshop Proceedings, 2006. 13. G. J. Klir and B. Yuan. Fuzzy sets and fuzzy logic: theory and applications. Prentice-Hall, Inc., 1995. 14. T. Lukasiewicz and U. Straccia. Managing uncertainty and vagueness in description logics for the semantic web. Journal of Web Semantics, 6:291–308, 2008. 15. B. Motik, R. Shearer, and I. Horrocks. Optimized reasoning in description log- ics using hypertableaux. In Proceedings of the 21st International Conference on Automated Deduction: Automated Deduction, CADE-21, pp. 67–83, 2007. Springer- Verlag. 16. N. Simou, T. P. Mailis, G. Stoilos, and G. B. Stamou. Optimization techniques for fuzzy description logics. In Proceedings of the 23rd International Workshop on Description Logics (DL 2010), volume 573 of CEUR Electronic Workshop Pro- ceedings, 2010. 17. U. Straccia. Description logics with fuzzy concrete domains. In 21st Conference on Uncertainty in Artificial Intelligence (UAI 2005), pp. 559–567, 2005. AUAI Press. 18. D. Tsarkov and I. Horrocks. Efficient reasoning with range and domain constraints. In Proceedings of the 2004 Description Logic Workshop (DL 2004), pp. 41–50, 2004. 19. D. Tsarkov, I. Horrocks, and P. F. Patel-Schneider. Optimizing terminologi- cal reasoning for expressive description logics. Journal of Automated Reasoning, 39(3):277–316, 2007. 20. J. Wu and V. Haarslev. Planning of axiom absorption. In Proceedings of the 21st International Workshop on Description Logics (DL 2008), volume 353 of CEUR Workshop Proceedings, 2008. 21. J. Wu, A. K. Hudek, D. Toman, and G. E. Weddell. Absorption for aboxes. In Proceedings of the 2012 International Workshop on Description Logics (DL 2012), volume 846 of CEUR Workshop Proceedings, 2012. 22. J. Wu, A. K. Hudek, D. Toman, and G. E. Weddell. Assertion absorption in object queries over knowledge bases. In Proceedings of the 13th International Conference Principles of Knowledge Representation and Reasoning (KR 2012). AAAI Press, 2012. 23. L. A. Zadeh. Fuzzy sets. Information and Control, 8(3):338–353, 1965. 24. M. Zuo and V. Haarslev. High performance absorption algorithms for terminolog- ical reasoning. In Proceedings of the 2006 International Workshop on Description Logics (DL 2006), volume 189 of CEUR Workshop Proceedings, 2006.