A Crisp Representation for Fuzzy SHOIN with Fuzzy Nominals and General Concept Inclusions Fernando Bobillo, Miguel Delgado, and Juan Gómez-Romero? Department of Computer Science and Artificial Intelligence, University of Granada C. Periodista Daniel Saucedo Aranda, 18071 Granada, Spain Phone: +34 958243194; Fax: +34 958243317 Email: fbobillo@decsai.ugr.es, mdelgado@ugr.es, jgomez@decsai.ugr.es Abstract. Fuzzy Description Logics are a family of logics which allow the representation of (and the reasoning within) structured knowledge affected by uncertainty and vagueness. They were born to overcome the limitations of classical Description Logics when dealing with such kind of knowledge, but they bring out some new challenges, requiring an ap- propriate fuzzy language to be agreed and needing practical and highly optimized implementations of the reasoning algorithms. In the current paper we face these problems by presenting a reasoning preserving proce- dure to obtain a crisp representation for a fuzzy extension of SHOIN , which makes possible to reuse a crisp representation language as well as currently available reasoners, which have demonstrated a very good performance in practice. As an additional contribution, we define the syntax and semantics of a novel fuzzy version of the nominal construct and allow to reason within fuzzy general concept inclusions. 1 Introduction Ontologies [1] are a core element in the layered architecture of the Semantic Web [2]. Description Logics (DLs for short) [3] are a family of logics for repre- senting structured knowledge. The name of each logic is composed by some labels which identify the constructs of the logic. DLs have been proved to be very useful as ontology languages [4]. As it has been widely pointed out, classical ontolo- gies and DLs are not appropriate to handle uncertain knowledge [5, 6] and since uncertainty is inherent to a lot of real-world application domains, the Semantic Web will not be fully operative as long as it does not provide means to manage it. A well studied solution is to extend DLs with fuzzy sets theory [7], producing fuzzy DLs (denoted with an f preceding the name of the corresponding DL and a subscript denoting the family of fuzzy operators considered e.g. fKD SHOIN uses maximum t-conorm, minimum t-norm, and Kleene-Dienes implication). ? Fernando Bobillo holds a FPU scholarship from the Spanish Ministerio de Educación y Ciencia. Juan Gómez-Romero holds a scholarship from Consejera de Innovación, Ciencia y Empresa (Junta de Andalucı́a). Nowadays, the World Wide Web Consortium (W3C) standard for ontology representation is OWL Web Ontology Language1 , a language comprising three sublanguages of increasing expressive power: OWL Lite, OWL DL and OWL Full (being OWL DL the most used level and nearly equivalent to SHOIN (D) [8] but without customised datatypes). In order to deal with uncertain knowledge, OWL may be extended to a fuzzy DL-based language e.g. FuzzyOWL [6], with the drawback that the large number of resources available (e.g. editors, reason- ers or ontologies to be imported) should be adapted. Furthermore, reasoning within expressive DLs has a very high worst-case complexity (e.g. NPspace in SHOIN ) and, consequently, there exists a significant gap between the design of a decision procedure and the achievement of a practical implementation [9] (as a matter of fact, some of the OWL DL reasoners used in practice do not support full SHOIN (D) e.g. Racer [10] and FaCT [11]). Regarding fuzzy DLs, there does not exist any implemented reasoner for f SHOIN . A reasoner for f SHIN (D) has been recently developed (fuzzyDL 2 ), but its efficiency is still to be investigated. Moreover, the experience with crisp DLs ( [9]) induces us to think that developing highly optimized implementations will be a hard task where ad-hoc mechanisms should be used for every particular fuzzy DL. An alternative way to obtain fuzzy ontologies facing these two problems is i) to represent fuzzy DLs using crisp DLs and ii) to reduce reasoning within fuzzy DLs to reasoning within crisp DLs. This way it would be possible to translate them automatically into a crisp ontology language (e.g. OWL) and to use currently available reasoners (e.g. Pellet [12]). Unfortunately, there does not exist a lot of work following this line and the logics investigated are still far from OWL DL: [13] shows a reasoning preserving procedure for f ALCH, [14] considers f ALC with truth values taken from an uncertainty lattice and [15], a restricted version of f ALCQ (e.g. they do not allow to reason within a TBox). On the other hand, current fuzzy DLs still present some limitations which we think that should be overcome. Some works on fuzzy DLs deal with nominals (named individuals) but they choose not to fuzzify the nominal construct arguing that a fuzzy singleton set does not represent any real concept world [5, 6]. Hence, only crisp concepts can be defined extensively, as nominals either have to fully belong to them or not. Besides, although there have been proposed fuzzy general concept inclusions (which allow to constrain the truth value of a general concept inclusion or GCI) [5], current reasoning algorithms do not allow them. Our work provides the following contributions. Firstly, we propose a differ- ent definition of f SHOIN , including a fuzzy nominal construct and fuzzy GCIs. Secondly, we reduce reasoning in fKD SHOIN to reasoning in SHOIN , extend- ing [13]. To the very best of our knowledge, there does not exist any reasoning algorithm dealing with such kind of fuzzy GCIs. The present paper is organized as follows. In the next section, we describe our fuzzy extension of SHOIN . Then, Sect. 3 shows how to reduce it into crisp SHOIN . Finally, in Sect. 4 we set out some conclusions and ideas for future work. 1 http://www.w3.org/TR/owl-features 2 http://gaia.isti.cnr.it/~straccia/software/fuzzyDL/fuzzyDL.html 2 Fuzzy SHOIN In this section we define f SHOIN , which extends SHOIN to the fuzzy case by letting (i) concepts denote fuzzy sets of individuals and (ii) roles denote fuzzy binary relations between individuals. Our logic is similar to [5, 6], adding fuzzy nominals and fuzzy GCIs. In fuzzy DLs most reasoning services are reducible to fKB satisfiability [16], so here in after we will only consider this task. Syntax. f SHOIN assumes three alphabets of symbols, for concepts, roles and individuals. The concepts of the language (denoted C or D) can be built in- ductively from atomic concepts (A), atomic roles (R), top concept >, bottom concept ⊥, named individuals (oi ) and simple roles (S)3 according to the follow- ing syntax rule (where n, m are natural numbers, n ≥ 0, m > 0, αi ∈ [0, 1]): C, D → A | (atomic concept) > | (top concept) ⊥ | (bottom concept) C u D | (concept conjunction) C t D | (concept disjunction) ¬C | (concept negation) ∀R.C | (universal quantification) ∃R.C | (full existential quantification) {(o1 , α1 ), . . . , (om , αm )} | (nominals) (≥ n S) | (at-least unqualified number restriction) (≤ n S) (at-most unqualified number restriction) If RA is an atomic role, complex roles are built using this syntax rule: R → RA | R − A fuzzy Knowledge Base (fKB) comprises two parts: the intensional knowl- edge, i.e. general knowledge about the application domain (a fuzzy Terminolog- ical Box or TBox KT and a fuzzy Role Box or RBox KR ), and the extensional knowledge, i.e. particular knowledge about some specific situation (a fuzzy As- sertional Box or ABox KA with statements about individuals). A fuzzy ABox f KA consists of a finite set of fuzzy assertions, which can be individual assertions or constraints on the truth value of a concept or role assertion. An individual as- sertion is either an inequality of individuals ha 6= bi or an equality of individuals ha = bi (they are necessary since we do not impose unique name assumption). A constraint on the truth value of a concept or role assertion is an expression of the form hΨ ≥ αi, hΨ > βi, hΦ ≤ βi, hΦ < αi, where Ψ is an assertion of the form a : C or (a, b) : R, Φ is an assertion of the form a : C, α ∈ (0, 1] and β ∈ [0, 1)). 3 A simple role is a non transitive role not having transitive sub-roles i.e. R is a sub-role of R0 if R v ∗R0 , where v ∗ is the transitive-reflexive closure of v Note that fuzzy assertions of the form h(a, b) : R ≤ βi, h(a, b) : R < αi are not allowed since they relate to negated roles, which are not part of SHOIN . A fuzzy TBox f KT consists of a finite set of fuzzy terminological axioms. A fuzzy terminological axiom is either a fuzzy GCI or a concept definition. A fuzzy GCI constrains the truth value of a GCI i.e. it is an expression of the form hΩ ≥ αi, hΩ > βi, hΩ ≤ βi or hΩ < αi, where Ω is a GCI of the form C v, α ∈ (0, 1] and β ∈ [0, 1). We think that concept definitions should not be fuzzified, so C ≡ D is an abbreviation of the pair of axioms hC v D ≥ 1i and hD v C ≥ 1i. A fuzzy RBox f KR consists of a finite set of fuzzy role axioms. A fuzzy role axiom is either a fuzzy role inclusion R v R0 , a fuzzy role definition R ≡ R0 (a short hand for both R v R0 and R0 v R) or a transitive role axiom trans(R). Semantics. A fuzzy interpretation I is a pair (∆I , ·I ) consisting of a non empty set ∆I (the interpretation domain) and a fuzzy interpretation function ·I mapping every individual onto an element of ∆I , every concept C onto a function C I : ∆I → [0, 1] and every role R onto a function RI : ∆I × ∆I → [0, 1]. C I (resp. RI ) is interpreted as the membership degree function of the fuzzy concept C (resp. fuzzy rol R) w.r.t. I. C I (a) (resp. RI (a, b)) gives us the degree of being the individual a an element of the fuzzy concept C (resp. the degree of being (a, b) an element of the fuzzy role R) under the fuzzy interpretation I. The fuzzy interpretation function is extended to complex concepts and roles as: >I (a) = 1 ⊥I (a) = 0 (C u D)I (a) = C I (a) ∧ DI (a) (C t D)I (a) = C I (a) ∨ DI (a) (¬C)I (a) = ¬C I (a) (∀R.C)I (a) = inf b∈∆I {RI (a, b) → C I (b)} (∃R.C)I (a) = supb∈∆I {RI (a, b) ∧ C I (b)} {(o1 , α1 ), . . . , (om , αm )}I (a) = supi | a∈{oIi } αi (≥ 0)I (a) = >I (a) = 1 (≥ m)I (a) = supb1 ,...,bm ∈∆I [∧m I V i=1 S (a, bi ) ∧i β, ≤ β and < α. – A fuzzy assertion h(a, b) : R ≥ αi iff RI (aI , bI ) ≥ α. Similar definitions can be given for > β, ≤ β and < α. – An assertion ha 6= bi iff aI 6= bI (resp. ha = bi iff aI = bI ). Note that we consider individuals assertions to be crisp. – A fuzzy GCI hC v D ≥ αi iff inf a∈∆I {C I (a) → DI (a)} ≥ α. Similar definitions can be given for > β, ≤ β and < α. – A concept definition C ≡ D iff C I = DI . – A role inclusion axiom R v R0 iff RI ⊆ R0I . – A role definition axiom R ≡ R0 iff RI = R0I . – An axiom trans(R) iff ∀a, b ∈ ∆I , RI (a, b) ≥ supc∈∆I RI (a, c) ∧ RI (c, b). – A fKB hf KA , f KT , f KR i iff it satisfies each element in KA , KT and KR . The definition of fuzzy GCIs allows concept subsumption to hold to a certain degree in [0, 1]. This does not hold for role inclusion axioms, which leads to a certain asymmetry in the expressivity. While this is not too elegant, it is a restriction imposed by the choice of the implication function, which would require the subjacent DL to have negated roles and role disjunction. However, for a higher practical utility, we have preferred to restrict ourselves to SHOIN , closer to the DL underlying OWL DL. The following lemma shows that our definition of f SHOIN is a sound ex- tension of crisp SHOIN : Lemma 1. Fuzzy interpretations coincide with crisp interpretations if we re- strict to the membership degrees of 0 and 1 [6]. Some properties. Here in after we will concentrate on fKD SHOIN , restrict- ing ourselves to the minimum t-norm a ∧ b = min{a, b}, maximum t-conorm a ∨ b = max{a, b}, Lukasiewicz negation ¬a = 1 − a and the Kleene-Dienes im- plication a → b = max{1 − a, b}. For instance, in the semantics of the at-least unqualified number restriction, ∧i 1 − β and ./= {≥, >}, the following prop- erties are verified: (i) ha : C ./ αi and hC v D ./ βi imply ha : D ≥ βi. (ii) h(a, b) : R ./ γi and hR v R0 i imply h(a, b) : R0 ./ γi. (iii) h(a, b) : R ./ αi and ha : ∀R.C ./ βi imply hb : C ./ βi. Unfortunately, the use of Kleene-Dienes implication in the semantics of fuzzy GCIs brings about two counter-intuitive effects. Firstly, a concept does not fully subsume itself i.e. C v C ⇒ inf a∈∆I max{1 − C I (a), C I (a)} = 0.5. Secondly, crisp concept subsumption forces fuzzy concepts to be crisp i.e. hC v D ≥ 1i ⇒ inf a∈∆I max{1 − C I (a), DI (a)} ≥ 1 which is true iff for each element of the domain DI (a) = 1 or 1 − C I (a) ≥ 1 ⇒ C I (a) = 0. These problems point out the need of further investigation involving alternative fuzzy operators. For example, using a residuum based implications (see [18] for a refresh on fuzzy operators) it is always true that a → b = 1 if a ≤ b, which would fix the first problem; while using Lukasiewicz implication (a → b = min{1, 1 − a + b}) would fix the second one. 3 A Crisp Representation for Fuzzy SHOIN In this section we show how to reduce a fKD SHOIN fKB into a crisp Knowledge Base (KB). The procedure preserves reasoning, so existing SHOIN reasoners could be applied to the resulting KB. [13] presents a reasoning pre- serving transformation for fKD ALCH into crisp ALCH: firstly, some new atomic concepts and roles are defined, then some new axioms are added to preserve the semantics of the fKB and finally the ABox, the TBox and the RBox are mapped separately. Our reduction extends this work to fKD SHOIN . A slight difference is that our mapping of the TBox can introduce some new assertions about new individuals (not appearing in the initial fKB). New Elements. Let Af K and Rf K be the set of atomic concepts and atomic roles occurring in a fKB f K = hf KA , f KT , f KR i. In [13] it is shown that the set of the degrees which must be considered for any reasoning task is defined as N f K = X f K ∪ {1 − α|α ∈ X f K }, where X f K is defined as follows: X f K = {0, 0.5, 1} ∪ {α|hΨ ≥ αi ∈ f KA } ∪ {β|hΨ > βi ∈ f KA } ∪{1 − β|hΦ ≤ βi ∈ f KA } ∪ {1 − α|hΦ < αi ∈ f KA } ∪{α|hΩ ≥ αi ∈ f KT } ∪ {β|hΩ > βi ∈ f KT } ∪{1 − β|hΩ ≤ βi ∈ f KT } ∪ {1 − α|hΩ < αi ∈ f KT } This also holds in fKD SHOIN , but note that it is no longer true when other fuzzy operators are considered. In that case, the process may calculate all possi- ble degrees in [0, 1] with a given precision, but further investigation is required. Without loss of generality, it can be assumed that N f K = {γ1 , . . . , γ|N f K | } and γi < γi+1 , 1 ≤ i ≤ |N f K | − 1. Now, for each α, β ∈ N f K , α ∈ (0, 1], β ∈ [0, 1), for each relation in {≥, > , ≤, <}, for each A ∈ Af K and for each R ∈ Rf K , four new atomic concepts A≥α , A>β , A≤β , A<α and two new atomic roles R≥α , R>β are introduced. A≥α represents the crisp set of individuals which are instance of A with degree higher or equal than α i.e the α-cut of A. The other new elements are defined in a similar way. Neither A<0 , A>1 , R>1 are considered (they are always empty sets) nor A≤1 , A≥0 , R≥0 (they are always equivalent to the top concept). The semantics of these newly introduced atomic concepts and roles is pre- served by some terminological and role axioms. For each 1 ≤ i ≤ |N f K | − 1, for each 2 ≤ j ≤ |N f K |, for each A ∈ Af K and for each R ∈ Rf K , T (N f K ) is the smallest terminology containing the following axioms: A≥γi+1 v A>γi A>γi v A≥γi A<γj v A≤γj A≤γi v A<γi+1 A≥γj u A<γj v ⊥ A>γi u A≤γi v ⊥ > v A≥γj t A<γj > v A>γi t A≤γi Similarly, R(N f K ) is the smallest terminology containing these two axioms: R≥γi+1 v R>γi R>γi v R≥γi It is easy to see that allowing expressions of the type h(a, b) : R ≤ βi, h(a, b) : R < αi would need additional role constructs (role conjunction, role disjunction, bottom role and top role). Mapping the ABox. Fuzzy assertions are mapped into SHOIN assertions using a mapping σ. Let γ ∈ N f K , ./∈ {≥, <, ≤, >}, σ(f KA ) = {σ(Φ)|Φ ∈ f KA }, where σ(Φ) is defined as in the following table (where ρ is inductively defined on the structure of concepts and roles as in Table 1): σ(ha : C ./ γi) = a : ρ(C, ./ γ) σ(h(a, b) : R ./ γi) = (a, b) : ρ(R, ./ γ) σ(ha 6= bi) = a 6= b σ(ha = bi) = a = b Mapping the TBox. f SHOIN fuzzy terminological axioms to either termi- nological axioms (for ≥ or >) or assertions S (for ≤ and <). In the former case, we redefine k(f K, f KT ) as k(f K, f KT ) = Ω∈f KT k(Ω), where Ω = hC v D{≥, > }γi and k(Ω) is defined as: k(hC v D ≥ γi) = ρ(C, > 1 − γ) v ρ(D, ≥ γ) k(hC v D > γi) = ρ(C, ≥ 1 − γ) v ρ(D, > γ) In the latter case, new assertions are necessary since negated terminological axioms are nor part of crisp SHOIN S . A new function A(f KT ) adds these new assertions to the ABox. A(f KT ) = Ξ∈f KT A(Ξ), where Ξ = hC v D{≤, <}γi and A(Ξ) is defined as: A(hC v D ≤ γi) = x : ρ(C, ≥ 1 − γ) u ρ(D, ≤ γ) A(hC v D < γi) = x : ρ(C, > 1 − γ) u ρ(D, < γ) Note that how to modify the reduction process when alternative implication functions are used remains an open question. Mapping S the RBox. Role axioms are reduced using a function k(f K, f KR ) = Ω∈f KR k(Ω), where k(Ω) is defined as: k(R v R0 ) = γ∈N f K ,./∈{≥,>} ρ(R, ./ γ) v ρ(R0 , ./ γ) S S k(trans(R)) = γ∈N f K ,./∈{≥,>} trans(ρ(R, ./ γ)) Table 1. Mapping ρ x y ρ(x, y) A ≥γ A≥γ if γ 6= 0, > otherwise A >γ A>γ , if γ 6= 1, ⊥ otherwise A ≤γ A≤γ if γ 6= 0, > otherwise A <γ A<γ , if γ 6= 1, ⊥ otherwise R ≥γ R≥γ if γ 6= 0, > otherwise R >γ R>γ , if γ 6= 1, ⊥ otherwise > ≥γ > > >γ > if γ 6= 1, ⊥ otherwise > ≤γ > if γ = 1, ⊥ otherwise > <γ ⊥ ⊥ ≥γ > if γ = 0, ⊥ otherwise ⊥ >γ ⊥ ⊥ ≤γ > ⊥ <γ > if γ 6= 0, ⊥ otherwise C uD {≥, >} γ ρ(C, {≥, >} γ) u ρ(D, {≥, >} γ) C uD {≤, <} γ ρ(C, {≤, <} γ) t ρ(D, {≤, <} γ) C tD {≥, >} γ ρ(C, {≥, >} γ) t ρ(D, {≥, >} γ) C tD {≤, <} γ ρ(C, {≤, <} γ u ρ(D, {≤, <} γ) ¬C {≥, >} γ ρ(C, {≤, <} 1 − γ) ¬C {≤, <} γ ρ(C, {≥, >} 1 − γ) ∃R.C {≥, >} γ ∃ρ(R, {≥, >} γ).ρ(C, {≥, >} γ) ∃R.C {≤, <} γ ∀ρ(R, {>, ≥} γ).ρ(C, {≤, <} γ) ∀R.C {≥, >} γ ∀ρ(R, {>, ≥} 1 − γ).ρ(C, {≥, >} γ) ∀R.C {≤, <} γ ∃ρ(R, {≥, >} 1 − γ).ρ(C, {≤, <} γ) {(o1 , α1 ), . . . , (om , αm )} ./ γ {oi | αi ./ γ, 1 ≤ i ≤ n}./γ ≥0S ./ γ ρ(>, ./ γ) ≥mS {≥, >} γ ≥ m ρ(S, {≥, >} γ) ≥mS {≤, <} γ ≤ m−1 ρ(S, {>, ≥} γ) ≤nS {≥, >} γ ≤ n ρ(S, {>, ≥} 1 − γ) ≤nS {≤, <} γ ≥ n+1 ρ(S, {≥, >} 1 − γ) R− ./ γ ρ(R, ./ γ)− Discussion. A fKB f K = hf KA , f KT , f KR i is reduced into a KB K(f K) = hσ(f KA ) ∪ A(f KT ), T (N f K ) ∪ k(f K, f KT ), R(N f K ) ∪ k(f K, f KR )i. The com- plexity of our procedure is quadratic: the ABox is linear while the TBox and the RBox are quadratic. It is interesting to note that, while [13] reduces a fuzzy terminological axiom into a set of crisp terminological axioms, our semantics for fuzzy GCIs allows to reduce each axiom into either an axiom or an assertion. This reduction in the size of the TBox (although it is still quadratic) is very in- teresting since reasoning with GCIs is a source of computational complexity [19]. Finally, an important theorem can be shown: Theorem 1. A fKD SHOIN fKB f K is satisfiable iff K(f K) is satisfiable. Unfortunately, we cannot show the proof due to space limitations. Firstly, it has to be proved that the translation preserves the satisfiability of every single statement of the fKB. It can be shown that, if there exists a fuzzy interpreta- tion satisfying a statement, then a crisp interpretation satisfying the result of its translation can be built. Secondly, it has to be proved that the translation preserves the satisfiability of the whole fKB. Then, it has be shown that the translation preserves the clashes. For example, the clash produced by the pair of conjugated axioms ha : A ≥ γi and ha : A < γi is preserved, since the axiom A≥γ u A<γ v ⊥ prevents any individual from belonging to A with degree ≥ γ and degree < γ. 4 Conclusions and Future Work This paper has presented an alternative approach to achieve fuzzy ontologies, reusing currently existing crisp ontology languages and reasoners. In particu- lar, after having presented a sound fuzzy extension of SHOIN including fuzzy nominals (enabling to define fuzzy sets extensively) and fuzzy GCIs (allowing to constrain the truth value of a GCI), we have presented a reasoning preserv- ing procedure (quadratic in complexity) to reduce a fKD SHOIN fKB into a crisp one. The semantics of fuzzy GCIs reduces the size of the resulting TBox w.r.t. [13], but imposes some counter-intuitive effects. The main direction for future work is to perform an empirical evaluation in order to validate the theoretical results. From a theoretical point view, we are considering different fuzzy operators to avoid the counter-intuitive effects of the Kleene-Dienes implication. We also plan to include a crisp representation for fuzzy datatypes. Since OWL does not currently allow to define customised datatypes, it seems interesting to consider OWL Eu [20], a promising extension of OWL supporting them. Another interesting direction for future research is to consider the more expressive DL SROIQ [21] (providing some additional role constructs such as disjoint roles and negated role assertions) and which is the subjacent DL of OWL 1.14 , an extension of OWL which has been recently proposed. We think that the additional expressivity may help to overcome the asymmetry in the definitions of fuzzy concept and role inclusion axioms. 4 http://www-db.research.bell-labs.com/user/pfps/owl/overview.html References 1. Gruber, T.R.: A translation approach to portable ontologies. Knowledge Acquisi- tion 5(2) (1993) 199–220 2. Berners-Lee, T., Hendler, J., Lassila, O.: The semantic web. Scientific American 284(5) (2001) 34–43 3. Baader, F., Calvanese, D., McGuinness, D., Nardi, D., Patel -Schneider, P.F.: The Description Logic Handbook: Theory, Implementation, and Applications. Cam- bridge University Press (2003) 4. Baader, F., Horrocks, I., Sattler, U.: Description logics as ontology languages for the semantic web. Volume 2605 of LNCS., Springer 5. Straccia, U.: A fuzzy description logic for the semantic web. In Sanchez, E., ed.: Fuzzy Logic and the Semantic Web. Volume 1 of Capturing Intelligence. Elsevier Science (2006) 73–90 6. Stoilos, G., Stamou, G., Tzouvaras, V., Pan, J.Z., Horrocks, I.: Fuzzy OWL: Uncertainty and the Semantic Web. In: Proceedings of the International Workshop on OWL: Experience and Directions (OWL-ED2005). (2006) 7. Zadeh, L.A.: Fuzzy sets. Information and Control 8 (1965) 338–353 8. Horrocks, I., Schneider, P.F.P.: Reducing OWL entailment to description logic satisfiability. Journal of Web Semantics 1(4) (2004) 345–357 9. Sirin, E., Grau, B.C., Parsia, B.: From wine to water: Optimizing description logic reasoning for nominals. In: Proceedings of KR-2006. (2006) 90–99 10. Haarslev, V., Möller, R.: Racer system description. In Proceedings of IJCAR-01. Volume 2083 of LNCS., Springer (2001) 701–705 11. Horrocks, I.: Using an expressive description logic: FaCT or fiction? In Cohn, A.G., Schubert, L., Shapiro, S.C., eds.: Proceedings of the Sixth International Conference on the Principles of Knowledge Representation and Reasoning (KR’98), Morgan Kaufmann Publishers (1998) 636–647 12. Sirin, E., Parsia, B., Grau, B.C., Kalyanpur, A., Katz, Y.: Pellet: A practical OWL-DL reasoner. Technical Report 2005-68, University of Maryland Institute for Advanced Computer Studies (UMIACS) (2005) 13. Straccia, U.: Transforming fuzzy description logics into classical description logics. In: Proceedings of JELIA-04. Volume 3229 of LNCS., Springer (2004) 385–399 14. Straccia, U.: Description logics over lattices. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems 14(1) (2006) 1–16 15. Li, Y., Xu, B., Lu, J., Kang, D.: Reasoning technique for extended fuzzy ALCQ. In: Proceedings of ICCSA 2006 (Part II). Volume 3981 of LNCS., Springer (2006) 1179–1188 16. Straccia, U.: Reasoning within fuzzy description logics. Journal of Artificial Intel- ligence Research 14 (2001) 137–166 17. Straccia, U.: A fuzzy description logic. In: Proceedings of the 15th National Conference on Artificial Intelligence (AAAI-98). (1998) 594–599 18. Klir, G.J., Yuan, B.: Fuzzy Sets and Fuzzy Logic: Theory and Applications. Prentice-Hall (1995) 19. Nebel, B.: Terminological reasoning is inherently intractable. Artificial Intelligence 43(2) (1990) 235–249 20. Pan, J.Z., Horrocks, I.: OWL-Eu: Adding customised datatypes into OWL. In Proceedings of ESWC 2005. Volume 3532 of LNCS., Springer (2005) 21. Horrocks, I., Kutz, O., Sattler, U.: The even more irresistible SROIQ. In: Pro- ceedings of KR-2006. (2006) 452–457