The Fuzzy Description Logic f-SHIN Giorgos Stoilos1 , Giorgos Stamou1 , Vassilis Tzouvaras1 , Jeff Z. Pan2 and Ian Horrocks2 1 Department of Electrical and Computer Engineering, National Technical University of Athens, Zographou 15780, Greece 2 School of Computer Science, The University of Manchester Manchester, M13 9PL, UK Abstract. In the Semantic Web information would be retrieved, pro- cessed, combined, shared and reused in the maximum automatic way possible. Obviously, such procedures involve a high degree of uncertainty and imprecision. For example ontology alignment or information retrieval are rarely true or false procedures but usually involve confidence degrees or provide rankings. Furthermore, it is often the case that information itself is imprecise and vague like the concept of a “tall” person, a “hot” place and many more. In order to be able to represent and reason with such type of information in the Semantic Web (SW), as well as, enhance SW applications we present an extension of the Description Logic SHIN with fuzzy set theory. We present the semantics as well as detailed rea- soning algorithms for the extended language. 1 Introduction Uncertainty, like imprecision and vagueness, is a factor that can cause the degra- dation of the performance of a system. To this end, many applications and do- mains have incorporated mathematical frameworks that deal with such type of information, resulting in the improvement of their effectiveness. Applications like robotics [1], computer vision [2] and many more have embraced frameworks like fuzzy set theory [3] in order to improve their performance. On the other hand, in the Semantic Web context, little work has been carried out towards this direc- tion. Apart from the fact that uncertainty is many times a feature of information itself, as for example the concepts of a “tall” man, a “fast” car, a “blue” sky and many more, applications like information retrieval, automatic information sharing and reuse are hardly true or false procedures but rather a matter of a degree. The need for covering vagueness in the Semantic Web has been stressed many times the past years [4–6]. It has been pointed out that dealing with such information would improve many Semantic Web applications [7–9]. Knowledge in the SW is usually structured in the form of ontologies [10]. This has led to considerable efforts to develop a suitable ontology language, culminating in the design of the OWL Web Ontology Language [11], which is now a W3C recommendation. The OWL recommendation actually consists of three languages of increasing expressive power, namely OWL Lite, OWL DL and OWL Full. OWL Lite and OWL DL are, basically very expressive description logics; they are almost3 equivalent to the SHIF(D+ ) and SHOIN (D+ ) DLs. OWL Full is clearly undecidable because it does not impose restrictions on the use of transitive properties. Although the above DL languages are very expressive, they feature expressive limitations regarding their ability to represent vague and imprecise knowledge. As obvious, in order to make applications that use DLs able to cope with vague and uncertain information we have to extend them with a theory capable of representing this kind of information. One such important theory is fuzzy set theory. In the current paper we extend the results obtained in [9] for fuzzy SI (f-SI) to the language SHIN , thus creating f-SHIN . SHIN extends SI [12] with number restrictions and role hierarchies [13]. Number restrictions give us the ability to restrict the number of objects that a certain object is related to by a specific relation. For example we can state that a car has exactly four wheels, writing Car ≡ Vehicle u ≥ 4hasWheel u ≤ 4hasWheel. But though this definition is correct, it faces many limitations, for example, in the context of image processing where several wheels of a car in an image might be hidden. Hence a detected object can belong to a concept like, ≥ 4hasWheel, only to a certain degree. On the other hand role hierarchies allow us to state sub-role/super-role relations, as for example the relation that holds between the hasChild and hasOffspring roles. Regarding expressive power, SHIN is more expressive than OWL-Lite, ignoring data-types. In the following we will introduce the syntax of f-SHIN and present a detailed procedure to reason with the extended language. 2 Syntax and Semantics of f-SHIN In this section we introduce the DL f-SHIN . As pointed out in the fuzzy DL literature [9,14], fuzzy extensions of DLs involve only the assertion of individuals to concepts and the semantics of the new language. Hence, as usual we have an alphabet of distinct concept names (C), role names (R) and individual names (I). f-SHIN -roles and f-SHIN -concepts are defined as follows: Definition 1. Let RN ∈ R be a role name, R an f-SHIN -role, C, D f-SHIN - concepts. Valid f-SHIN -roles are defined by the abstract syntax: R ::= RN | R− . The inverse relation of roles is symmetric, and to avoid considering roles such as R−− , we define a function Inv, which returns the inverse of a role, more precisely Inv(R) := RN − if R = RN and Inv(R) := RN if R = RN − . The set of f-SHIN concepts is the smallest set such that: 1. every concept name C ∈ CN is an f-SHIN -concept, 2. if C and D are f-SHIN -concepts, R is an f-SHIN -role, S a simple f- SHIN -role [15] and p ∈ N, then (C t D), (C u D), (¬C), (∀R.C), (∃R.C), (≥ pS) and (≤ pS) are also f-SHIN concepts. 3 They also provide annotation properties, which Description Logics don’t. Table 1. Semantics of f-SHIN -concepts >I (a) = 1 ⊥I (a) = 0 (¬C)I (a) = 1 − C I (a) (C t D)I (a) = max(C I (a), DI (a)) (C u D)I (a) = min(C I (a), DI (a)) (∀R.C)I (a) = inf b∈∆I {max(1 − RI (a, b), C I (b))} (∃R.C)I (a) = supb∈∆I {min(RI (a, b), C I (b))} (≥ pR)I (a) = supb1 ,...,bp ∈∆I minpi=1 RI (a, bi ) (≤ pR)I (a) = inf b1 ,...,bp+1 ∈∆I maxp+1 I i=1 {1 − R (a, bi )} (R− )I (b, a) = I R (a, b) A fuzzy T Box is a finite set of fuzzy concept axioms. Let A be a concept name, C a f-SHIN -concept. Fuzzy concept axioms of the form A v C are called fuzzy inclusion introductions; fuzzy concept axioms of the form A ≡ C are called fuzzy equivalence introductions. Note that how to deal with general fuzzy concept inclusions [12] still remains an open problem in fuzzy concept languages. A fuzzy RBox is a finite set of fuzzy role axioms. Fuzzy role axioms of the form Trans(RN ), where RN is a role name, are called fuzzy transitive role axioms; fuzzy role axioms of the form R v S are called fuzzy role inclusion axioms. We use the notation v * to denote the transitive-reflexive closure of v. A role R is called sub-role (super-role) of a role S if R v * S (S v * R). A fuzzy ABox is a finite set of fuzzy assertions. A fuzzy assertion [14] is of the form . ha : C./ni, h(a, b) : R./ni, where ./ stands for ≥, >, ≤ or < or a =6 b, for a, b ∈ I. Intuitively, a fuzzy assertion of the form ha : C ≥ ni means that the membership degree of a to the concept C is at least equal to n. We call assertions defined by ≥, > positive assertions, while those defined by ≤, < negative assertions [9]. A fuzzy knowledge base Σ is a triple hT , R, Ai, where T is a fuzzy T Box, R is a fuzzy RBox and A is a fuzzy ABox. A pair of assertions are called conjugated if they impose contradicting restrictions. For example, the pair of assertions hφ ≥ ni and hφ < mi, with n ≥ m contradict to each other. In the presence of role hierarchies one should also take into consideration possible sub- or super-roles when checking for such contradictions. For example the assertions h(a, b) : R ≥ 0.7i and h(a, b) : P ≤ 0.4i, with P v * R are conjugated. For a detailed description of the possible conjugated pairs the reader is referred to [14]. The semantics of fuzzy DLs are provided by a fuzzy interpretation [9, 14]. A fuzzy interpretation is a pair I = h∆I , ·I i where the domain ∆I is a non-empty set of objects and ·I is a fuzzy interpretation function, which maps an individ- ual name a to elements of aI ∈ ∆I and a concept name A (role name R) to a membership function AI : ∆I → [0, 1] (RI : ∆I × ∆I → [0, 1]). Moreover, fuzzy interpretations are extended to interpret arbitrary f-SHIN -concepts and roles. The complete set of semantics is depicted in Table 1, where inf stands for the infimum and sup for the supremum of a set. Note that apart from the fuzzy number restrictions, the interpretation of fuzzy concepts and concept con- structors is the usual one found in the DL literature [9, 14, 16], where the Gödel conjunction (t(a,b)=min(a,b)), the Gödel disjunction (u(a,b)=max(a,b)) and the Kleen-Dienes fuzzy implication (J (a,b)=max(1-a,b)) are used for perform- ing the fuzzy set theoretic operations. The semantics of fuzzy number restric- tions were first presented in [17]. We chose to follow these semantics because, as pointed out in [17], they are derived by the First-Order formulae of classical number restrictions [17]. In [9] the naming fKD -SI was used due to the usage of the Kleen-Dienes fuzzy implication. Since we also use the same implication here, from now on, we will refer to the extended language as fKD -SHIN . An fKD -SHIN -concept C is satisfiable iff there exists some fuzzy interpre- tation I for which there is some a ∈ ∆I such that C I (a) = n, and n ∈ (0, 1]. A fuzzy interpretation I satisfies a fuzzy T Box T iff ∀a ∈ ∆I , AI (a) ≤ C I (a) for each A v C in T and AI (a) = C I (a) for each A ≡ C in T . The seman- tics of fuzzy inclusion axioms is the usual one found in fuzzy set theory [3]. A fuzzy interpretation I satisfies a fuzzy RBox R iff ∀a, b, c ∈ ∆I , RI (a, c) ≥ supb∈∆I {min(RI (a, b), RI (b, c))} for each Trans (R) in R, and ∀ha, bi ∈ ∆I ×∆I , RI (a, b) ≤ S I (a, b) for each R v S. Note that the semantics of role inclusion ax- ioms R v S imply Inv(R) v Inv(S). A fuzzy relation R, defined over the domain X × X, is called sup-min transitive iff R(x, z) ≥ supy∈X min(R(x, y), R(y, z)). Given a fuzzy interpretation I, I satisfies ha : C ≥ ni if C I (aI ) ≥ n, I satis- . fies h(a, b) : R ≥ ni if RI (aI , bI ) ≥ n, while I satisfies a = 6 b if aI 6= bI . The satisfiability of fuzzy assertions with ≤, > and < is defined analogously. A fuzzy interpretation satisfies a fuzzy ABox A if it satisfies all fuzzy assertions in A. In this case, we say I is a model of A. If A has a model then we say that it is consistent. Finally, a fuzzy knowledge base Σ is satisfiable iff there exists a fuzzy interpretation I which satisfies all axioms in Σ. Moreover, Σ entails an assertion hφ./ni or a fuzzy concept inclusion axiom C v D, written Σ |= hφ./ni or Σ |= C v D, iff any model of Σ also satisfies the fuzzy assertion or fuzzy con- cept inclusion axiom, respectively. The problems of entailment and subsumption can be reduced to fuzzy knowledge base satisfiability as is shown in [14]. Since a fuzzy ABox A might contain many positive assertions for the same individual (pair of individuals), without forming a contradiction, it is in our interest to compute what is the best lower and upper truth-value bounds of a fuzzy assertion. In [14] the concept of greatest lower bound of a fuzzy assertion w.r.t. Σ was defined as glb(Σ, φ) = sup{n : Σ |= hφ ≥ ni}, and that of a least upper bound as, lub(Σ, φ) = inf{n : Σ |= hφ ≤ ni}, where φ represents a crisp assertion of the form a : C or (a, b) : R. Observe that sup ∅ = 0 and inf ∅ = 1. A procedure to solve the best truth-value bound was provided in [14]. Such a procedure can also be used in our framework. 3 A fuzzy tableau for fKD -SHIN ABoxes Most of the inference services of fuzzy DLs, can be reduced to the problem of con- sistency checking for ABoxes [14]. Consistency is usually checked with tableaux algorithms that try to construct a fuzzy tableau for a fuzzy ABox A [9], which is an abstraction of a model of A [13]. The tableau has a forest-like structure with nodes representing the individuals that appear in A, and edges between nodes, which represent the relations that hold between two individuals. Each node is labelled with a set of triples of the form hD, ./, ni, which denote the concept, the type of inequality and the membership degree that the individual of the node has been asserted to belong to D. We call such triples membership triples. For triples of a single node, the concepts of conjugated, positive and negative triples can be defined in the obvious way. Since the expansion rules decompose the initial concept, the concepts that appear in triples are sub-concepts of the initial concept. Sub-concepts of a concept D are denoted by sub(D). The set of all sub-concepts that appear within an ABox is denoted by sub(A). Since the De’Morgan laws are satisfied by the operations we use in the current paper [3] all concepts are assumed to be in their negation normal form (NNF) [18]. In the following we use the symbols B and C as a placeholder for the inequalities ≥, > and ≤, < and the symbol ./ as a placeholder for all types of inequations. Furthermore we use the symbols ./− , B− and C− to denote their reflections. For example the reflection of ≤ is ≥ and that of > is <. Definition 2. Let A be an fKD -SHIN ABox, RA the set of roles occurring in A together with their inverses, IA the set of individuals in A, X the set {≥, > , ≤, <} and R a fuzzy RBox. A fuzzy tableau T for A w.r.t. R is a quadruple (S, L, E, V) such that: – S is a non-empty set of individuals (nodes), – L : S → 2sub(A) × X × [0, 1] maps each element of S to membership triples, – E : RA → 2S×S × X × [0, 1] maps each role to membership triples, – V : IA → S maps individuals occurring in A to elements in S. For all s, t ∈ S, C, E ∈ sub(A), and R ∈ RA , T satisfies: 1. If h¬C, ./, ni ∈ L(s), then hC, ./− , 1 − ni ∈ L(s), 2. If hC u E, B, ni ∈ L(s), then hC, B, ni ∈ L(s) and hE, B, ni ∈ L(s), 3. If hC t E, C, ni ∈ L(s), then hC, C, ni ∈ L(s) and hE, C, ni ∈ L(s), 4. If hC t E, B, ni ∈ L(s), then hC, B, ni ∈ L(s) or hE, B, ni ∈ L(s), 5. If hC u E, C, ni ∈ L(s), then hC, C, ni ∈ L(s) or hE, C, ni ∈ L(s), 6. If h∀R.C, B, ni ∈ L(s) and hhs, ti, B0 , n1 i ∈ E(R) is conjugated with hhs, ti, B− , 1 − ni, then hC, B, ni ∈ L(t), 7. If h∃R.C, C, ni ∈ L(s) and hhs, ti, B, n1 i ∈ E(R) is conjugated with hhs, ti, C, ni, then hC, C, ni ∈ L(t), 8. If h∃R.C, B, ni ∈ L(s), then there exists t ∈ S such that hhs, ti, B, ni ∈ E(R) and hC, B, ni ∈ L(t), 9. If h∀R.C, C, ni ∈ L(s), then there exists t ∈ S such that hhs, ti, C− , 1 − ni ∈ E(R) and hC, C, ni ∈ L(t), 10. If h∃S.C, C, ni ∈ L(s), and hhs, ti, B, n1 i ∈ E(R) is conjugated with hhs, ti, C, ni, for some R v * S with Trans(R), then h∃R.C, C, ni ∈ L(t), 11. If h∀S.C, B, ni ∈ L(s) and hhs, ti, B0 , n1 i ∈ E(R) is conjugated with hhs, ti, B− , 1 − ni, for some R v * S with Trans(R), then h∀R.C, B, ni ∈ L(t), 12. hhs, ti, ./, ni ∈ E(R) iff hht, si, ./, ni ∈ E(Inv(R)), 13. If hhs, ti, B, ni ∈ E(R) and R v * S then, hhs, ti, B, ni ∈ E(S), 14. If h≥ pR, B, ni ∈ L(x), then |{t ∈ S | hhs, ti, B, ni ∈ E(R)}| ≥ p, 15. If h≤ pR, C, ni ∈ L(x), then |{t ∈ S | hhs, ti, C− , 1 − ni ∈ E(R)}| ≥ p + 1, 16. If h≥ pR, C, ni ∈ L(x), then |{t ∈ S | hhs, ti, B, ni i ∈ E(R)}| ≤ p − 1, conjugated with hhs, ti, C, ni, 17. If h≤ pR, B, ni ∈ L(x), then |{t ∈ S | hhs, ti, B0 , ni i ∈ E(R)}| ≤ p conjugated with hhs, ti, B− , 1 − ni, 18. There do not exist two conjugated triples in any label of any individual x ∈ S, 19. If ha : C./ni ∈ A, then hC, ./, ni ∈ L(V(a)), 20. If h(a, b) : R./ni ∈ A, then hhV(a), V(b)i, ./, ni ∈ E(R), . 6 b ∈ A, then V(a) 6= V(b) 21. If a = Properties 10 and 11 are a consequence of the fact that the supremum and infimum restrictions have to be preserved, when relations that have transitive sub-roles participate in negative existential and positive value restrictions. The membership degrees that the concepts are being propagated, in Properties 10 and 11, is the same as in the nodes that cause propagation. The proof of this property is quite technical and omitted here. Properties 14-17 are a direct consequence of the semantics of fuzzy number restrictions and the fact that from the De’ Morgan laws we can establish equivalences between negative and positive triples. Lemma 1. An fKD -SHIN -ABox A is consistent w.r.t. R iff there exists a fuzzy tableau for A w.r.t. R. 3.1 The Tableaux Algorithm In order to decide ABox consistency a procedure that constructs a fuzzy tableau for an fKD -SHIN ABox has to be determined. In the current section we will provide the technical details for constructing a correct tableaux algorithm. As pointed out in [13] algorithms that decide consistency of an ABox work on completion-forests rather than on completion-trees. This is because an ABox might contain several individuals with arbitrary roles connecting them. Such a forest is a collection of trees that correspond to the individuals in the ABox. Nodes in the completion-forest are labelled with a set of triples L(x) (node triples), which contain membership triples. More precisely we define L(x){hC, ./, ni}, where C ∈ sub(A) and n ∈ [0, 1]. Furthermore, edges hx, yi are labelled with a set L(hx, yi) (edge triples) defined as, L(hx, yi) = {hR, ./, ni}, where R ∈ RA . The algorithm expands the tree either by expanding the set L(x), of a node x with new triples, or by adding new leaf nodes. If nodes x and y are connected by an edge hx, yi, then y is called a successor of x and x is called a predecessor of y, ancestor is the transitive closure of predecessor. A node x is called an S − neighbour of a node x if for some R with Table 2. Tableaux expansion rules Rule Description (¬) if 1. h¬C, ./, ni ∈ L(x) 2. and hC, ./− , 1 − ni 6∈ L(x) then L(x) → L(x) ∪ {hC, ./− , 1 − ni} (uB ) if 1. hC1 u C2 , B, ni ∈ L(x), x is not indirectly blocked, and 2. {hC1 , B, ni, hC2 , B, ni} 6⊆ L(x) then L(x) → L(x) ∪ {hC1 , B, ni, hC2 , B, ni} (tC ) if 1. hC1 t C2 , C, ni ∈ L(x), x is not indirectly blocked, and 2. {hC1 , C, ni, hC2 , C, ni} 6⊆ L(x) then L(x) → L(x) ∪ {hC1 , C, ni, hC2 , C, ni} (tB ) if 1. hC1 t C2 , B, ni ∈ L(x), x is not indirectly blocked, and 2. {hC1 , B, ni, hC2 , B, ni} ∩ L(x) = ∅ then L(x) → L(x) ∪ {C} for some C ∈ {hC1 , B, ni, hC2 , B, ni} (uC ) if 1. hC1 u C2 , C, niL(x), x is not indirectly blocked, and 2. {hC1 , C, ni, hC2 , C, ni} ∩ L(x) = ∅ then L(x) → L(x) ∪ {C} for some C ∈ {hC1 , C, ni, hC2 , C, ni} (∃B ) if 1. h∃R.C, B, ni ∈ L(x), x is not blocked, 2. x has no R-neighbour y connected with a triple hP ∗ , B, ni, P v * R and hC, B, ni ∈ L(y) then create a new node y with L(hx, yi) = {hR, B, ni}, L(y) = {hC, B, ni}, (∀C ) if 1. h∀R.C, C, ni ∈ L(x), x is not blocked, 2. x has no R-neighbour y connected with a triple hP ∗ , C− , 1 − ni, P v * R and hC, C, ni ∈ L(y) then create a new node y with L(hx, yi) = {hR, C− , 1 − ni}, L(y) = {hC, C, ni}, (∀B ) if 1. h∀R.C, B, ni ∈ L(x), x is not indirectly blocked, and 2. x has an R-neighbour y with hC, B, ni 6∈ L(y) and 3. h∗, B− , 1 − ni is conjugated with the positive triple that connects x and y then L(y) → L(y) ∪ {hC, B, ni}, (∃C ) if 1. h∃R.C, C, ni ∈ L(x), x is not indirectly blocked and 2. x has an R-neighbour y with hC, C, ni 6∈ L(y) and 3. h∗, C, ni is conjugated with the positive triple that connects x and y then L(y) → L(y) ∪ {hC, C, ni}, (∀+ ) if 1. h∀R.C, B, ni ∈ L(x), x is not indirectly blocked, and 2. there is some P , with Trans(P ), and P v * R, x has a P -neighbour y with, h∀P.C, B, ni 6∈ L(y), and 3. h∗, B− , 1 − ni is conjugated with the positive triple that connects x and y then L(y) → L(y) ∪ {h∀P.C, B, ni}, (∃+ ) if 1. h∃R.C, C, ni ∈ L(x), x is not indirectly blocked and 2. there is some P , with Trans(P ), and P v* R, x has a P -neighbour y with, h∃P.C, C, ni 6∈ L(y), and 3. h∗, C, ni is conjugated with the positive triple that connects x and y then L(y) → L(y) ∪ {h∃P.C, C, ni}, (≥B ) if 1. h≥ pR, B, ni ∈ L(x), x is not blocked, 2. there are no p R-neighbours y1 , ..., yp connected to x with a triple hP ∗ , B, ni, P v * R, 3. and yi 6= yj for 1 ≤ i < j ≤ p then create p new nodes y1 , ..., yp , with L(hx, yi i) = {hR, B, ni} and yi 6= yj for 1 ≤ i < j ≤ p (≤C ) if 1. h≤ pR, C, ni ∈ L(x), x is not blocked, then apply (≥B )-rule for the triple h≥ (p + 1)R, C− , 1 − ni (≤B ) if 1. h≤ pR, B, ni ∈ L(x), x is not indirectly blocked, 2. there are p + 1 R-neighbours y1 , ..., yp+1 connected to x with a triple hP ∗ , B0 , ni i, P v * R, . 3. which is conjugated with hP ∗ , B− , 1 − ni, and there are two of them y, z, with no y = 6 z and 4. y is neither a root node nor an ancestor of z then 1. L(z) → L(z) ∪ L(y) and 2. if z is an ancestor of x then L(hz, xi) −→ L(hz, xi) ∪ Inv(L(hx, yi)) else L(hx, zi) −→ L(hx, zi) ∪ L(hx, yi) 3. L(hx, yi) −→ ∅ . . 4. Set u =6 z for all u with u = 6 y (≥C ) if 1. h≥ pR, C, ni ∈ L(x), x is not indirectly blocked, then apply (≤B )-rule for the triple h≤ (p − 1)R, C− , 1 − ni (≤rB ) if 1. h≤ pR, B, ni ∈ L(x), 2. there are p + 1 R-neighbours y1 , ..., yp+1 connected to x with a triple hP ∗ , B0 , ni i, P v * R, . 3. conjugated with hP ∗ , B− , 1 − ni, and there are two of them y, z, both root nodes, with no y = 6 z then 1. L(z) → L(z) ∪ L(y) and 2. For all edges hy, wi: i. if the edge hz, wi does not exist, create it with L(hz, wi) = ∅ ii. L(hz, wi) −→ L(hz, wi) ∪ L(hy, wi) 3. For all edges hw, yi: i. if the edge hw, zi does not exist, create it with L(hw, zi) = ∅ ii. L(hw, zi) −→ L(hw, zi) ∪ L(hw, yi) 4. Set L(y) = ∅ and remove all edges to/from y . . . 5. Set u =6 z for all u with u = 6 y and set y = z (≥rC ) if 1. h≥ pR, C, ni ∈ L(x), then apply (≤rB )-rule for the triple h≤ (p − 1)R, C− , 1 − ni Rv * S either y is a successor of x and L(hx, yi) = hR, ./, ni or y is a predecessor of x and L(hy, xi) = hInv(R), ./, ni. We then say that the edge triple connects x and y to a degree of n. A node x is blocked iff it is not a root node and it is either directly or indirectly blocked. A node x is directly blocked iff none of its ancestors is blocked, and it has ancestors x0 , y and y 0 such that: (i) y is not a root node, (ii) x is a successor of x0 and y a successor of y 0 , (iii) L(x) = L(y) and L(x0 ) = L(y 0 ) and, (iv) L(hx0 , xi) = L(hy 0 , yi). In this case we say that y blocks x. A node y is indirectly blocked iff none of its ancestors is blocked, or it is a successor of a node x and L(hx, yi) = ∅. The algorithm initializes a forest FA to contain a root node xi0 , for each individual ai ∈ IA occurring in the ABox A and additionally {hCi , ./, ni}∪L(xi0 ), for each assertion of the form hai : Ci ./ni in A, and an edge hxi0 , xj0 i if A contains an assertion h(ai , aj ) : Ri ./ni, with {hRi , ./, ni}∪L(hxi0 , xj0 i) for each assertion of . . the form h(ai , aj ) : Ri ./ni in A. At last we initialize the relation = 6 xj0 if 6 as xi0 = . . ai 6= aj ∈ A and the relation = to be empty. FA is then expanded by repeatedly applying the rules from Table 2. We use the notation R∗ to denote either the role R or the role returned by Inv(R), and the notation h∗, ./, ni, to denote any role that participates in such a triple. For a node x, L(x) is said to contain a clash if it contains one of the following: (a) two conjugated pairs of triples, (b) one of the triples h⊥, ≥, ni, h>, ≤, ni, with n > 0, n < 1, h⊥, >, ni, h>, <, ni hC, <, 0i or hC, >, 1i, (c) some triple h≤ pR, B, ni ∈ L(x) and x has p + 1 R-neighbours y0 , ..., yp , connected to x with a triple hP ∗ , B0 , ni i, P v ∗ − * R, which is conjugated with hP , B , 1 − ni, and yi 6= yj , for all 0 ≤ i < j ≤ p, or (d) some triple h≥ pR, C, ni ∈ L(x) and x has p R-neighbours y0 , ..., yp−1 , connected to x with a triple hP ∗ , B, ni i, P v * R, which is conjugated with hP ∗ , C, ni, and yi 6= yj , for all 0 ≤ i < j ≤ p. A completion- forest is clash-free if none of its nodes contains a clash, and it is complete if none of the expansion rules is applicable. Lemma 2. Let A be an fKD -SHIN ABox and R a fuzzy RBox. Then 1. when started for A and R the tableaux algorithm terminates 2. A has a fuzzy tableau w.r.t. R if and only if the expansion rules can be applied to A and R such that they yield a complete and clash-free completion forest. 4 Related Work Much work has been carried out towards combining fuzzy logic and description logics during the last decade. The initial idea was presented by Yen in [19], where a structural subsumption algorithm was provided in order to perform reasoning. The DL language used was a sub-language of the basic DL ALC. Reasoning in fuzzy ALC was latter presented in [14], as well as in other approaches [20, 21], where an additional concept constructor, called membership manipulator was included in the extended language. In all these approaches tableaux decision procedures were presented for performing reasoning services. The operations used to interpret the concept constructors in all these approaches were the same ones as in our context. Approaches towards more expressive DLs, are presented in [16], where the DL is ALCQ, and in [17], where the language is SHOIN (D+ ). The former one also included fuzzy quantifiers, which is a new novel idea for fuzzy DLs. Unfortunately, in both these approaches only the semantics of the extended languages were provided and no reasoning algorithms. As far as we know the most expressive fuzzy DL presented till now, which also covers reasoning, is fKD -SI, appeared in [9]. The present work provides an extension of the latter one to an even more expressive DL, namely SHIN . 5 Conclusions The importance and role that uncertainty, like vagueness (fuzziness) and im- precision, plays in the Semantic web context, as well as to many applications that use DLs to capture, represent and perform reasoning with domain knowl- edge has been stressed many times in the literature [4–8]. To this extent we have presented an extension of the very expressive description logic SHIN with fuzzy set theory. Description logics are very powerful and expressive logical for- malisms, which are used by ontology creation languages in the Semantic Web context. Moreover, fuzzy set theory is one very important theory for capturing and dealing with vagueness. Additionally, we have presented a detailed reasoning algorithm for deciding fuzzy ABox consistency. In order to achieve this goal we have provided an investigation of the properties of fuzzy cardinalities, in order to provide sound rules for such types of concept constructors. As far as future directions are concerned, these will include the extension of the SHOIN (G) de- scription with fuzzy set theory. SHOIN (G) extends SHIN with nominals [22] and datatype groups [23]. Acknowledgements. This work is supported by the FP6 Network of Excellence EU project Knowledge Web (IST-2004-507482). References 1. Kim, W., Ko, J., Chung, M.: Uncertain robot environment modelling using fuzzy numbers. Fuzzy Sets and Systems 61 (1994) 53–62 2. Krishnapuram, R., Keller, J.: Fuzzy set theoretic approach to computer vision: An overview. In: IEEE International Conference on Fuzzy Systems. (1992) 135–142 3. Klir, G.J., Yuan, B.: Fuzzy Sets and Fuzzy Logic: Theory and Applications. Prentice-Hall (1995) 4. Stamou, G., Tzouvaras, V., Pan, J., Horrocks, I.: A fuzzy extension of swrl, W3C Workshop on Rule Languages for Interoperability (2005) 5. Matheus, C.: Using ontology-based rules for situation awareness and information fusion, W3C Work. on Rule Languages for Interoperability (2005) 6. Kifer, M.: Requirements for an expressive rule language on the semantic web, W3C Workshop on Rule Languages for Interoperability (2005) 7. Zhang, L., Yu, Y., Zhou, J., Lin, C., Yang, Y.: An enhanced model for searching in semantic portals. In: Int. WWW Conference Committee. (2005) 8. Bechhofer, S., Goble, C.: Description Logics and Multimedia - Applying Lessons Learnt from the GALEN Project. In: KRIMS 96 Workshop on Knowledge Repre- sentation for Interactive Multimedia Systems, ECAI 96, Budapest (1996) 9. Stoilos, G., Stamou, G., Tzouvaras, V., Pan, J., Horrocks, I.: A fuzzy description logic for multimedia knowledge representation, Proc. of the International Workshop on Multimedia and the Semantic Web (2005) 10. Lassila, O., R.Swick, R.: Resource Description Framework (RDF) Model and Syn- tax Specification – W3C Recommendation 22 February 1999. Technical report, World Wide Web Consortium (1999) 11. Bechhofer, S., van Harmelen, F., Hendler, J., Horrocks, I., McGuinness, D.L., Patel- Schneider, P.F., eds., L.A.S.: OWL Web Ontology Language Reference (2004) 12. Horrocks, I., Sattler, U.: A description logic with transitive and inverse roles and role hierarchies. Journal of Logic and Computation 9 (1999) 385–410 13. Horrocks, I., Sattler, U., Tobies, S.: Reasoning with Individuals for the Descrip- tion Logic SHIQ. In MacAllester, D., ed.: CADE-2000. Number 1831 in LNAI, Springer-Verlag (2000) 482–496 14. Straccia, U.: Reasoning within fuzzy description logics. Journal of Artificial Intel- ligence and Research 14 (2001) 137–166 15. Horrocks, I., Sattler, U., Tobies, S.: Practical reasoning for expressive description logics. In: Proceedings of the 6th International Conference on Logic for Program- ming and Automated Reasoning (LPAR’99). Number 1705 in LNAI, Springer- Verlag (1999) 161–180 16. Sánchez, D., Tettamanzi, G.: Generalizing quantification in fuzzy description logic. In: Proceedings 8th Fuzzy Days in Dortmund. (2004) 17. Straccia, U.: Towards a fuzzy description logic for the semantic web. In: Proceed- ings of the 2nd European Semantic Web Conference. (2005) 18. Hollunder, B., Nutt, W., Schmidt-Schaus, M.: Subsumption algorithms for concept description languages. In: European Conference on Artificial Intelligence. (1990) 348–353 19. Yen, J.: Generalising term subsumption languages to fuzzy logic. In: In Proc of the 12th Int. Joint Conf on Artificial Intelligence (IJCAI-91). (1991) 20. Tresp, C., Molitor, R.: A description logic for vague knowledge. In: In proc of the 13th European Conf. on Artificial Intelligence (ECAI-98). (1998) 21. Hölldobler, S., Khang, T.D., Störr, H.P.: A fuzzy description logic with hedges as concept modifiers. In: Proceedings InTech/VJFuzzy’2002. (2002) 25–34 22. Horrocks, I., Sattler, U.: Ontology reasoning in the SHOQ(D) description logic. In: Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence. (2001) 23. Pan, J.Z.: Web Ontology Reasoning in the SHOQ(Dn) Description Logic. In: Carlos Areces and Maartin de Rijke, editors,Proceedings of the Methods for Modalities 2 (M4M-2). (2001) ILLC, University of Amsterdam.