Minimal realization for fuzzy behaviour: A bicategory-theoretic approach

Abstract

The purpose of present work is to introduce and study two minimal realizations for a given fuzzy behaviour in bicategory-theoretic setup. One such realization is based on Myhill Nerode’s theory, while the other realization is based on derivative of the given fuzzy behaviour. It is shown here that there exists a unique 2-cell in bicategory of crisp deterministic fuzzy machines between both the realizations.

Keywords

Bicategory crisp deterministic fuzzy automaton fuzzy behaviour minimal realization

1 Introduction

From the beginning of the theory of fuzzy sets by Zadeh [23], fuzzy automata, fuzzy machines and languages are introduced and studied as a means for bridging the gap between the precision of computer languages and vagueness. Such studies were initiated by Santos [4] and Wee [38]. Later, these concepts were studied and developed by many researchers (cf., [6 , 40]). The works done in [2,3,7,13,14,28,30,39,41,43,45 , 2,3,7,13,14,28,30,39,41,43,45] are towards the recent development in the abovementioned area. Among these studies, the concept of a crisp deterministic fuzzy automaton (deterministic automaton equipped with fuzzy set of final states) was introduced and studied in [13,30,43 , 13,30,43]. The importance of such automaton is justified from the fact that (i) a fuzzy language is accepted by some fuzzy automaton iff it is accepted by some crisp deterministic fuzzy automaton (cf., [30]), and (ii) the Nerode automaton of a fuzzy automaton is a crisp-deterministic fuzzy automaton equivalent to given fuzzy automaton(cf., [14]). Also, the minimization of fuzzy automata and fuzzy machines was studied in [5 , 37]. The basic idea in these cited papers was to reduce the number of states of a fuzzy automaton/machines by computing and merging indistinguishable states.

