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

Abstract

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

Keywords

fuzzy description logic fuzzy bisimulation bisimilarity Gödel semantics minimization

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.

2.1 The Gödel fuzzy operators

The family of Gödel fuzzy operators are defined as follows, where p, q ∈ [0, 1]: $\begin{matrix} p \otimes q & = & min {p, q} \\ p \oplus q & = & max {p, q} \\ ⊖ p & = & (if p = 0 then 1 else 0) \\ (p \Rightarrow q) & = & (if p ≤ q then 1 else q) \\ (p \Leftrightarrow q) & = & (p \Rightarrow q) \otimes (q \Rightarrow p) . \end{matrix}$

Note that $(p \Leftrightarrow q) = (if p = q then 1 else min { p,q}) .$

For a finite set Γ = {p₁, …, p_n} ⊂ [0, 1], where n ≥ 0, we define: $\begin{matrix} \otimes Γ & = & p_{1} \otimes \dots \otimes p_{n} \otimes 1 \\ \oplus Γ & = & p_{1} \oplus \dots \oplus p_{n} \oplus 0 . \end{matrix}$

2.2 Fuzzy relations

A fuzzy subset of a set Δ is a function of type Δ → [0, 1]. By representing a fuzzy subset S of Δ as {x₁ : p₁, …, x_n : p_n} we mean S (x_i) = p_i for 1 ≤ i ≤ n, and S (x) =0 for x ∈ Δ - {x₁, …, x_n}.

Let S and T be fuzzy subsets of Δ. We write S ≤ T to denote that S (x) ≤ T (x) for all x ∈ Δ. By S ∪ T we denote the fuzzy subset of Δ specified by (S ∪ T) (x) = S (x) ⊕ T (x) for x ∈ Δ. If $S$ is a set of fuzzy subsets of Δ, then by $sup S$ we denote the fuzzy subset of Δ specified by $(sup S) (x) = sup {S (x) ∣ S \in S}$ .

