Minimizing interpretations in fuzzy description logics under the Gödel semantics by using fuzzy bisimulations

1 Introduction

Minimizing structures like automata, transition systems and logic interpretations is an important topic, which has been studied for a long time. Such a minimization allows to save memory and speed up computations that use the structure. It is expected that the resulting structure is equivalent to the original w.r.t. some important aspects. Minimization is usually done as follows: after computing the largest equivalence relation between elements of the domain w.r.t. the considered aspects, elements of each equivalence class are merged. One of the issues is to specify the merging, i.e., to specify the contents of the new structure. The resulting structure is usually called the quotient of the original w.r.t. that equivalence relation. Another issue is to guarantee that it is minimum and equivalent to the original w.r.t. the considered aspects.

Two states in an automaton are equivalent if they are bisimilar to each other. The bisimilarity relation is the largest auto-bisimulation of the automaton. Hopcroft [8] gave an efficient algorithm for computing the partition of such an equivalence relation for a given deterministic finite automaton. For minimizing nondeterministic finite automata, the Paige-Tarjan algorithm [11] for computing the partition, originally formulated for graphs, can be used instead.

Fuzzy bisimulations for fuzzy automata were introduced by Ćirić et al. [2]. They are just called bisimulations in [2]. Such a bisimulation is a fuzzy relation between the state sets of two given fuzzy automata. The authors defined four kinds of fuzzy bisimulation: forward, backward, forward-backward and backward-forward. The first one is most related to crisp bisimulations between traditional automata. Fuzzy backward bisimulations can be treated as fuzzy forward bisimulations between reversed fuzzy automata. The other kinds are mixtures of fuzzy forward simulation and fuzzy backward simulation. The work [2] provides results on invariance of languages under fuzzy bisimulations and characterizations of fuzzy bisimulations via factor fuzzy automata, which are similar to quotient structures but defined by using a fuzzy equivalence relation. One of the results of [2] states that, given a fuzzy automaton A and for E being the greatest fuzzy forward bisimulation on A , the factor fuzzy automaton of A w.r.t. E is minimal among the fuzzy automata that are “uniformly forward bisimulation equivalent” to  A .

The notion of bisimulation arose from research on modal logics [14–16] and state transition systems [7, 12]. It has widely been studied for various variants and extensions of modal logics. In [5] Fan introduced fuzzy bisimulations for some Gödel modal logics, which are fuzzy modal logics using the Gödel semantics. She also studied crisp bisimulations for Gödel modal logics extended with involutive negation. She provided results on the Hennessy-Milner property of such fuzzy/crisp bisimulations.

Description logics (DLs) are variants of modal logics that are used for representing and reasoning about terminological knowledge. In DLs, the domain of an interpretation consists of individuals, which are counterparts of states and possible worlds in modal logics. Concepts and roles in DLs correspond to formulas and accessibility relations in modal logics, respectively. Thus, a concept is interpreted as a set of individuals, and a role as a binary relation between individuals. They are built from atomic concepts (concept names), atomic roles (role names) and individual names by using constructors. Terminological axioms about all individuals are grouped into a TBox, and assertions about named individuals are grouped into an ABox. Crisp bisimulations have been studied for DLs [3, 13]. Minimizing crisp interpretations in DLs by using crisp bisimulations has been studied in [3, 4]. In [6] Ha et al. defined and studied fuzzy bisimulations and bisimilarity relations for fuzzy DLs under the Gödel semantics. They provided results on invariance of concepts under fuzzy bisimulations, conditional invariance of fuzzy TBoxes and fuzzy ABoxes under bisimilarity, and the Hennessy-Milner property of fuzzy bisimulations.

In this paper, we study the problem of minimizing interpretations in fuzzy DLs under the Gödel semantics by using fuzzy bisimulations. This is the first time the problem is investigated. The considered logics are fuzzy extensions of the DL ALC reg (a variant of propositional dynamic logic) with additional features among inverse roles, nominals and the universal role. Given a fuzzy interpretation I and for E being the greatest fuzzy auto-bisimulation of I w.r.t. the considered DL, we define the quotient I / E of I w.r.t. E and prove that it is minimum w.r.t. certain criteria. Namely, I / E is a minimum fuzzy interpretation that validates the same set of fuzzy terminological axioms in the considered DL as I . Furthermore, if the considered DL allows the universal role, then I / E is a minimum fuzzy interpretation bisimilar to  I , as well as a minimum fuzzy interpretation that validates the same set of fuzzy concept assertions in the considered DL as  I .