The usefulness of certain ideas, concepts and tools from category theory in the design of functional and imperative programming languages, implementation techniques for functional languages, semantic models of programming languages, the development of algorithms, polymorphism and in the development of many aspects of theoretical computer science is well-known [1]. In theoretical computer science, there have been many research dealing with the categorical approach to automata theory (cf., [10 , 36]). Among these studies, one of the famous result is the construction of minimal realization for a given behaviour by using the categorical theory (cf., [10]). Similar to category theory, bicategory theory (a concept which generalizes many familiar notions existing in the category theory (cf., [12]) has also been used in the realization theory of automata [31]. In continuation, the usefulness of category theory in the study of fuzzy automata was reported in [8 , 44]. In this paper, we use the concepts of bicategory for the study of minimal crisp deterministic fuzzy machine for a given fuzzy behaviour (a concept almost identical to fuzzy language). Specifically, we construct two minimal crisp deterministic fuzzy machines for a given fuzzy behaviour by different approaches and show that there exists a unique 2-cell between them in the bicategory of crisp deterministic fuzzymachines.

2 Preliminaries

In this section, we recall the concepts associated with fuzzy automata, deterministic fuzzy automata and fuzzy behaviours (fuzzy languages) introduced in [18, 30]. The fuzzy sets considered in this paper are in the sense of [9], i.e., a fuzzy set λ on a set X is a map λ : X → L,where L is a poset. Also, for a nonempty set X, X^* denotes the free monoid generated by X. We shall denote by ɛ, the identity element of X^*.

We begin with the following concept of a fuzzy automaton from [18].

Definition 2.1. A fuzzy automaton is a 5-tuple M = (Q, X, δ, q₀, τ), where Q and X are nonempty finite sets, called the set of states and the set of inputs, respectively, δ is a fuzzy subset of Q × X × Q, q₀ ∈ Q is initial state and τ is a fuzzy subset of Q, called the fuzzy set of final states.

In [18], it has been shown that the transition function δ : Q × X × Q → L can be extended to δ : Q × X^* × Q → L such that ∀p, q ∈ Q, ∀u ∈ X^*, and ∀x ∈ X, $δ (q, e, p) = {\begin{matrix} 1 & if q = p \\ 0 & if q \neg = p, and \end{matrix}$ $δ (p, ux, q) = \lor {δ (p, u, r) \land δ (r, x, q) : r \in Q} .$

Also, in [18], it has been observed that $\begin{matrix} δ (p, uv, q) = \lor {δ (p, u, r) \land δ (r, u, q) : r \in Q}, \\ \forall p, q \in Q, \forall u, v \in X^{*} . \end{matrix}$

Now, we recall the following from [30].

Definition 2.2. A crisp deterministic fuzzy automaton is a 5-tuple M = (Q, X, δ, q₀, τ), where Q and X are nonempty finite sets, called the set of states and the set of inputs, respectively, δ : Q × X → Q is a map, called transition function, q₀ ∈ Q is initial state and τ is a fuzzy subset of Q, called the fuzzy set of final states.

Definition 2.3. A fuzzy language f : X^* → L

is accepted by a fuzzy automaton (Q, X, δ, q₀, τ) if f (w) = ∨ {δ^* (q₀, w, p) ∧ τ (p) : p ∈ Q}, for all w ∈ X^*, and

is accepted by a crisp deterministic fuzzy automaton (Q, X, δ, q₀, τ) if f (w) = τ (δ^*(q₀, w)), for all w ∈ X^*.

Regarding the equivalence between the concepts of a fuzzy automaton and a deterministic fuzzy automaton in terms of acceptance of a fuzzy language, the following has been shown in [30].

Proposition 2.1. A fuzzy language is accepted by some fuzzy automaton iff it is accepted by some crisp deterministic fuzzy automaton.

In view of the study of fuzzy machines, several researchers [4 , 42] have included the set of output and a (fuzzy) output map instead of fuzzy set of final states in the definition of a fuzzy automaton. In this paper, we work with such crisp deterministic fuzzy machines.

3 Bicategory of crisp deterministic fuzzy machines

In this section, we introduce the concepts associated with crisp deterministic fuzzy machines and fuzzy behaviours. Throughout, we use the category Set of sets as base category.

We begin with the following.

Definition 3.1. Let X and Y be two sets. A crisp deterministic fuzzy machine is a 4-tuple M = (Q, δ, q₀, β), where

Q is a nonempty set called the state-set.

α : Q × X → Q is a map called transition map.

β : Q × Y → L is a map called fuzzy output map.

q₀ ∈ Q is a fixed state called the initial state.

For crisp deterministic fuzzy machine M = linebreak (Q, δ, q₀, β), the sets X and Y are respectively called, the input-set and the output-set.

Proposition 3.1. The class of objects of Set and arrows as crisp deterministic fuzzy machines forms abicategory.

Proof. Let A be the class of Set-objects and for X, Y∈ Set the arrows from X to Y are (Q, α, β, q₀), where α : Q × X → Q, β : Q × Y → L and q₀ : 1 → Q are maps. Then the identity arrow on X is (1, t_α, t_β, 1), where t_α : 1 × X → 1 and t_β : 1 × X → L are maps. 2-cells, composition of arrows, vertical and horizontal composition of two cells in $A$ are given as follows:

2-cells from (Q, α, β, q₀) to $(Q^{'}, α^{'}, β^{'}, q_{0}^{'})$ are arrows h : Q → Q′ of Set such that the diagrams in Fig. 1 commute. Here, we have identified q₀ in Q with the map from one element set 1 to Q which has {q₀} for its image, h × X : Q × X → Q′ × X is a map such that (h × X) (q, x) = (h (q) , x) and h × Y : Q × Y → Q′ × Y is a map such that (β′ ∘ (h × Y)) (q, y) = β′ (h (q) , y) ≥ β (q, y).

For two arrows (Q, α, β, q₀) : X → Y and $(S, α^{'}, β^{'}, q_{0}^{'}) : Y \to Z$ , their composition is an arrow $(S, α^{'}, β^{'}, q_{0}^{'}) (Q, α, β, q_{0}) =$ $(Q \times S, (Q \times α^{'}) (α \times S \times Y), β \circ β^{'}, (q_{0}, q_{0}^{'}))$ ,where (Q× α′) (α × S × Y) : Q × S × X × Y → Q × S is a map such that the diagram in Figure 2 commutes and β ∘ β′ : Q × S × Y × Z → L is a map such that (β ∘ β′) (q, s, y, z) = β (q, y) ∧ β′ (s, z).

The vertical composition of 2-cells

$h : (Q, α, β, q_{0}) \to (Q^{'}, α^{'}, β^{'}, q_{0}^{'})$ and $h^{'} : (Q^{'}, α^{'}, β^{'}, q_{0}^{'}) \to (Q^{″}, α^{″}, β^{″}, q_{0}^{″}),$ is an arrow of Set such that the diagrams in Fig. 3 commute.

For two crisp deterministic fuzzy machines

(Q, α, β, q₀) : X → Y and (S, γ, δ, s₀) : Y → Z, the horizontal composition of 2-cells

$h : (Q, α, β, q_{0}) \to (Q^{'}, α^{'}, β^{'}, q_{0}^{'})$ and $g : (S, γ, δ, s_{0}) \to (S^{'}, γ^{'}, δ^{'}, s_{0}^{'})$ is <h, g > : Q × S → Q′ × S′ such that the diagrams in Fig. 4 commute.

Hence A is a bicategory.

Remark 3.1. For X, Y∈ Set, $A (X, Y)$ denotes the set of all crisp deterministic fuzzy machines having input-set X and output-set Y.

Definition 3.2. For a given $(Q, α, β, q_{0}) \in A (X, Y)$ , the free extension α^* of α is the map α^* : Q × X^* → Q such that

α^* (q, ɛ) = q,

α^* (q, wx) = α (α^* (q, w) , x) , ∀ q ∈ Q, w ∈ X^* and x ∈ X.

Now, we have the following.

Proposition 3.2. Let $(Q, α, β, q_{0}), (S, α^{'}, β^{'}, q_{0}^{'}) \in A (X, Y)$ and $φ : (Q, α, β, q_{0}) \to (S, α^{'}, β^{'}, q_{0}^{'})$ be a 2-cell in A. Then φ (α^* (q, w)) = α^′* (φ (q) , w), ∀w ∈ X^* and q ∈ Q.

Proof. Similar to that of Lemma 6 of [31].

Definition 3.3. The reachability map r of

$(Q, α, β, q_{0}) \in A (X, Y)$ is a map r : X^* → Q such that

r (ɛ) = q₀,

r (wa) = α (r (w) , a) , ∀ w ∈ X^* and ∀a ∈ X.

Remark 3.2. It can be easily seen that

r (w) = α^* (q₀, w) , ∀ w ∈ X^*, and

r (ww′) = α^* (r (w) , w′) , ∀ w, w′ ∈ X^*.

Reachability of a crisp deterministic fuzzy machine means that all of its states should be reached from the initial state, i.e., $(Q, α, β, q_{0}) \in A (X, Y)$ is said to be reachable if for each q ∈ Q there exists w ∈ X^* such that α^* (q₀, w) = q. Which in terms of the reachability map can be characterized as the following.

Proposition 3.3. (Q, α, β, q₀) in $A (X, Y)$ is reachable iff r is onto.

Remark 3.3. For X, Y∈ Set, $A_{R} (X, Y)$ denotes the set of all reachable crisp deterministic fuzzy machines having input-set X and output-set Y.

Definition 3.4. For $M = (Q, α, β, q_{0}) \in A (X, Y)$ , the reachable kernel of M is R (Q, α, β, q₀) = (Q_R, α_R, β_R, q₀), where Q_R = {q ∈ Q : ∃ w ∈ X^*, such that α^* (q₀, w) = q}, and α_R, β_R are restrictions of α and β on Q_R × X and Q_R × Y, respectively.

Proposition 3.4. Let $(Q, α, β, q_{0}) \in A (X, Y)$ and $(S, α^{'}, β^{'}, q_{0}^{'}) \in A (Y, Z)$ . Then the assignment r_QS (q, s) = (q, s) , ∀ q ∈ Q and s ∈ S defines a 2-cell $r_{QS} : R ((S, α^{'}, β^{'}, q_{0}^{'}) (Q, α, β, q_{0})) \to R (S, α^{'}, β^{'}, q_{0}^{'}) R (Q, α, β, q_{0})$ , in A.

Proof. In order to show that r_QS is a 2-cell in A, it is enough to show that the diagrams in Fig. 5 commute. Now, to show the commutativity of the square (A) in Fig. 5, let ((q, s) _R, x, y) ∈ (Q × S) _R × X × Y. Then we have $\begin{matrix} {(r_{QS} \circ ((Q \times α^{'}) (α \times S \times Y))_{R}) ((q, s)_{R}, x, y)} \\ = r_{QS} ((Q \times α^{'}) (α (q, x)_{R}, s, y)) \end{matrix}$ $\begin{matrix} = r_{QS} ((α (q, x), α^{'} (s, y))_{R}) \\ = (α_{R} (q, x), α_{R}^{'} (s, y)), \end{matrix}$ and $\begin{matrix} {((Q_{R} \times α_{R}^{'}) (α_{R} \times S_{R} \times Y)) \\ (r_{QS} \times X \times Y) ((q, s)_{R}, x, y)} \\ = ((Q_{R} \times α_{R}^{'}) (α_{R} \times S_{R} \times Y)) (r_{QS} (q, s)_{R}, x, y) \\ = ((Q_{R} \times α_{R}^{'}) (α_{R} \times S_{R} \times Y)) ((q, s), x, y) \\ = (Q_{R} \times α_{R}^{'}) ((α_{R} \times S_{R} \times Y) ((q, s), x, y)) \\ = (Q_{R} \times α_{R}^{'}) (α_{R} (q, x), s, y) \\ = (α_{R} (q, x), α_{R}^{'} (s, y)) . \end{matrix}$

Thus ${(r_{QS} \circ ((Q \times α^{'}) (α \times S \times Y))_{R}) = {((Q_{R} \times α_{R}^{'}) (α_{R} \times S_{R} \times Y)) (r_{QS} \times X \times Y)$ . Hence the Square (A) in Fig. 5 commutes. Again, to show the commutativity of the Triangle (B) in Fig. 5, let ((q, s) _R, y, z) ∈ (Q × S) _R × Y × Z. Then we have $\begin{matrix} {((β_{R}^{'} \circ β_{R}) \circ (r_{QS} \times Y \times Z)) ((q, s)_{R}, (y, z))} \\ \geq (β^{'} \circ β)_{R} ((q, s), y, z) \\ = (β^{'} \circ β) ((q, s), (y, z)) \\ = β (q, y) \land β^{'} (s, z) \\ = (β^{'} \circ β)_{R} ((q, s)_{R}, (y, z)) . \end{matrix}$

Thus $(β_{R}^{'} \circ β_{R}) (r_{QS} \times Y \times Z) \geq (β^{'} \circ β)_{R}$ . Hence the Triangle (B) in Fig. 5 commutes.

Now, we introduce the concept of fuzzy behaviour for arbitrary sets.

Definition 3.5. For X, Y∈ Set, the fuzzy behaviour from X to Y is a map f : X^* × Y → L.

In case of crisp deterministic fuzzy machines, the concept of fuzzy behaviour may be stated as follows.

Definition 3.6. Let $(Q, α, β, q_{0}) \in A (X, Y)$ . The fuzzy behaviour (in state q) of (Q, α, β, q₀) is a map E_q ((Q, α, β, q₀)) : X^* × Y → L such that E_q ((Q, α, β, q₀)) (w, y) = β (α^* (q, w) , y) , ∀ w ∈ X^*, y∈Y. Also, the fuzzy behaviour (in state q₀), i.e., E_{q
₀} ((Q, α, β, q₀)) is called the fuzzy behaviour of (Q, α, β, q₀), and is simply denoted by E ((Q, α, β, q₀)).

Remark 3.4. It can be seen easily that E ((Q, α, β, q₀)) linebreak = β ∘ (r × Y).

Proposition 3.5. Let $φ : (Q, α, β, q_{0}) \to (S, α^{'}, β^{'}, q_{0}^{'})$ be a 2-cell in A. Then $E ((Q, α, β, q_{0})) = E ((S, α^{'}, β^{'}, q_{0}^{'})) .$

Proof. We prove this by induction on the length of strings in X^*. For this, let w ∈ X^* and y ∈ Y. Then for |w|=0,

$\begin{matrix} E ((Q, α, β, q_{0})) (ɛ, y) \\ = β (α^{*} (q_{0}, ɛ), y) \\ = β^{'} (α^{' *} (φ (q_{0}), ɛ), y), \\ (from Proposition 3.2) \\ = β^{'} (α^{' *} (q_{0}^{'}, ɛ), y) \\ = E ((S, α^{'}, β^{'}, q_{0}^{'})) (ɛ, y) . \end{matrix}$

Thus the result holds for |w|=0. We now assume that the result is true for all strings of length less than or equal to n, i.e., for all w ∈ X^* such that |w| ≤ n, $E ((Q, α, β, q_{0})) (w, y) = E ((S, α^{'}, β^{'}, q_{0}^{'})) (w, y), w \in X^{*}, y \in Y$ . Then for x ∈ X,

$\begin{matrix} E ((Q, α, β, q_{0})) (wx, y) \\ = β (α^{*} (q_{0}, wx), y) \\ = β (α (α^{*} (q_{0}, w), x), y) \\ = β^{'} (α^{'} ({α^{'}}^{*} (φ (q_{0}), w), x), y) \\ = β^{'} (α^{'} ({α^{'}}^{*} (q_{0}^{'}, w), x), y) \\ = β^{'} ({α^{'}}^{*} (q_{0}^{'}, wx), y) \\ = E ((S, α^{'}, β^{'}, q_{0}^{'})) (wx, y) . \end{matrix}$

Hence the result holds for |w| = n + 1.

Definition 3.7. (a) Given $(Q, α, β, q_{0}) \in A (X, Y)$ , the observability map σ is a map σ : Q → L^{X
^*} such that σ (q) = E_q ((Q, α, β, q₀)) , ∀ q ∈ Q.

(b) (Q, α, β, q₀) is called observable, if σ is one-one.

Remark 3.5. (i) Note that, σ (q₀) = E_{q
₀} ((Q, α, β, q₀)), where E_{q
₀} ((Q, α, β, q₀)) (w, y) = (β ∘ r) (w, y) = β (r (w) , y) = β (α^* (q₀, w)), ∀w ∈ X^*.

(ii) The observability of $(Q, α, β, q_{0}) \in A (X, Y)$ tells that different fuzzy behaviours are assigned to distinct states.

We close this section by introducing the following concept of minimal realization (minimal crisp deterministic fuzzy machine) for a given fuzzy behaviour.

Definition 3.8. $(Q, α, β, q_{0}) \in A (X, Y)$ is a realization for fuzzy behaviour f, if E ((Q, α, β, q₀)) = f. Further, the realization (Q, α, β, q₀) is minimal, if it is both reachable and observable.

4 Minimal realization for fuzzy behaviour

In this section, we introduce and study the concept of minimal realizations for a given fuzzy behaviour in bicategory-theoretic setup. The construction of first realization is based on Myhill Nerode’s theory while that of other is based on the derivative of given fuzzy behaviour. Finally, we show that there exists a 2-cell between both of the minimal realizations in $A$ .

Proposition 4.1. Given a fuzzy behaviour f : X^* × Y → L there exists a minimal realization in $A (X, Y)$ which realizes f.

Proof. Define a relation ∼_f on X^* by w₁ ∼ _fw₂ iff f (w₁w, y) = f (w₂w, y), for all w ∈ X^* and y ∈ Y. Then ∼_f is an equivalence relation on X^*. Now, let Q_f = X^*slash ∼ _f = {[w] _f : w ∈ X^*}, where [w] _f = {w′ ∈ X^* : w ∼ _fw′} and define the maps α_f : Q_f × X → Q_f and β_f : Q_f × Y → L such that α_f ([w] _f, x) = [wx] _f and β_f ([w] _f, y) = f (w, y). The maps α_f and β_f are well defined as for w₁, w₂ ∈ X^* such that [w₁] _f = [w₂] _f, we have $\begin{matrix} [w_{1}]_{f} = [w_{2}]_{f} & \Rightarrow & w_{1} \sim_{f} w_{2} \\ \Rightarrow & f (w_{1} w^{'}, y) = f (w_{2} w^{'}, y), \\ \forall w^{'} \in X^{*}, y \in Y \\ \Rightarrow & f (w_{1} {xw}^{'}, y) = f (w_{2} {xw}^{'}, y), \\ w^{'} \in X^{*}, x \in X, y \in Y \\ \Rightarrow & w_{1} x \sim_{f} w_{2} x \\ \Rightarrow & [w_{1} x]_{f} = [w_{2} x]_{f} \\ \Rightarrow & α_{f} ([w_{1}]_{f}, x) = α_{f} ([w_{2}]_{f}, x), \end{matrix}$ and $\begin{matrix} [w_{1}]_{f} = [w_{2}]_{f} & \Rightarrow & w_{1} \sim_{f} w_{2} \\ \Rightarrow & f (w_{1} w^{'}, y) = f (w_{2} w^{'}, y), \\ \forall w^{'} \in X^{*}, y \in Y \\ \Rightarrow & f (w_{1} ɛ, y) = f (w_{2} ɛ, y), \forall y \in Y \\ \Rightarrow & f (w_{1}, y) = f (w_{2}, y) \\ \Rightarrow & β_{f} ([w_{1}]_{f}, y) = β_{f} ([w_{2}]_{f}, y) . \end{matrix}$

Thus N_f = (Q_f, α_f, β_f, [ɛ] _f)∈ $A (X, Y)$ . Now, let w ∈ X^* and y ∈ Y. Then $\begin{matrix} E ((Q_{f}, α_{f}, β_{f}, [ɛ]_{f})) (w, y) & = & β_{f} (α_{f}^{*} ([ɛ]_{f}, w), y) \\ = & β_{f} ([ɛ w]_{f}, y) \\ = & β_{f} ([w]_{f}, y) \\ = & f (w, y), \end{matrix}$ or that, E ((Q_f, α_f, β_f, [ɛ] _f)) = f, whereby N_f is a realization for f.

Finally, to prove the minimality of realization N_f, let [w] _f ∈ Q_f. Then $r (w) = α_{f}^{*} ([ɛ]_{f}, w) = [ɛ w]_{f} = [w]_{f}$ . Thus r is onto, and so N_f is reachable. Also, let w₁, w₂ ∈ X^* such that σ ([w₁] _f) = σ ([w₂] _f). Then E_{[w₁]_f} (N_f) = E_{[w₂]_f} (N_f). Now, for all (w, y) ∈ X^* × Y, $\begin{matrix} E_{[w_{1}]_{f}} (N_{f}) = E_{[w_{2}]_{f}} (N_{f}) \\ \Rightarrow E_{[w_{1}]_{f}} (N_{f}) (w, y) = E_{[w_{2}]_{f}} (N_{f}) (w, y) \\ \Rightarrow β_{f} (α_{f}^{*} ([w_{1}]_{f}, w), y) = β_{f} (α_{f}^{*} ([w_{2}]_{f}, w), y) \\ \Rightarrow β_{f} ([w_{1} w]_{f}, y) = β_{f} ([w_{2} w]_{f}, y) \\ \Rightarrow f (w_{1} w, y) = f (w_{2} w, y) \\ \Rightarrow w_{1} \sim_{f} w_{2} \\ \Rightarrow [w_{1}]_{f} = [w_{2}]_{f}, \end{matrix}$ whereby σ : Q_f → L^{X^*×Y} is one-one. Hence N_f is minimal.

Example 4.1. Let L = [0, 1] and X^* = {0, 1, 2 . . .} = Y. Obviously, (X^*, +) is a free monoid. Define f : X^* × Y → L such that ∀x ∈ X^*, ∀ y ∈ Y, $f (x, y) = {\begin{matrix} 0 & if (x, y) = (0, 0) \\ 0.7 & otherwise . \end{matrix}$

Then it can be seen that the deterministic fuzzy automaton, which realizes f is N_f = (Q_f, δ_f, [0] , β_f), where Q_f = {[0] , [1]}, δ_f ([w] , y) = [w + y] , ∀ w ∈ X^*, ∀ y ∈ Y and for all [w] ∈ Q_f and for all y ∈ Y, $β_{f} ([w], y) = {\begin{matrix} 0 & if ([w], y) = ([0], 0) \\ 0.7 & otherwise . \end{matrix}$

Proposition 4.2. Let $(Q, α, β, q_{0}) \in A_{R (X, Y)}$ . Then there exists a unique 2-cell from (Q, α, β, q₀) to N_f = (Q_f, α_f, β_f, [ɛ] _f) in $A$ iff E ((Q, α, β, q₀)) = f.

Proof. Let $\bar{φ} : (Q, α, β, q_{0}) \to (Q_{f}, α_{f}, β_{f}, [ɛ]_{f})$ . Then from Proposition 4.1, E ((Q, α, β, q₀)) = Elinebreak (N_f) = f.

Conversely, let E ((Q, α, β, q₀)) = f and define a map $\bar{φ} : (Q, α, β, q_{0}) \to (Q_{f}, α_{f}, β_{f}, [ɛ]_{f})$ such that $\bar{φ} (q) = [w]_{f}$ , for some w ∈ X^* iff α^* (q₀, w) = q. Obviously, $\bar{φ}$ is well defined. In order to show that $\bar{φ}$ define a 2-cell it is enough to show that the diagrams in Fig. 6 commute. Now, let q ∈ Q and x ∈ X. Then $\begin{matrix} (α_{f} \circ (\bar{φ} \times X)) (q, x) & = & α_{f} (\bar{φ} (q), x) \\ = & α_{f} ([w]_{f}, x) \\ = & [wx]_{f} \\ = & \bar{φ} (α^{*} (q_{0}, wx)) \\ = & \bar{φ} (α (α^{*} (q_{0}, w), x)) \\ = & \bar{φ} (α (q, x)) \\ = & (\bar{φ} \circ α) (q, x) . \end{matrix}$

Thus $α_{f} \circ (\bar{φ} \times X) = \bar{φ} \circ α$ , or that the Square (A) in Fig. 6 commutes. Also, the commutativity of Triangle (B) in Fig. 6 follows from the fact that for all q ∈ Q and for all y ∈ Y, $(β_{f} \circ (\bar{φ} \times Y)) (q, y) \geq β_{f} ([w]_{f}, y) = f (w, y) = E ((Q, α, β, q_{0}))$ $(w, y) = β (α_{f}^{*} (q_{0}, w), y) = β (q, y)$ , i.e., (β_f∘ $(\bar{φ} \times Y)) \geq β$ . To prove the uniqueness of $\bar{φ} : (Q, α, β, q_{0}) \to (Q_{f}, α_{f}, β_{f}, [ɛ]_{f})$ , let $\bar{ψ}$ be another such 2-cell in $A$ . In order to show that $\bar{ψ} = \bar{φ}$ , we use the method of induction on the length of strings in X^*. Let w ∈ X^* such that |w|=0. Then $\bar{ψ} (q_{0}) = [ɛ]_{f} = \bar{φ} (q_{0})$ . Thus $\bar{ψ} = \bar{φ}$ holds for all states reachable from q₀ for all w ∈ X^* such that |w|=0. We now assume that $\bar{ψ} = \bar{φ}$ on all states reachable from q₀ by words of length less than or equal to n, i.e., for all w ∈ X^* such that |w| ≤ n. Then for x ∈ X such that α^* (q₀, wx) = q, $\begin{matrix} \bar{ψ} (q) & = & \bar{ψ} (α^{*} (q_{0}, wx)) \\ = & \bar{ψ} (α (α^{*} (q_{0}, w), x)) \\ = & α_{f} (\bar{ψ} (α^{*} (q_{0}, w)), x), \\ (from Proposition 3.2) \\ = & α_{f} (α_{f}^{*} (\bar{ψ} (q_{0}), w), x) \\ = & α_{f} (α_{f}^{*} (\bar{φ} (q_{0}), w), x) \\ = & α_{f} (\bar{φ} (α^{*} (q_{0}, w), x)) \\ = & \bar{φ} (α (α^{*} (q_{0}, w), x)) \\ = & \bar{φ} (α^{*} (q_{0}, wx)) \\ = & \bar{φ} (q), \end{matrix}$ whereby $\bar{ψ} = \bar{φ}$ on all states reachable from q₀ by words of length n + 1. Hence $\bar{ψ} = \bar{φ}$ .

Now, we introduce the following concept of derivative of a fuzzy behaviour.

Definition 4.1. For a given fuzzy behaviourf : X^* × Y → L, the derivative of f with respect to u ∈ X^* is a map f^u : X^* × Y → L such that f^u (v, y) = f (uv, y), for every v ∈ X^*, y ∈ Y.

For a given fuzzy behaviour f : X^* × Y → L, we put Q^f = {f^u : u ∈ X^*}.

Proposition 4.3. Given a fuzzy behaviour f : X^* × Y → L there exists a crisp deterministic fuzzy machine $N^{f} \in A (X, Y)$ whose fuzzy behaviour is f.

Proof. Let f : X^* × Y → L. Define the maps α^f : Q^f × X → Q^f and β^f : Q^f × Y → L such that α^f (f^u, x) = f^ux and β^f (f^u, y) = f^u (ɛ, y) = f (u, y). The maps α^f and β^f are well defined which can be shown as follows.

Let f^u, f^v ∈ Q^f be such that f^u = f^v, where u, v ∈ X^*. Then $\begin{matrix} f^{u} = f^{v} & \Rightarrow & f^{ux} = f^{vx} \\ \Rightarrow & α^{f} (f^{u}, x) = α^{f} (f^{v}, x), \end{matrix}$ whereby α^f is well defined. Also, for y ∈ Y, $\begin{matrix} f^{u} = f^{v} & \Rightarrow & f^{u} (ɛ, y) = f^{v} (ɛ, y) \\ \Rightarrow & β^{f} (f^{u}, y) = β^{f} (f^{v}, y), \end{matrix}$ whereby β^f is well defined.

Thus $N^{f} = (Q^{f}, α^{f}, β^{f}, f^{ɛ}) \in A (X, Y)$ . Also, by induction it is easy to verify that α^f can be extended to α^{f
^*} : Q^f × X^* → Q^f such that α^{f
^*} (f^u, w) = f^uw, for every f^u ∈ Q^f, w ∈ X^*.

Finally, to prove that the behaviour of $N^{f} \in A (X, Y)$ is f, let w ∈ X^* and y ∈ Y. Then $\begin{matrix} E (N^{f}) (w, y) & = & β^{f} (α^{f^{*}} (f^{ɛ}, w), y) \\ = & β^{f} (f^{w}, y) \\ = & f (w, y) . \end{matrix}$

Hence E (N^f) = f.

Proposition 4.4. Let $(Q, α, β, q_{0}) \in A_{R} (X, Y)$ . Then there exists a unique 2-cell from (Q, α, β, q₀) to N^f = (Q^f, α^f, β^f, f^ɛ) in A iff E (Q, α, β, q₀) = f.

Proof. Let $\bar{ψ} : (Q, α, β, q_{0}) \to (Q^{f}, α^{f}, β^{f}, f^{ɛ})$ . Then, from Lemma 2.2 and Proposition 2.2,

E ((Q, α, β, q₀)) = E (N^f) = f.

Conversely, let E ((Q, α, β, q₀)) = f. Define a map $\bar{ψ} : (Q, α, β, q_{0}) \to (Q^{f}, α^{f}, β^{f}, f^{ɛ})$ such that $\bar{ψ} (q) = f^{u}$ , for some u ∈ X^* iff α^* (q₀, u) = q for all q ∈ Q. Obviously, $\bar{ψ}$ is well defined. In order to show that $\bar{ψ}$ define a 2-cell it is enough to show that the diagrams in Figure 7 commute.

Now, let q ∈ Q and x ∈ X. Then $\begin{matrix} (α^{f} \circ (\bar{ψ} \times X)) (q, x) & = & α^{f} (\bar{ψ} (q), x) \\ = & α^{f} (f^{u}, x) \\ = & f^{ux} \\ = & \bar{ψ} (α^{*} (q_{0}, ux)) \\ = & \bar{ψ} (α (α^{*} (q_{0}, u), x)) \\ = & \bar{ψ} (α (q, x)) \\ = & (\bar{ψ} \circ α) (q, x) . \end{matrix}$

Thus $α^{f} \circ (\bar{ψ} \times X) = \bar{ψ} \circ α$ , for all (q, x) ∈ linebreakQ × X. Hence Square (A) in Fig. 7 commutes.

The commutativity of Triangle (B) in Fig. 7 follows from the fact that for all q ∈ Q and for all y ∈ Y, $\begin{matrix} (β^{f} \circ (\bar{ψ} \times Y)) (q, y) & \geq & β^{f} (\bar{ψ} (q), y) \\ = & β^{f} (f^{u}, y) \\ = & f^{u} (ɛ, y) \\ = & f (u, y) \\ = & β (q, y) . \end{matrix}$ To show the uniqueness of $\bar{ψ} : (Q, α, β, q_{0}) \to (Q^{f}, α^{f}, β^{f}, f^{ɛ})$ , let $\bar{φ} : (Q, α, β, q_{0}) \to (Q^{f}, α^{f}, β^{f}, f^{ɛ})$ be another such 2-cell. In order to show that $\bar{φ} = \bar{ψ}$ , we use method of induction on the length of the strings in X^*. Let $w \in X_{0}^{*}$ such that |w|=0. Then $\bar{φ} (q_{0}) = f^{ɛ} = \bar{ψ} (q_{0})$ , i.e., $\bar{φ} = \bar{ψ}$ holds for all states reachable from q₀ by words of length zero. We now assume that $\bar{φ} = \bar{ψ}$ on all states reachable from q₀ by words of length less than or equal to n, i.e., for all string w such that |w| ≤ n, so for any x ∈ X such that α^* (q₀, wx) = q, we have $\begin{matrix} \bar{φ} (q) & = & φ (α^{*} (q_{0}, wx)) \\ = & \bar{φ} (α (α^{*} (q_{0}, w), x)) \\ = & α^{f} (\bar{φ} (α^{*} (q_{0}, w), x)), \\ (from Proposition 3) \\ = & α^{f} (α^{f *} (\bar{φ} (q_{0}), w), x)) \\ = & α^{f} (α^{f *} (\bar{ψ} (q_{0}), w), x)) \\ = & \bar{ψ} (α (α^{*} (q_{0}, w), x)) \\ = & \bar{ψ} (α^{*} (q_{0}, wx)) \\ = & \bar{ψ} (q), \end{matrix}$ whereby $\bar{φ} = \bar{ψ}$ on all states reachable from q₀ by words of length n + 1. Hence $\bar{φ} = \bar{ψ}$ .

Proposition 4.5. For a given fuzzy behaviour f : X^* × Y → L, there exists a unique 2-cell from N_f = (Q_f, α_f, β_f, [ɛ] _f) to N^f = (Q^f, α^f, β^f, f^ɛ) in A.

Proof. Follows from Proposition 3.4.

5 Conclusion

In this paper, we have tried to introduce and study the concepts of two minimal realizations for a given fuzzy behaviour in bicategory theoretic setup. Interestingly, we have shown that there exist a unique 2-cell in bicategory $A$ between both the minimal realizations. Here, we have worked with the crisp deterministic fuzzy automata, in which the fuzziness is due to the consideration of fuzzy output map, while such works for fuzzy automata with fuzzy transition maps is still to be done. We will try to handle it in near future.

Acknowledgments

The authors are greatly indebted to the the referees for their valuable observations and suggestions for improving the paper.

References

Pierce

B.C.

, Basic Category Theory for Computer Scientists, The MIT Press, Cambridge, 1991.

Qiu

, Automata theory based on complete residuated latticevalued logic(I), Science in China 44 (2001), 419–429.

Qiu

, Automata theory based on complete residuated latticevalued logic(II), Science in China 45 (2002), 442–452.

Santos

E.S.

, Max-product machines, Journal of Mathematical Analysis and Applications 37 (1972), 677–686.

Lei

and Li

Y.M.

, Minimization of states in automata theory based on finite lattice-ordered monoids, Information Sciences 177 (2007), 1413–1421.

Kumbhojkar

H.V.

and Chaudhri

S.R.

, On proper fuzzification of fuzzy finite state machines, International Journal of Fuzzy Mathematics 4 (2008), 1019–1027.

Xing

, Qiu

, Liu

and Fan

, Equivalence in automata theory based on complete residuated lattice-valued logic, Fuzzy Sets and Systems 158 (2007), 1407–1422.

Xing

and Qiu

, Automata theory based on complete residuated lattice-valued logic: A categorical approach, Fuzzy Sets and Systems 160 (2009), 2416–2428.

Goguen

J.A.

, L-fuzzy sets, Journal of Mathematical Analysis and Applications 18 (1967), 145–174.

10.

Goguen

J.A.

, Minimal realization of machines in closed categories, Bulletin of American Mathematical Society 78 (1972), 777–783.

11.

Adamek

and Trnkova

, Automata and Algebras in Categories, Kluwer, 1990.

12.

Bénabou

, Introduction to bicategories, Reports of the Midwest Category Seminar, Lecture Notes in Mathematics 47 (1967), 1–77.

13.

Ignjatović

, Ćirić

and Bogdanović

, Determinization of fuzzy automata with membership values in complete residuated lattices, Information Sciences 178 (2008), 164–180.

14.

Ignjatović

, Ćirić

, Bogdanović

and Petković

, Myhill- Nerode type theory for fuzzy languages and automata, Fuzzy Sets and Systems 161 (2010), 1288–1324.

15.

Močkoř

, A category of fuzzy automata, International Journal of General Systems 20 (1991), 73–82.

16.

Močkoř

, Fuzzy and non-deterministic automata, Soft Computing 3 (1999), 221–226.

17.

Močkoř

, Semigroup homomorphisms and fuzzy automata, Soft Computing 6 (2002), 423–427.

18.

Mordeson

J.N.

and Malik

D.S.

, Fuzzy Automata and Languages: Theory and Applications, Chapman and Hall/CRC. London/Boca Raton, 2000.

19.

Abolpour

and Zahedi

M.M.

, Isomorphism between two BLgeneral fuzzy automata, Soft Computing 16 (2012), 103–118.

20.

Peeva

K.G.

, Behaviour, reduction and minimization of finite L-automata 28 (1988), 171–181.

21.

Peeva

, Finite L-fuzzy machines, Fuzzy Sets and Systems 141 (2004), 415–437.

22.

Peeva

and Zahariev

Z.l.

, Computing behavior of finite fuzzy machines-Algorithm and its application to reduction and minimization 178 (2008), 4152–4165.

23.

Zadeh

L.A.

, Fuzzy sets, Information and Control 8 (1965), 338–353.

24.

Arbib

M.A.

and Manes

E.G.

, Machines in a category: An expository introduction, SIAM Review 16 (1974), 163–192.

25.

Arbib

M.A.

and Manes

E.G.

, Basic concepts of category theory applicable to computation and control, Proc First International Symposium AMherst MA, Lecture Notes in Computer Science 25 (1975), 2–41.

26.

Arbib

M.A.

and Manes

E.G.

, A categorist’s view of automata and systems, Proc First International Symposium AMherst MA, Lecture Notes in Computer Science 25 (1975), 62–78.

27.

Barr

and Wells

, Category Theory for Computing Science, Prentice-Hall International (UK) Limited, Englewood Cliffs, NJ, 1996.

28.

Doostfatemeh

and Kremer

S.C.

, New Directions in Fuzzy Automata 38 (2005), 175–214.

29.

Basak

N.C.

and Gupta

, On quotient machines of a fuzzy automaton and the minimal machine, Fuzzy Sets and Systems 125 (2002), 223–229.

30.

Bělohlávek

, Determinism and fuzzy automata, Information Sciences 143 (2002), 205–209.

31.

Rosebrugh

, Sabadini

and Walters

R.F.C.

, Minimal realization in bicategories of automata, Mathematical Structures in Computer Science 8 (1998), 93–116.

32.

Eilenberg

, Automata, Languages and Machines: A, Academic Press, New York, 1974.

33.

Tiwari

S.P.

, Yadav

V.K.

and Singh

A.K.

, Construction of a minimal realization and monoid for a fuzzy language: A categorical approach, Journal of Applied Mathematics and Computing 47 (2014), 401–416.

34.

Petković

, Congruences and homomorphisms of fuzzy automata, Fuzzy Sets and Systems 157 (2006), 444–458.

35.

Trnková

, Automata and categories, Lecture Notes in Computer Science 32 (1975), 160–166.

36.

Trnková

, Relational automata in a category and their languages, Lecture Notes in Computer Science 56 (1977), 340–355.

37.

Cheng

and Mo

, Minimization algorithm of fuzzy finite automata, Fuzzy Sets and Systems 141 (2004), 439–448.

38.

Wee

W.G.

, On generalizations of adaptive algorithm and application of the fuzzy sets concept to pattern classification, Ph. D. Thesis, Purdue University, Lafayette, IN, 1967.

39.

Lihua

and Qiu

, Automata theory based on complete residuated lattice-valued logic: Reduction and minimization, Fuzzy Sets and Systems 161 (2010), 1635–1656.

40.

Kim

Y.H.

, Kim

J.G.

and Cho

S.J.

, Products of T-generalized state machines and T-generalized transformation semigroups, Fuzzy Sets and Systems 93 (1998), 87–97.

41.

and Pedrycz

, Fuzzy finite automata and fuzzy regular expressions with membership values in lattice-ordered monoids, Fuzzy Sets and Systems 156 (2005), 68–92.

42.

and Pedrycz

, The equivalence between fuzzy Mealy and fuzzy Moore machines, Soft Computing 10 (2006), 953–959.

43.

and Pedrycz

, Minimization of lattice finite automata and its application to the decomposition of lattice languages, Fuzzy Sets and Systems 158 (2007), 1423–1436.

44.

Y.M.

, A categorical approach to lattice-valued fuzzy automata, Fuzzy Sets and Systems 156 (2006), 855–864.

45.

Jančić

and Ćirić

, Brzozowski type determinization for fuzzy automata, Fuzzy Sets and Systems 249 (2014), 73–82.