Reasoning with Fuzzy Ontologies Yanhui Li1 and Baowen Xu1 and Jianjiang Lu2 and Dazhou Kang1 Abstract. By the development of Semantic Web, increasing de- a novel semantical discretization technique to enable translation of mands for vague information representation have triggered a mass of membership degree values from continuous ones into discrete theoretical and applied researches of fuzzy ontologies, whose main ones. In this paper, we will extend this discretization technique into logical infrastructures are fuzzy description logics. However, cur- FSHIN ; and based on it, we will design a discrete tableau algo- rent tableau algorithms can not supply complete reasoning support rithm for reasoning with general TBox in FSHIN . Since nominals within fuzzy ontology: reasoning with general TBox is still a dif- should not be fuzzyfied, our discrete tableau algorithms for SHIN , ficult problem in fuzzy description logics. The main trouble is that together with reasoning technique to deal with nominals in crisp fuzzy description logics adopt fuzzy models with continuous but not DLs [3], can be extended to provide a tableau algorithm for general discrete membership degrees. In this paper, we propose a novel se- TBox in FSHOIN , that will achieve complete reasoning within mantical discretization to discretize membership degrees in fuzzy fuzzy ontologies. description logic FSHIN . Based on this discretization, we design discrete tableau algorithms to achieve reasoning with general TBox. 2 Logical Infrastructure of Fuzzy Ontologies 1 Introduction Let NC be a set of concept names (A), NR a set of role names (R) with a subset NR + of transitive role names and NI a set of individual The Semantic Web stands for the idea of a future Web, in which in- names (a). FSHIN roles are either role names R ∈ NR or their in- formation is given well-defined meaning, better enabling intelligent verse roles R− . To avoid R−− , we use Inv(R) to denote the inverse Web information processing [1]. In the Semantic Web, ontology is a role of R. FSHIN concepts C, D are inductively defined with the crucial knowledge representation model to express a shared under- application of FSHIN concept constructors in the following syn- standing of information between users and machines. Along with the tax rules: evolvement from current Web to the Semantic Web, the management C, D :: >|⊥|A|¬C|C u D|C t D|∃R.C|∀R.C| ≥ pR| ≤ pR of ill-structured, ill-defined or imprecise information plays a more and more important role in applications of the Semantic Web [13]. Since concepts and roles in FSHIN are considered as fuzzy This trend calls for ontologies with capability to deal with uncer- sets, the semantics of concepts and roles are defined in terms of tainty. However, classical DLs, as the logical foundation of ontolo- fuzzy interpretations I = h∆I , ·I i, where ∆I is a nonempty do- gies, are two-value-based languages. The need for expressing uncer- main, and ·I is an interpretation function mapping individuals a tainty in the Semantic Web has triggered extending classical DLs into aI ∈ ∆I ; concept (role) names A (R) into membership func- with fuzzy capabilities, yielding Fuzzy DLs (FDLs for short). Strac- tions AI (RI ) : ∆I (∆I × ∆I ) → [0, 1]. And for any transitive cia proposed a representative fuzzy extension FALC of DL ALC, role name R ∈ NR + , I satisfies ∀d, d0 ∈ ∆I , RI (d, d0 ) ≥ in which fuzzy semantics is introduced to interpret concepts and supx∈∆I {min(RI (d, x), RI (x, d0 ))}. Furthermore, ·I satisfies the roles as fuzzy sets [11]. Following researchers extended FALC with following conditions for complex concepts and roles built by con- more complex constructions: FALCQ [6] with qualified number re- cept and role constructors: for any d, d0 ∈ ∆I striction , FSI [7] with transitive and inverse role, and FSHIN >I (d) = 1 [8], a extension of FSI with role hierarchy and unqualified num- ⊥I (d) = 0 ber restriction. Stoilos et al introduced Straccia’s fuzzy framework (¬C)I (d) = 1 − C I (d) into OWL, hence getting a fuzzy ontology language FSHOIN , by (C u D)I (d) = min{C I (d), DI (d)} which fuzzy ontologies are coded as FDL knowledge bases [9]. (C t D)I (d) = max{C I (d), DI (d)} Though the fuzzy DLs have done a lot, to our best knowledge, (∃R.C)I (d) = sup d0 ∈∆I {min(RI (d, d0 ), C I (d0 ))} reasoning with general TBox in FDLs is still a difficult problem [8]. (∀R.C)I (d) = inf d0 ∈∆I {max(1 − RI (d, d0 ), C I (d0 ))} Current tableau algorithms in FDLs are applied to achieve reasoning (≥ pR)I (d) = sup d1 ,d2 ,...,dp ∈∆I {minp1 (RI (d, di )} without TBox or with acyclic TBox [7, 8, 11], that limits reasoning support within fuzzy ontologies. The main trouble in reasoning with (≤ pR)I (d) = inf d1 ,d2 ,...,dp+1 ∈∆I {maxp+1 1 (1 − RI (d, di )} general TBox is that fuzzy interpretations I map concepts C into (R− )I (d, d0 ) = I 0 R (d , d) membership degree functions C I () w.r.t domain ∆I : ∆I → [0, 1], A FSHIN knowledge base (KB) K is a triple K=hT , R, Ai, where the value domain [0,1] is continuous. In [4], we represented where T , R and A are FSHIN TBox, RBox and ABox. The syn- 1 Department of Computer Science and Engineering, Southeast University, tax and semantics of axioms in them are given in table 1. An inter- Nanjing 210096, P. R. China. email: yanhuili,bwxu,swws@seu.edu.cn pretation I satisfies an axiom if it satisfies corresponding semantics 2 Institute of Command Automation, PLA University of Science and Tech- restriction given in table 1. I satisfies (is a fuzzy model of) a KB K, nology, Nanjing 210007, China. email:jjlu@seu.edu.cn iff I satisfies any axiom in T , R and A. K is satisfiable iff it has a fuzzy model. In this paper, we will propose a discrete tableau algo- 4 Discrete Tableau Algorithms for FSHIN rithm to decide satisfiability of FSHIN KBs, which is based on the ”semantical discretization” discussed in the following section. For a KB K, let RK and OK be the sets of roles and individuals appearing in K, and sub(K) the set of sub-concepts of all concepts Table 1. Syntax and semantics of FSHIN axioms in K. We also introduce Trans(R) as a boolean value to tell whether Syntax Semantics R is transitive, ¤ and ¢ as two placeholders for the inequalities TBox T CvD ∀d ∈ ∆I , C I (d) ≤ DI (d) ≥, > and ≤, <, and the symbols ./− , ¤− and ¢− to denote their RBox R RvP ∀d, d0 ∈ ∆I , RI (d, d0 ) ≤ P I (d, d0 ) reflections. A discrete tableau T for K within a degree set S is a a : C ./ n C I (aI ) ./ n quadruple: hO, L, E, Vi, where ABox A ha, bi : R ./ RI (aI , bI ) ./ n • O: a nonempty set of nodes; a 6= b aI 6= bI • L:O → 2M , M = sub(K) × {≥, >, ≤, <} × S; C and D (R and P ) are concepts (roles); a, b ∈ NI ; ./∈ {≥, >, ≤, <}; n ∈ [0,1]. • E: RK → 2Q , Q = {O × O} × {≥, >, ≤, <} × S; • V:OK → O, maps any individual into a corresponding node in O. 3 Semantical Discretization in FSHIN From the definition of T, each node d is labelled with a set L(d) For any fuzzy model of FSHIN KBs, we discretize it into a special of degree triples: hC, ./, ni, which denotes the membership degree model, in which any value of membership degree functions belongs of d being an instance of C ./ n. In a discrete tableau T, for any to a given discrete degree set S. And we call it a discrete model d, d0 ∈ O, a, b ∈ OK , C, D ∈ sub(K) and R ∈ RK , the following within S. Let us now proceed formally in the creation of S. Let Nd be conditions, a extension of tableau conditions in dealing without the set of degrees appearing in ABox Nd = {n|α ./ n ∈ A}. From TBox [8] by adding KB conditions and NNF conditions, must hold: Nd , we define the degree closure Nd∗ = {0, 0.5, 1}∪Nd ∪{n|1−n ∈ Nd } and order degrees in ascending order: Nd∗ = {n0 , n1 , . . . , ns }, KB condition: If C v D ∈ T , then there must be some n ∈ S where for any 0 ≤ i ≤ s, ni < ni+1 . For any two back-to-back with hC, ≤, ni and hD, ≥, ni in L(d). elements ni , ni+1 ∈ Nd∗ , we insert their median mi+1 = (ni + NNF condition: If hC, ./, ni ∈ L(d), then hnnf(¬C), ./− , 1 − ni+1 )/2 to get S = {n0 , m1 , n1 , . . . , ns−1 , ms , ns }. We call S a ni ∈ L(d). Here we use nnf(¬C) to denote the equivalent form discrete degree set w.r.t K. Obviously for any 1 ≤ i ≤ s, mi + of ¬C in Negation Normal Form (NNF). ms+1−i = 1 and ni−1 < mi < ni . Theorem 2 For any K =< T , R, A > and any discrete degree set Theorem 1 For any K=hT , R, Ai and any discrete degree set S S w.r.t K, K has a discrete model within S iff it has a discrete tableau w.r.t K, iff K has a fuzzy model, it has a discrete model within S. T within S. Proof. Let I = h∆I , ·I i be a fuzzy model of K and the degree set S = {n0 , m1 , n1 , . . . , ns−1 , ms , ns }. Consider a translation From theorem 1 and 2, an algorithm that constructs a discrete function ϕ() : [0, 1] → S: tableau of K within S can be considered as a decision procedure ½ for the satisfiability of K. The discrete tableau algorithm works ni if x = ni on a completion forest FK with a set S 6= to denote ”6=” rela- ϕ(x) = mi if ni−1 < x < ni tion between nodes. The algorithm expands the forest FK either Based on ϕ(), we will construct a discrete model Ic = h∆Ic , ·Ic i by extending L(x) for the current node x or by adding new leaf within S from I = h∆I , ·I i: node y with expansion rules in table 2. A node y is called an R- • The interpretation domain ∆Ic is defined as: ∆Ic = ∆I ; successor of another node x and x is called a R-predecessor of • The interpretation function ·Ic is defined as: for any individual y, if hR, ./, ni ∈ L(hx, yi). Ancestor is the transitive closure of name a, aIc = aI ; for any concept name A and any role name R: predecessor. And for any two connected nodes x and y, we define AIc () = ϕ(AI ()) and RIc () = ϕ(RI ()). DR (x, y)={h./, ni|P v∗ R, hP, ./, ni ∈ L(hx, yi) or hInv(P ), ./ , ni ∈ L(hy, xi)}. If DR (x, y) 6= ∅, y is called a R-neighbor of x. 1. For any concept C and role R and any d, d0 ∈ ∆Ic , we show, on The tableau algorithm initializes FK to contain a root node xa for induction on the structure of C and R, that C Ic (d) = ϕ(C I (d)) each individual a ∈ OK and labels xa with L(xa )= {hC, ./, ni|a : and RIc (d, d0 ) = ϕ(RI (d, d0 )): C ./ n ∈ A}; for any pair hxa , xb i, Lhxa , xb i={hR, ./, ni|ha, bi : • ≥ pR: (≥ pR)I (d) = sup d1 ,d2 ,...,dp ∈∆I {minp1 (RI (d, di ))}. R ./ n ∈ A}; and for any a 6= b ∈ A, hxa , xb i ∈ S 6= . As in- verse role and number restriction are allowed in SHIN , we make Let f (d0 ) = RI (d, d0 ), and f ∗ (d0 ) = ϕ(f (d)). Assume use of pairwise blocking technique [2] to ensure the termination and there are p elements d∗1 , d∗2 , . . . , d∗p with the maximum value correctness of our tableau algorithm: a node x is directly blocked by of f (): for any other d0 in ∆I , f (d∗i ) ≥ f (d0 ). Obvi- its ancestor y iff (1) x is not a root node; (2) x and y have prede- ously from the property of ϕ( ), for any other d0 in ∆Ic , cessors x0 and y 0 , such that L(x) = L(y) and L(x0 ) = L(y 0 ) and f ∗ (d∗i ) = ϕ(f (d∗i )) ≥ ϕ(f (d)) = f ∗ (d0 ). Then we get L(hy 0 , yi) = L(hx0 , xi). A node x is indirectly blocked if its pre- (≥ pR)Ic (d) = sup d1 ,d2 ,...,dp ∈∆Ic {minp1 (f ∗ (di ))} decessor is blocked. A node x is blocked iff it is either directly or = minp1 (f ∗ (d∗i )) = ϕ(minp1 (f (d∗i ))) indirectly blocked. A completion forest FK is said to contain a clash, = ϕ(sup d1 ,d2 ,...,dp ∈∆I {minp1 (RI (d, di ))}) if for a node x in FK , (1) L(x) contains two conjugated triples, or a mistake triple [4]; or (2) h≥ pR, ¢, ni or h≤ (p−1)R, ¢− , 1−ni ∈ = ϕ((≥ pR)I (d)) L(x), and there are p nodes y1 , y2 , . . . yp in FK with hR, ¤i , mi i, 2. We show Ic is a fuzzy model of K. h¤i , mi i is conjugated with h¢, ni and for any two nodes yi and yj , • C v D ∈ T : Obviously, ∀d ∈ ∆I = ∆Ic , C I (d) ≤ DI (d). hyi , yj i ∈ S 6= . A completion forest FK is clash-free if it does not And from 1, for any concept C, C Ic (d) = ϕ(C I (d)). There- contain a clash, and it is complete if none of the expansion rules are fore, C Ic (d) = ϕ(C I (d)) ≤ ϕ(DI (d)) = DIc (d); applicable. Table 2. Expansion rules of discrete Tableau Rule name Description KB rule: if C v D ∈ T and there is no n with hC, ≤, ni and hD, ≥, ni in L(x); then L(x) → L(x) ∪ {hC, ≤, ni hD, ≥, ni} for some n ∈ S. The following rules are applied to nodes x which is not indirectly blocked. ¬./ rule: if hC, ./, ni ∈ L(x) and hnnf(¬C), ./− , ni ∈ / L(x); then L(x) → L(x) ∪ {hnnf(¬C), ./− , ni}. u¤ rule: if hC u D, ¤, ni ∈ L(x), and hC, ¤, ni or hD, ¤, ni ∈ / L(x); then L(x) → L(x) ∪ {hC, ¤, ni, hD, ¤, ni}. t¤ rule: if hC t D, ¤, ni ∈ L(x), and hC, ¤, ni, hD, ¤, ni ∈ / L(x) then L(x) → L(x) ∪ {T }, for some T ∈ {hC, ¤, ni, hD, ¤, ni} ∀¤ rule: if h∀R.C, ¤, ni ∈ L(x), there is a R-neighbor y of x with h¤0 , mi ∈ DR (x, y), which is conjugated with h¤− , 1 − ni and hC, ¤, ni ∈ / L(y); then L(y) → L(y) ∪ {hC, ¤, ni}. ∀+¤ rule: if h∀P.C, ¤, ni ∈ L(x), there is a R-neighbor y of x with R v∗ P , Trans(R)=True and h¤0 , mi ∈ DR (x, y), h¤0 , mi is conjugated with h¤− , 1 − ni and h∀R.C, ¤, ni ∈ / L(y); L(y) → L(y) ∪ {h∀R.C, ¤, ni}. ≤ p¤ rule: if h≤ pR, ¤, n ∈ L(x); there is p + 1 R-successors y1 , y2 , . . . , yp+1 of x with hR, ¤i , mi i ∈ L(hx, yi i) and h¤i , mi i is conjugated with h¢− , 1 − ni for any 1 ≤ i ≤ p + 1; and hyi , yj i ∈/ S 6= for some 1 ≤ i < j ≤ p + 1 then merge two nodes yi and yj into one : L(yi ) → L(yi ) ∪ L(yj ); ∀x, L(yi , x) → L(yi , x) ∪ L(yj , x), hyj , xi ∈ S 6= , add hyi , xi in S 6= The following rules are applied to nodes x which is not blocked. ∃¤ rule: if h∃R.C, ¤, ni ∈ L(x); there is not a R-neighbor y of x with h¤, ni ∈ DR (x, y) and hC, ¤, ni ∈ L(y). then add a new node z with hR, ¤, ni ∈ L(hx, zi) and hC, ¤, ni ∈ L(z). ≥ pR¤ rule: if h≥ pR, ¤, ni ∈ L(x), there are not p R-neighbors y1 , y2 , . . . , yp of x with hR, ¤, ni ∈ L(hx, yi i) and for any i 6= j, hyi , yj i ∈ S 6= . then add p new nodes z1 , z2 , . . . , zp with hR, ¤, ni ∈ L(hx, zi i) and for any two node zi and zj , add hzi , zj i in S 6= . Theorem 3 For any K =< T , R, A > and any discrete degree set TBox in FSHIN KBs. Our work can be considered as a logical S w.r.t K, K has a discrete tableau within S iff the tableau algorithm foundation to support reasoning with fuzzy ontologies. can construct a complete and clash-free completion forest. REFERENCES 5 Related Work [1] T. Berners-Lee, J. Hendler, and O. Lassila, ‘The semantic web’, Scien- tific American, 284(5), 34–43, (2001). In FDLs area, we have introduced a lot of work in introduction, all [2] I. Horrocks and U. Sattler, ‘A description logic with transitive and in- that work are based on Straccia’ fuzzification framework. Here we verse roles and role hierarchies’, Journal of Logic and Computation, 9, get into reasoning issue for fuzzy DLs. The first reasoning algo- 385–410, (1999). rithm was represented in [10], and the soundness and completeness [3] I. Horrocks and U. Sattler, ‘A tableaux decision procedure for shoiq’, in Proceedings of 19th Int. Joint Conf. on Artificial Intelligence, (2005). of it were proved in [11]. This algorithm is designed to reasoning [4] Y.H. Li, B.W. Xu, J.J. Lu, and D.Z. Kang, ‘Discrete tableau Algorithms with FALC acyclic TBox form. More in detail, it first adopted KB for fshi’, in Proceedings of 2006 International Workshop on Descrip- expansion [5] to eliminate acyclic TBox, then achieved reasoning tion Logics - DL2006, The Lake District of the UK, (2006). without TBox. However, such expansion technique is not available [5] B. Nebel, ‘Computational complexity of terminological reasoning in for general TBox in FDLs. The following extension of FALC in- back’, Artificial Intelligence, 34, 371–383, (1988). [6] D. Sanchez and G. Tettamanzi, ‘Generalizing quantification in fuzzy herited this idea to design reasoning algorithm, so most of these ex- description logic’, in Proceedings of the 8th Fuzzy Days, (2004). tension are limited to dealing with empty or acyclic TBox. In gen- [7] G. Stoilos, G. Stamou, V. Tzouvaras, J.Z. Pan, and I. Horrock, ‘A Fuzzy eral TBox cases, a noteworthy reasoning method is PTIME bounded Description Logic for Multimedia Knowledge Representation’, in Proc. translations from FALCH KBs into ALCH ones and reusing ex- of the International Workshop on Multimedia and the Semantic Web, (2005). isting classical algorithm to achieve reasoning in fuzzy DLs [12]. [8] G. Stoilos, G. Stamou, V. Tzouvaras, J.Z. Pan, and I. Horrocks, ‘The This PTIME bounded translation can be considered as a result of re- fuzzy description logic shin’, in Proceedings of International Workshop searches on relationship between DLs and fuzzy DLs. It can not deal of OWL: Experiences and Directions, Galway, (2005). with ha, bi : R ¢ n in A, as this assertion will be translated into role [9] G. Stoilos, G. Stamou, V. Tzouvaras, J.Z. Pan, and I. Horrocks, ‘Fuzzy negation (that is not allowed in ALC). owl: Uncertainty and the semantic web’, in Proceedings of Interna- tional Workshop of OWL: Experiences and Directions, Galway, (2005). [10] U. Straccia, ‘A fuzzy description logic’, in Proceedings of AAAI-98, 15th National Conference on Artificial Intelligence, pp. 594–599, Madi- 6 Conclusion son, Wisconsin, (1998). [11] U. Straccia, ‘Reasoning within fuzzy description logics’, Journal of Ar- In this paper, we point out a novel semantical discretization to dis- tificial Intelligence Researc, 14, 137–166, (2001). cretize membership degree values in fuzzy models of FSHIN KBs, [12] U. Straccia, ‘Transforming fuzzy description logics into classical de- hence yielding ”discrete models”. Based on this discretization tech- scription logics’, in Proceedings of the 9th European Conference on nique, we design a discrete tableau algorithm to construct discrete Logics in Artificial Intelligence, pp. 385–399, Lisbon, (2004). [13] D.H. Widyantoro and J. Yen, ‘Using fuzzy ontology for query refine- tableaus, which are abstraction of discrete models. From the equiv- ment in a personalized abstract search engine’, in Proceedings of Joint alence of existence between fuzzy models and discrete models, our 9th IFSA World Congress and 20th NAFIPS International Conference, algorithm is a decision procedure to achieve reasoning with general Vancouver, Canada, (2001).