The rest of this paper is structured as follows. Section 2 presents notation and definitions related to fuzzy DLs. In Section 3, we recall the notions of fuzzy bisimulation and bisimilarity for fuzzy DLs under the Gödel semantics [6], but restrict them to the class of DLs studied in the current paper. We also recall some results of [6]. Section 4 contains our results and examples on minimization. Concluding remarks are given in Section 5.

2 Preliminaries

In this section, we recall definitions of the Gödel fuzzy operators, fuzzy relations, fuzzy DLs under the Gödel semantics, and related notions that are needed for this paper.

3 Fuzzy bisimulations

In this section, we recall the notions of fuzzy bisimulation and bisimilarity defined in [6] for fuzzy DLs under the Gödel semantics, but restrict them to the case with Φ ⊆ {I, O, U}. We then recall some results of [6]. All theorems and assertions presented in this section come from [6] or directly follow from the results of [6].

Definition 2. Let I and I ′ be fuzzy interpretations. A fuzzy relation Z : Δ I × Δ I ′ → [ 0 , 1 ] is called a fuzzy Φ-bisimulation (under the Gödel semantics) between I and I ′ if the following conditions hold for every x ∈ Δ I , x ′ ∈ Δ I ′ , A ∈ C, a ∈ I, r ∈ R and every basic role R w.r.t. Φ: Z ( x , x ′ ) ≤ ( A I ( x ) ⇔ A I ′ ( x ′ ) )(1) ∀ y ∈ Δ I ∃ y ′ ∈ Δ I ′ Z ( x , x ′ ) ⊗ R I ( x , y ) ≤ Z ( y , y ′ ) ⊗ R I ′ ( x ′ , y ′ )(2) ∀ y ′ ∈ Δ I ′ ∃ y ∈ Δ I Z ( x , x ′ ) ⊗ R I ′ ( x ′ , y ′ ) ≤ Z ( y , y ′ ) ⊗ R I ( x , y ) ;(3) if O ∈ Φ, then Z ( x , x ′ ) ≤ ( x = a I ⇔ x ′ = a I ′ ) ;(4) if U ∈ Φ, then ∀ y ∈ Δ I ∃ y ′ ∈ Δ I ′ Z ( x , x ′ ) ≤ Z ( y , y ′ )(5) ∀ y ′ ∈ Δ I ′ ∃ y ∈ Δ I Z ( x , x ′ ) ≤ Z ( y , y ′ ) .(6) For example, if Φ = {I, O}, then only Conditions (1)-(4) are essential. ■

Example 3. Let R = {r}, C = {A} and I = {a}. Consider the fuzzy interpretations I and I ′ illustrated below and specified similarly as in Example 2, with a I = u and a I ′ = u ′ .