A fuzzy (binary) relation between two sets Δ and Δ′ is a fuzzy subset of Δ × Δ′. Given a fuzzy relation R : Δ × Δ′ → [0, 1], the inverse of R is the fuzzy relation R^- : Δ′ × Δ → [0, 1] such that R^- (x, y) = R (y, x) for all x ∈ Δ′ and y ∈ Δ. Given fuzzy relations R : Δ × Δ′ → [0, 1] and S : Δ′ × Δ″ → [0, 1], the composition of R and S is the fuzzy relation (R ∘ S) : Δ × Δ″ → [0, 1] defined as follows: $(R \circ S) (x, y) = sup {R (x, z) \otimes S (z, y) ∣ z \in Δ^{'}} .$

Similarly, given a fuzzy relation S : Δ × Δ′ → [0, 1] and a fuzzy subset T : Δ′ → [0, 1], the composition of S and T is the fuzzy subset (S ∘ T) : Δ → [0, 1] defined as follows: $(S \circ T) (x) = sup {S (x, y) \otimes T (y) ∣ y \in Δ^{'}} .$ A fuzzy relation E : Δ × Δ → [0, 1] is called a fuzzy equivalence relation on Δ if it satisfies the following conditions:

reflexity: ∀x ∈ Δ E (x, x) =1,

symmetry: ∀x, y ∈ Δ E (x, y) = E (y, x),

transitivity: ∀x, y, z ∈ Δ E (x, y) ⊗ E (y, z) ≤ E (x, z).

Given a fuzzy equivalence relation E on Δ and a ∈ Δ, the fuzzy equivalence class of E determined by a is defined to be the fuzzy subset E_a of Δ specified by E_a (x) = E (a, x), for x ∈ Δ.

Lemma 1. [see, e.g., [2]] Let E be a fuzzy equivalence relation on Δ. For every x, y ∈ Δ, the following conditions are equivalent:

E (x, y) =1,

E_x = E_y,

E (x, z) = E (y, z) for all z ∈ Δ,

E (z, x) = E (z, y) for all z ∈ Δ.

2.3 Fuzzy description logics under the Gödel semantics

In this paper, by Φ we denote a subset of {I, O, U}, where the symbols I, O and U stand for the features of inverse roles, nominals and the universal role, respectively. In this subsection, we first define the syntax of roles and concepts in the fuzzy DL $L_{Φ}$ , where $L$ extends the DL ${ALC}_{reg}$ with fuzzy truth values and $L_{Φ}$ extends $L$ with the features from Φ. We then define fuzzy interpretations and the Gödel semantics of $L_{Φ}$ .

Our logic language uses a finite set C of concept names, a finite set R of role names, and a finite set I of individual names. A basic role w.r.t. Φ is either a role name or the inverse r^- of a role name r (when I ∈ Φ).

Roles and concepts of $L_{Φ}$ are defined as follows:

if r ∈ R, then r is a role of $L_{Φ}$ ,

if R, S are roles of $L_{Φ}$ and C is a concept of $L_{Φ}$ , then R ∘ S, R ⊔ S, R^* and C ? are roles of $L_{Φ}$ ,

if I ∈ Φ and R is a role of $L_{Φ}$ , then R^- is a role of $L_{Φ}$ ,

if U ∈ Φ, then U is a role of $L_{Φ}$ , called the universal role (we assume that U ∉ R),

if p ∈ [0, 1], then p is a concept of $L_{Φ}$ ,

if A ∈ C, then A is a concept of $L_{Φ}$ ,

if C and D are concepts of $L_{Φ}$ and R is a role of $L_{Φ}$ , then:

C ⊓ D, C → D, ¬C, C ⊔ D, ∀R . C and ∃R . C are concepts of $L_{Φ}$ ,

if O ∈ Φ and a ∈ I, then {a} is a concept of $L_{Φ}$ .

The concept 0 stands for ⊥, and 1 for ⊤.

By $L_{Φ}^{0}$ we denote the largest sublanguage of $L_{Φ}$ that disallows the role constructors R ∘ S, R ⊔ S, R^*, C ? and the concept constructors ¬C, C ⊔ D, ∀R . C.

Example 1. One can represent data and knowledge about a collection of publications by using:

concept names: Author, Publication, Topic, …

role names:

wrote (an author wrote a publication),

writtenBy (a publication was written, among others, by an author),

relatedTo (a publication or a topic is related to another one),

interestedIn (an author is interested in a topic),

individual names:

topics: logic, algorithms, fuzzy systems, …

and identifications of authors and publications.

The role names relatedTo and interestedIn are fuzzy predicates. Here are examples of complex concepts:

∃wrote . ∃ relatedTo . {fuzzysystems}: this stands for the set of authors who wrote some publications related to fuzzy systems,

Author ⊓ ∀ wrote.∃ relatedTo.{fuzzy systems}: this stands for the set of authors who wrote only publications that are related to fuzzy systems,

∀writtenBy . ¬ ∃ interestedIn . {logic}: this stands for the set of publications written only by authors not interested in logic. ■

We use letters A and B to denote atomic concepts (which are concept names), C and D to denote arbitrary concepts, r and s to denote atomic roles (which are role names), R and S to denote arbitrary roles, a and b to denote individual names.

Definition 1. A (fuzzy) interpretation is a pair $I = 〈 Δ^{I}, \cdot^{I} 〉$ , where $Δ^{I}$ is a non-empty set, called the domain, and $\cdot^{I}$ is the interpretation function, which maps every individual name a to an element $a^{I} \in Δ^{I}$ , every concept name A to a fuzzy subset $A^{I}$ of $Δ^{I}$ , and every role name r to a fuzzy binary relation $r^{I}$ on $Δ^{I}$ . The function $\cdot^{I}$ is extended to complex roles and concepts as follows (cf. [1]), where the extrema are taken in the complete lattice [0, 1]: $\begin{matrix} U^{I} (x, y) = 1 \\ (R^{-})^{I} (x, y) = R^{I} (y, x) \\ (C ?)^{I} (x, y) = (if x = y then C I(x) else 0) \\ (R \circ S)^{I} (x, y) = \\ sup {R^{I} (x, z) \otimes S^{I} (z, y) ∣ z \in Δ^{I}} \\ (R ⊔ S)^{I} (x, y) = R^{I} (x, y) \oplus S^{I} (x, y) \\ (R^{*})^{I} (x, y) = sup {\otimes {R^{I} (x_{i}, x_{i + 1}) ∣ 0 \leq i < n} ∣ \\ n \geq 0, x_{0}, \dots, x_{n} \in Δ^{I}, x_{0} = x, x_{n} = y} \end{matrix}$

$\begin{matrix} p^{I} (x) = p \\ {a}^{I} (x) = (if x = a I then 1 else 0) \\ (\neg C)^{I} (x) = ⊖ C^{I} (x) \\ (C ⊓ D)^{I} (x) = C^{I} (x) \otimes D^{I} (x) \\ (C ⊔ D)^{I} (x) = C^{I} (x) \oplus D^{I} (x) \\ (C \to D)^{I} (x) = (C^{I} (x) \Rightarrow D^{I} (x)) \\ (\exists R . C)^{I} (x) = sup {R^{I} (x, y) \otimes C^{I} (y) ∣ y \in Δ^{I}} \\ (\forall R . C)^{I} (x) = inf {R^{I} (x, y) \Rightarrow C^{I} (y) ∣ y \in Δ^{I}} . \end{matrix}$

For definitions of the Zadeh, Łukasiewicz and Product semantics for fuzzy DLs, we refer the reader to [1].

Example 2. Let R = {r}, C = {A} and I = {a}. Consider the fuzzy interpretation $I$ illustrated and specified below:

We have that: $\begin{matrix} (\exists r . A)^{I} = {u : 0.5}, \\ (\forall r . A)^{I} = {u : 0.3, v_{1} : 1, v_{2} : 1, v_{3} : 1}, \\ (\exists (r ⊔ r^{-})^{*} . A)^{I} = {u : 0.5, v_{1} : 0.7, v_{2} : 0.8, v_{3} : 0.5}, \\ (\forall U . ({a} ⊔ (0.4 \to A)))^{I} = {x : 0.3 ∣ x \in Δ^{I}} . \end{matrix}$

A fuzzy interpretation $I$ is finite if $Δ^{I}$ is finite.

A fuzzy assertion in $L_{Φ}$ is an expression of the form a ≐ b, a $\dot{\neq}$ b, C (a) ⋈ p or R (a, b) ⋈ p, where C is a concept of $L_{Φ}$ , R is a role of $L_{Φ}$ , ⋈ ∈ {≥ , > , ≤ , <} and p ∈ [0, 1]. A fuzzy assertion of the form C (a) ⋈ p is called a fuzzy concept assertion. A fuzzy ABox in $L_{Φ}$ is a finite set of fuzzy assertions in $L_{Φ}$ .

A fuzzy GCI (general concept inclusion) in $L_{Φ}$ , also called a fuzzy terminological axiom in $L_{Φ}$ , is an expression of the form (C ⊑ D) ⊳ p, where C and D are concepts of $L_{Φ}$ , ⊳ ∈ {≥ , >} and p ∈ [0, 1]. A fuzzy TBox in $L_{Φ}$ is a finite set of fuzzy GCIs in $L_{Φ}$ .

Given a fuzzy interpretation $I$ and a fuzzy assertion or GCI φ, we say that $I$ validates φ, denoted by $I ⊨ φ$ , if:

case φ = (a ≐ b): $a^{I} = b^{I}$ ,

case φ = (a $\dot{\neq}$ b): $a^{I} \neq b^{I}$ ,

case φ = (C (a) ⋈ p): $C^{I} (a^{I}) ⋈ p$ ,

case φ = (R (a, b) ⋈ p): $R^{I} (a^{I}, b^{I}) ⋈ p$ ,

case φ = (C ⊑ D) ⊳ p: $(C \to D)^{I} (x) ⊳ p$ for all $x \in Δ^{I}$ .

A fuzzy interpretation $I$ is a model of a fuzzy ABox $A$ , denoted by $I ⊨ A$ , if $I ⊨ φ$ for all $φ \in A$ . Similarly, $I$ is a model of a fuzzy TBox $T$ , denoted by $I ⊨ T$ , if $I ⊨ φ$ for all $φ \in T$ .

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} \times Δ^{I'} \to [0, 1]$ is called a fuzzy Φ-bisimulation (under the Gödel semantics) between $I$ and $I^{'}$ if the following conditions hold for every $x \in Δ^{I}$ , $x^{'} \in Δ^{I'}$ , A ∈ C, a ∈ I, r ∈ R and every basic role R w.r.t. Φ: $Z (x, x^{'}) \leq (A^{I} (x) \Leftrightarrow A^{I'} (x^{'}))$ (1) $\forall y \in Δ^{I} \exists y^{'} \in Δ^{I'}$ $Z (x, x^{'}) \otimes R^{I} (x, y) \leq Z (y, y^{'}) \otimes R^{I'} (x^{'}, y^{'})$ (2) $\forall y^{'} \in Δ^{I'} \exists y \in Δ^{I}$ $Z (x, x^{'}) \otimes R^{I'} (x^{'}, y^{'}) \leq Z (y, y^{'}) \otimes R^{I} (x, y);$ (3) if O ∈ Φ, then $Z (x, x^{'}) \leq (x = a^{I} \Leftrightarrow x^{'} = a^{I'});$ (4) if U ∈ Φ, then $\forall y \in Δ^{I} \exists y^{'} \in Δ^{I'} Z (x, x^{'}) \leq Z (y, y^{'})$ (5) $\forall y^{'} \in Δ^{I'} \exists y \in Δ^{I} Z (x, x^{'}) \leq 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}^{'}) \leq 0.7$ , $Z (v_{2}, v_{1}^{'}) \leq 0.7$ , $Z (v_{3}, v_{i}^{'}) \leq 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}^{'}) \leq 0.3$ . Similarly, $Z (v_{2}, v_{1}^{'}) \leq 0.3$ and $Z (v_{2}, v_{2}^{'}) \leq 0.3$ . It can be checked that $Z_{2} = {〈 u, u^{'} 〉 : 0.3} \cup {〈 v_{i}, v_{j}^{'} 〉 : 0.3 ∣ 1 \leq i \leq 3, 1 \leq j \leq 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}^{'}) \leq 0.3$ . Similarly, $Z (v_{i}, v_{j}^{'}) \leq 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} \times Δ^{I} \to [0, 1]$ specified by $Z (x, x^{'}) = (if x = x′ then 1 else 0)$ is a fuzzy Φ-bisimulation between $I$ and itself.

If Z is a fuzzy Φ-bisimulation between $I$ and $I^{'}$ , then Z^- is a fuzzy Φ-bisimulation between $I^{'}$ and $I$ .

If Z₁ is a fuzzy Φ-bisimulation between $I$ and $I^{'}$ , and Z₂ is a fuzzy Φ-bisimulation between $I^{'}$ and $I^{″}$ , then Z₁ ∘ Z₂ is a fuzzy Φ-bisimulation between $I$ and $I^{″}$ .

If $Z$ is a finite set of fuzzy Φ-bisimulations between $I$ and $I^{'}$ , then $sup Z$ is also a fuzzy Φ-bisimulation between $I$ and $I^{'}$ .

Let $I$ and $I^{'}$ be fuzzy interpretations. For $x \in Δ^{I}$ and $x^{'} \in Δ^{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 \sim_{Φ} 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 \in Δ^{I}$ , every $x^{'} \in Δ^{I'}$ and every concept C of $L_{Φ}$ , $Z (x, x^{'}) \leq (C^{I} (x) \Leftrightarrow C^{I'} (x^{'})) .$

Theorem 2. Let $I$ and $I^{'}$ be finite fuzzy interpretations. The function $Z : Δ^{I} \times Δ^{I'} \to [0, 1]$ specified by $\begin{matrix} Z (x, x^{'}) & = & inf {C^{I} (x) \Leftrightarrow C^{I'} (x^{'}) ∣ \\ C is a concept of LΦ 0} \end{matrix}$ is the greatest fuzzy Φ-bisimulation between $I$ and $I^{'}$ .

Given fuzzy interpretations $I$ , $I^{'}$ and $x \in Δ^{I}$ , $x^{'} \in Δ^{I'}$ , we write x ≡ _Φx′ (resp. $x \equiv_{Φ}^{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 \in Δ^{I}$ , $x^{'} \in Δ^{I'}$ . Then, $x \equiv_{Φ} x^{'} iff x \sim_{Φ} x^{'} iff x \equiv_{Φ}^{0} x^{'} .$

Ccorollary 2. Let $I$ and $I^{'}$ be finite fuzzy interpretations and suppose I≠ ∅. Then, $I$ and $I^{'}$ are Φ-bisimilar iff $a^{I} \equiv_{Φ}^{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.

4 Minimizing 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 \in Δ^{I}}$ ,

$a^{I /_{E}} = E_{a^{I}}$ for a ∈ I,

$A^{I /_{E}} (E_{x}) = A^{I} (x)$ for A ∈ C and $x \in Δ^{I}$ ,

$r^{I /_{E}} (E_{x}, E_{y}) = (E \circ r^{I} \circ E) (x, y)$ for r ∈ R and $x, y \in Δ^{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
₃} = {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 \in {v_{1}, v_{2}, v_{3}, v_{1}^{'}, v_{2}^{'}}, x \neq y}$ . Thus, E_x ≠ E_y if x ≠ y, for all $x, y \in Δ^{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 \in Δ^{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} \times Δ^{I /_{E}} \to [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 $\begin{matrix} Z (x, E_{x^{″}}) & = & E (x, x^{″}) \\ \leq & (A^{I} (x) \Leftrightarrow A^{I} (x^{″})) \\ = & (A^{I} (x) \Leftrightarrow A^{I /_{E}} (E_{x^{″}})) . \end{matrix}$

Consider Condition (2). Let x′ = E_x″ and $y \in Δ^{I}$ . Since E is the greatest fuzzy Φ-auto-bisimulation of $I$ , there exists $y^{″} \in Δ^{I}$ such that $E (x, x^{″}) \otimes R^{I} (x, y) \leq E (y, y^{″}) \otimes R^{I} (x^{″}, y^{″}) .$ Thus, $\begin{matrix} E (x, x^{″}) \otimes R^{I} (x, y) \\ \leq & E (y, y^{″}) \otimes (E \circ R^{I} \circ E) (x^{″}, y^{″}) \\ = & E (y, y^{″}) \otimes R^{I /_{E}} (E_{x^{″}}, E_{y^{″}}), \end{matrix}$ which means $\begin{matrix} Z (x, E_{x^{″}}) \otimes R^{I} (x, y) \leq \\ Z (y, E_{y^{″}}) \otimes R^{I /_{E}} (E_{x^{″}}, E_{y^{″}}) . \end{matrix}$ So, we can choose y′ = E_y″.

Consider Condition (3). Let x′ = E_x″ and y′ = E_y″ with $y^{″} \in Δ^{I}$ . There exist $x_{3}, y_{3} \in Δ^{I}$ such that $\begin{matrix} R^{I /_{E}} (E_{x^{″}}, E_{y^{″}}) = \\ E (x^{″}, x_{3}) \otimes R^{I} (x_{3}, y_{3}) \otimes E (y_{3}, y^{″}) . \end{matrix}$ Since E is the greatest fuzzy Φ-auto-bisimulation of $I$ , there exists $y \in Δ^{I}$ such that $E (x, x_{3}) \otimes R^{I} (x_{3}, y_{3}) \leq E (y, y_{3}) \otimes R^{I} (x, y) .$ We have that $\begin{matrix} Z (x, E_{x^{″}}) \otimes R^{I /_{E}} (E_{x^{″}}, E_{y^{″}}) \\ = & E (x, x^{″}) \otimes R^{I /_{E}} (E_{x^{″}}, E_{y^{″}}) \\ = & E (x, x^{″}) \otimes E (x^{″}, x_{3}) \otimes & R^{I} (x_{3}, y_{3}) \otimes E (y_{3}, y^{″}) \\ \leq & E (x, x_{3}) \otimes R^{I} (x_{3}, y_{3}) \otimes E (y_{3}, y^{″}) \\ \leq & E (y, y_{3}) \otimes R^{I} (x, y) \otimes E (y_{3}, y^{″}) \\ \leq & E (y, y^{″}) \otimes R^{I} (x, y) \\ = & Z (y, E_{y^{″}}) \otimes R^{I} (x, y) . \end{matrix}$

Consider Condition (4) for the case O ∈ Φ. Let x′ = E_x″. Without loss of generality, suppose Z (x, x′) >0, which means E (x, x″) >0. Since E is the greatest fuzzy Φ-auto-bisimulation of $I$ , we have $E (x, x^{″}) \leq (x = a^{I} \Leftrightarrow x^{″} = a^{I})$ . By Lemma 1, $x^{″} = a^{I}$ is equivalent to $E_{x^{″}} = E_{a^{I}} = a^{I /_{E}}$ . Therefore, $\begin{matrix} Z (x, x^{'}) & = & E (x, x^{″}) \\ \leq & (x = a^{I} \Leftrightarrow x^{″} = a^{I}) \\ = & (x = a^{I} \Leftrightarrow E_{x^{″}} = a^{I /_{E}}) \\ = & (x = a^{I} \Leftrightarrow x^{'} = a^{I /_{E}}) . \end{matrix}$

Condition (5) holds because we can take y′ = E_y to have Z (y, y′) =1.

Condition (6) holds because, if y′ = E_y″, then we can take y = y″ to have Z (y, y′) =1. ■

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$ ,

if O ∈ Φ or $A$ consists of only fuzzy assertions of the form C (a) ⋈ p, then $I ⊨ A$ iff $I /_{E} ⊨ A$ .

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$ ,

if I≠ ∅ and U ∈ Φ, then:

$I /_{E}$ is a minimum fuzzy interpretation Φ-bisimilar to $I$ ,

$I /_{E}$ is a minimum fuzzy interpretation that validates the same set of fuzzy assertions of the form C (a) ⋈ p 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}, \dots, v_{n}}$ , where v₁, …, v_n are pairwise distinct and v_i = E_{x
_i} with $x_{i} \in Δ^{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}) \neq C_{i, j}^{I /_{E}} (v_{j})$ . Let $D_{i, j} = (C_{i, j} \to 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}) \to 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} \times Δ^{I /_{E}} \to [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} \in Δ^{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.

Consider the assertion 2a of the theorem and let $I^{'}$ be a fuzzy interpretation that validates the same set of fuzzy assertions of the form C (a) ⋈ p in $L_{Φ}$ as $I$ . Thus, $a^{I'} \equiv_{Φ}^{0} a^{I}$ for all a ∈ I. Without loss of generality, assume that $I^{'}$ is finite. By Corollary 2, $I^{'}$ and $I$ are Φ-bisimilar. By the assertion 2a proved above, it follows that the cardinality of $Δ^{I'}$ is greater than or equal to n. ■

5 Concluding remarks

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$ ,

if I≠ ∅ and U ∈ Φ, then:

$I /_{E}$ is a minimum fuzzy interpretation Φ-bisimilar to $I$ ,

$I /_{E}$ is a minimum fuzzy interpretation that validates the same set of fuzzy assertions of the form C (a) ⋈ p 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
₂} 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.

References

Bobillo

, Delgado

, Ómez-Romero

J.G.

and Straccia

Fuzzy description logics under Gödel semantics, Int J Approx Reasoning 50(3) (2009)494–514.

Ćirić

, Ignjatović

, Damljanović

and Bašic

Bisimulations for fuzzy automata, Fuzzy Sets and Systems 186(1) (2012)100–139.

Divroodi

A.R.

Bisimulation Equivalence in Description Logics and Its Applications, PhD thesis, University of Warsaw, 2015.

Divroodi

A.R.

and Nguyen

L.A.

On bisimulations for description logics, Information Sciences 295 (2015)465–493.

Fan

T.-F.

Fuzzy bisimulation for Gödel modal logic, IEEE Trans Fuzzy Systems 23(6) (2015)2387–2396.

Q.-T.

, Nguyen

L.A.

, Nguyen

T.H.K.

and Tran

T.-L.

Fuzzy bisimulations in fuzzy description logics under the Gödel semantics. In Proceedings of IJCRS 2018, volume 11103 of LNCS, (2018), pp. 559–571, Springer.

Hennessy

and Milner

Algebraic laws for nondeterminism and concurrency, Journal of the ACM 32(1) (1985)137–161.

Hopcroft

An n log n algorithm for minimizing states in a finite automaton. Available at ftp://reports.stanford.edu/pub/cstr/reports/cs/tr/71/190/CS-TR-71-190.pdf, 1971.

Kurtonina

and de Rijke

Expressiveness of concept expressions in first-order description logics, Artif Intell 107(2) (1999)303–333.

10.

Lutz

, Piro

and Wolter

Description logic TBoxes: Model-theoretic characterizations and rewritability. In T. Walsh, editor, Proc. of IJCAI’2011 (2011), pp. 983–988.

11.

Paige

and Tarjan

R.E.

Three partition refinement algorithms, SIAM J Comput 16(6) (1987)973–989.

12.

Park

D.M.R.

Concurrency and automata on infinite sequences. In Deussen

Peter

, editor, Proceedings of the 5th GI Conference, volume 104 of LNCS, (1981), pp. 167–183. Springer.

13.

Piro

Model Theoretic Characterisations of Description Logics, PhD thesis, University of Liverpool, 2012.

14.

van Benthem

Modal Correspondence Theory, PhD thesis, Mathematisch Instituut & Instituut voor Grondslagenonderzoek, University of Amsterdam, 1976.

15.

van Benthem

Modal Logic and Classical Logic, Bibliopolis, Naples, 1983.

16.

van Benthem

Correspondence theory. In Gabbay

and Guenther

, editors, Handbook of Philosophical Logic, Volume II, (1984), pp. 167–247. Reidel, Dordrecht.