Let Z be the greatest fuzzy Φ-bisimulation between I and I ′ . Consider the case when Φ ⊆ {O}. By Condition (1), we have that Z ( u , v i ′ ) = 0 for i ∈ {1, 2}, Z (v _i , u′) =0 for i ∈ {1, 2, 3}, Z ( v 1 , v 2 ′ ) ≤ 0.7 , Z ( v 2 , v 1 ′ ) ≤ 0.7 , Z ( v 3 , v i ′ ) ≤ 0.3 for i ∈ {1, 2}. By Condition (2) with x = u, x′ = u′, y = v₃ and R = r, we have that Z (u, u′) ≤0.3. It can be checked that Z 1 = { 〈 u , u ′ 〉 : 0.3 , 〈 v 1 , v 1 ′ 〉 : 1 , 〈 v 1 , v 2 ′ 〉 : 0.7 , 〈 v 2 , v 1 ′ 〉 : 0.7 , 〈 v 2 , v 2 ′ 〉 : 1 , 〈 v 3 , v 1 ′ 〉 : 0.3 , 〈 v 3 , v 2 ′ 〉 : 0.3 } is a Φ-bisimulation between I and I ′ . Therefore, Z = Z₁. Consider the case when {U} ⊆ Φ ⊆ {O, U}. We have that Z ≤ Z₁. By Condition (5) with x = v₁, x ′ = v 1 ′ and y = u, we have that Z ( v 1 , v 1 ′ ) ≤ 0.3 . Similarly, Z ( v 2 , v 1 ′ ) ≤ 0.3 and Z ( v 2 , v 2 ′ ) ≤ 0.3 . It can be checked that Z 2 = { 〈 u , u ′ 〉 : 0.3 } ∪ { 〈 v i , v j ′ 〉 : 0.3 ∣ 1 ≤ i ≤ 3 , 1 ≤ j ≤ 2 } is a Φ-bisimulation between I and I ′ . Therefore, Z = Z₂. Consider the case when I ∈ Φ. We have that Z ≤ Z₁. By Condition (2) with x = v₁, x ′ = v 1 ′ and R = r^-, we have that Z ( v 1 , v 1 ′ ) ≤ 0.3 . Similarly, Z ( v i , v j ′ ) ≤ 0.3 for all 1 ≤ i ≤ 3 and 1 ≤ j ≤ 2. It can be checked that Z₂ is also a Φ-bisimulation between I and I ′ for this case. Therefore, Z = Z₂.

Proposition 1. Let I , I ′ and I ″ be fuzzy interpretations.

The function Z : Δ I × Δ I → [ 0 , 1 ] specified by Z ( x , x ′ ) = ( if x = x′ then 1 else 0 ) is a fuzzy Φ-bisimulation between I and itself.

Let I and I ′ be fuzzy interpretations. For x ∈ Δ I and x ′ ∈ Δ I ′ , we write x ∼  _Φ x′ to denote that there exists a fuzzy Φ-bisimulation Z between I and I ′ such that Z (x, x′) =1. If x ∼  _Φ x′, then we say that x and x′ are Φ-bisimilar. If I≠ ∅ and there exists a fuzzy Φ-bisimulation Z between I and I ′ such that Z ( a I , a I ′ ) = 1 for all a ∈ I, then we say that I and I ′ are Φ-bisimilar and write I ∼ Φ I ′ .

The theorems and corollaries presented in the rest of this section are versions of the ones of [6] that are restricted to finite fuzzy interpretations.

Theorem 1. If Z is a fuzzy Φ-bisimulation between finite fuzzy interpretations I and  I ′ , then for every x ∈ Δ I , every x ′ ∈ Δ I ′ and every concept C of L Φ , Z ( x , x ′ ) ≤ ( C I ( x ) ⇔ C I ′ ( x ′ ) ) .

Theorem 2. Let I and I ′ be finite fuzzy interpretations. The function Z : Δ I × Δ I ′ → [ 0 , 1 ] specified by Z ( x , x ′ ) = inf { C I ( x ) ⇔ C I ′ ( x ′ ) ∣ C is a concept of LΦ 0 } is the greatest fuzzy Φ-bisimulation between I and  I ′ .

Given fuzzy interpretations I , I ′ and x ∈ Δ I , x ′ ∈ Δ I ′ , we write x ≡  _Φ x′ (resp. x ≡ Φ 0 x ′ ) to denote that C I ( x ) = C I ′ ( x ′ ) for every concept C of  L Φ (resp.  L Φ 0 ).

Corollary 1. Let I , I ′ be finite fuzzy interpretations and let x ∈ Δ I , x ′ ∈ Δ I ′ . Then, x ≡ Φ x ′ iff x ∼ Φ x ′ iff x ≡ Φ 0 x ′ .

Ccorollary 2. Let I and I ′ be finite fuzzy interpretations and suppose I≠ ∅. Then, I and I ′ are Φ-bisimilar iff a I ≡ Φ 0 a I ′ for all a ∈ I.

A fuzzy TBox T is said to be invariant under Φ-bisimilarity between finite fuzzy interpretations if, for every finite fuzzy interpretations I and I ′ that are Φ-bisimilar, I ⊨ T iff I ′ ⊨ T . The notion of invariance of fuzzy ABoxes under Φ-bisimilarity between finite fuzzy interpretations is defined analogously.

Theorem 3. If U ∈ Φ, then all fuzzy TBoxes in L Φ are invariant under Φ-bisimilarity between finite fuzzy interpretations.

Theorem 4. Let A be a fuzzy ABox in L Φ . If O ∈ Φ or A consists of only fuzzy assertions of the form C (a) ⋈ p, then A is invariant under Φ-bisimilarity between finite fuzzy interpretations.

Let I be a finite fuzzy interpretation. By Theorem 2, the greatest fuzzy Φ-bisimulation between I and itself exists. We call it the greatest fuzzy Φ-auto-bisimulation of I . By Proposition 1, it is a fuzzy equivalence relation. In this section, we define the quotient fuzzy interpretation I / E of I w.r.t. the greatest fuzzy Φ-auto-bisimulation E of I and prove that it is minimum w.r.t. certain criteria. Note that we study only the case with Φ ⊆ {I, O, U}.

Proposition 2. If E is the greatest fuzzy Φ-auto-bisimulation of a fuzzy interpretation  I , then it is also the greatest fuzzy (Φ ∪ {U})-auto-bisimulation of  I .

This proposition holds because Conditions (5) and (6) hold when I ′ = I .

Definition 3. Let I be a finite fuzzy interpretation and E the greatest fuzzy Φ-auto-bisimulation of I . The quotient fuzzy interpretation I / E of I w.r.t. the fuzzy equivalence relation E is specified as follows:

Δ I / E = { E x ∣ x ∈ Δ I } ,

By Lemma 1, this definition is well-defined.

Example 4. Let R = {r}, C = {A} and I = {a}. Consider the fuzzy interpretation I illustrated below and specified similarly as in Example 3, with a I = u .

It is the combination of the two fuzzy interpretations given in Example 3. For a fixed Φ, let E be the greatest fuzzy Φ-auto-bisimulation of  I .

Consider the case when Φ ⊆ {U}. Similarly as for Example 3, we have that E (u, u′) ≤0.3 and E is the reflexive-symmetric closure of {〈u, u′〉  :  0.3, 〈 v i , v i ′ 〉 : 1 , 〈 v i , v j ′ 〉 : 0.7 , 〈v₃, v _i 〉  :  0.3, 〈 v 3 , v i ′ 〉 : 0.3 ∣ {i, j} ⊆ {1, 2}, i ≠ j}. We have that:

E _u  = {u  :  1, u′  :  0.3}, E_u′ = {u′  :  1, u  :  0.3}, E v 1 = E v 1 ′ = { v 1 : 1 , v 1 ′ : 1 , v₂  :  0.7, v 2 ′ : 0.7 , v₃  :  0.3}, E v 2 = E v 2 ′ = { v 2 : 1 , v 2 ′ : 1 , v₁  :  0.7, v 1 ′ : 0.7 , v₃  :  0.3}, and E _{v 3}  = {v₃  :  1, v₁  :  0.3, v₂  :  0.3, v 1 ′ : 0.3 , v 2 ′ : 0.3 } .

The quotient fuzzy interpretation I / E is illustrated below.

{Consider the case when {O} ⊆ Φ ⊆ {O, U}. This case differs from the previous case in that E (u, u′) =0. The quotient fuzzy interpretation I / E remains the same as for the previous case except that E _u and E_u′ are now something else. Consider the case when I ∈ Φ. Similarly as for Example 3, it can be checked that E is the reflexive closure of {〈u, u′〉  :  0.3, 〈u′, u〉  : 0.3}   ∪ { 〈 x , y 〉 : 0.3 ∣ x , y ∈ { v 1 , v 2 , v 3 , v 1 ′ , v 2 ′ } , x ≠ y } . Thus, E _x  ≠ E _y if x ≠ y, for all x , y ∈ Δ I . It can be checked that I / E is “isomorphic” to  I (in particular, r I / E ( E x , E y ) = r I ( x , y ) for all x , y ∈ Δ I ).

Example 5. Consider a modification of Example 4 with r I ( u , v 3 ) = 0.7 and A I ( v 3 ) = 0.9 . The modified fuzzy interpretation I is illustrated below.

Let E be the greatest fuzzy Φ-auto-bisimulation of  I . Consider the case when Φ ⊆ {U}. It can be checked that E is the reflexive-symmetric closure of { 〈 v i , v i ′ 〉 : 1 , 〈 v i , v j ′ 〉 : 0.7 ∣ {i, j} ⊆ {1, 2}, i≠ j}   ∪ {〈u, u′〉  :  1, 〈v₃, v₁〉  :  0.7, 〈v₃, v₂〉  :  0.8, 〈 v 3 , v 1 ′ 〉 : 0.7 , 〈 v 3 , v 2 ′ 〉 : 0.8 } . Thus, E _u  = E_u′, E v 1 = E v 1 ′ and E v 2 = E v 2 ′ . The quotient fuzzy interpretation I / E is illustrated below.

Lemma 2. Let I be a finite fuzzy interpretation and E the greatest fuzzy Φ-auto-bisimulation of I . Let Z : Δ I × Δ I / E → [ 0 , 1 ] be specified by Z (x, E_x″) = E (x, x″). Then, Z is a fuzzy Φ-bisimulation between I and I / E . It is also a fuzzy (Φ ∪ {U})-bisimulation between I and I / E .

Proof. We need to prove Conditions (1)–(6) (regardless of whether U ∈ Φ) for I ′ = I / E .

Consider Condition (1) with x′ = E_x″. We have Z ( x , E x ″ ) = E ( x , x ″ ) ≤ ( A I ( x ) ⇔ A I ( x ″ ) ) = ( A I ( x ) ⇔ A I / E ( E x ″ ) ) .

Corollary 3. Let I be a finite fuzzy interpretation and E the greatest fuzzy Φ-auto-bisimulation of I . If I≠ ∅, then I and I / E are both Φ-bisimilar and (Φ ∪ {U})-bisimilar.

This corollary immediately follows from Lemma 2.

Corollary 4. Let I be a finite fuzzy interpretation, E the greatest fuzzy Φ-auto-bisimulation of I , T a fuzzy TBox and A a fuzzy ABox in L Φ . Then:

I ⊨ T iff I / E ⊨ T ,

Proof. Without loss of generality, we assume that I≠ ∅. By Corollary 3, I and I / E are both Φ-bisimilar and (Φ ∪ {U})-bisimilar. By Theorem 3, all fuzzy TBoxes in L Φ are invariant under (Φ ∪ {U})-bisimilarity between finite fuzzy interpretations. In particular, T is invariant under (Φ ∪ {U})-bisimilarity between finite fuzzy interpretations. Hence, I ⊨ T iff I / E ⊨ T . Consider the second assertion and suppose that O ∈ Φ or A consists of only fuzzy assertions of the form C (a) ⋈ p. By Theorem 4, A is invariant under Φ-bisimilarity between finite fuzzy interpretations. Hence, I ⊨ A iff I / E ⊨ A . □

In the following theorem, the term “minimum” is understood w.r.t. the size of the domain of the considered fuzzy interpretation.

Theorem 5. Let I be a finite fuzzy interpretation and E the greatest fuzzy Φ-auto-bisimulation of I . Then:

I / E is a minimum fuzzy interpretation that validates the same set of fuzzy GCIs in L Φ as I ,

Proof. Without loss of generality, we assume that I≠ ∅. By Corollaries 3 and 4, I / E validates the same set of fuzzy GCIs in L Φ as I , is Φ-bisimilar to I , and validates the same set of fuzzy assertions of the form C (a) ⋈ p in L Φ as I . It remains to justify its minimality. Since I is finite, I / E is also finite. Let Δ I / E = { v 1 , … , v n } , where v₁, …, v _n are pairwise distinct and v _i  = E _{x i} with x i ∈ Δ I , for 1 ≤ i ≤ n. By Lemma 2, x _i  ∼  _Φ v _i for all 1 ≤ i ≤ n. Let i and j be arbitrary indexes such that 1 ≤ i, j ≤ n and i ≠ j. We have that x _{i notsimΦ}x _j , and by Proposition 1, it follows that v _{i notsimΦ}v _j . Consequently, by Corollary 1, v i ≢ Φ 0 v j . Therefore, there exists a concept C_i,j of L Φ 0 such that C i , j I / E ( v i ) ≠ C i , j I / E ( v j ) . Let D i , j = ( C i , j → C i , j I / E ( v i ) ) if C i , j I / E ( v i ) < C i , j I / E ( v j ) , and D i , j = ( C i , j I / E ( v i ) → C i , j ) otherwise (i.e., when C i , j I / E ( v i ) > C i , j I / E ( v j ) ). We have that D i , j I / E ( v i ) = 1 and D i , j I / E ( v j ) < 1 . Let D _i  = D_i,1 ⊓ … ⊓ D_i,i-1 ⊓ D_i,i+1 ⊓ … ⊓ D_i,n. We have that D i I / E ( v i ) = 1 and D i I / E ( v j ) < 1 . Let F = D₁ ⊔ … ⊔ D _n and F _i  = D₁ ⊔ … ⊔ D_i-1 ⊔ D_i+1 ⊔ … ⊔ D _n . We have that I / E validates the fuzzy GCI (1 ⊑ F) ≥1 but does not validate (1 ⊑ F _i ) ≥1 for any 1 ≤ i ≤ n. Any other fuzzy interpretation with such properties must have at least n elements in the domain. That is, I / E is a minimum fuzzy interpretation that validates the same set of fuzzy GCIs in L Φ as I . Consider the second assertion of the theorem and suppose U ∈ Φ. Let Z : Δ I × Δ I / E → [ 0 , 1 ] be specified by Z (x, E_x″) = E (x, x″). By Lemma 2, Z is a Φ-bisimulation between I and I / E .

Consider the assertion 2a of the theorem and let I ′ be a fuzzy interpretation Φ-bisimilar to  I . There exists a Φ-bisimulation Z′ between I ′ and I such that Z ′ ( a I ′ , a I ) = 1 for all a ∈ I. Let Z″ = Z′ ∘ Z. By Proposition 1, Z″ is a Φ-bisimulation between I ′ and I / E . Furthermore, Z ″ ( a I ′ , a I / E ) = 1 for all a ∈ I .(7) Since I≠ ∅, by (7) and Condition (6) (with I and I ′ in Condition (6) replaced by I ′ and I / E , respectively), for every 1 ≤ i ≤ n, there exists u i ∈ Δ I ′ such that Z″ (u _i , v _i ) =1. Thus, u _i  ∼  _Φ v _i for all 1 ≤ i ≤ n. Since v _{i notsimΦ}v _j for any i ≠ j, it follows that u _{i notsimΦ}u _j for any i ≠ j. Therefore the cardinality of Δ I ′ is greater than or equal to n.

We have defined the quotient I / E of a finite fuzzy interpretation I w.r.t. its greatest fuzzy Φ-auto-bisimulation E for the case when Φ ⊆ {I, O, U} and proved that:

I / E is a minimum fuzzy interpretation that validates the same set of fuzzy GCIs in L Φ as I ,

The assertions 2a and 2b require the assumption that U ∈ Φ, which is quite restrictive. Reconsider Example 5 for the case when Φ =∅. Recall that the resultant quotient I / E is

It is not a minimum fuzzy interpretation Φ-bisimilar to I , because one can delete the individual E _{v 2} to obtain a fuzzy interpretation Φ-bisimilar to I . How to minimize fuzzy interpretations w.r.t. Φ-bisimilarity or validity of fuzzy assertions in L Φ for the case when U ∉ Φ remains a challenging open problem.

Recall that the features I, O and U stand for inverse roles, nominals and the universal role, respectively. In [6] Ha et al. defined fuzzy bisimulations also for DLs with the features Q and Self, which stand for qualified number restrictions and local reflexivity of a role, respectively. How to minimize a fuzzy interpretation w.r.t. validity in L Φ for the case when {Q, Self} ∩ Φ≠ ∅? In [3, 4] Nguyen and Divroodi studied the problem of minimizing crisp interpretations for that case. They introduced QS-interpretations that allow “multi-edges” and keep information about “self-edges” (where “edge” is understood as an instance of a role). They used such QS-interpretations for minimizing crisp interpretations for the mentioned case. Generalizing their approach for minimizing fuzzy interpretations for the case when {Q, Self} ∩ Φ≠ ∅ is a non-trivial task and remains an open problem.