# A General Categorical Framework of Minimal Realization Theory for a Fuzzy Multiset Language

Authors: Swati Yadav; S. P. Tiwari
Journal: Mathematical Problems in Engineering
 (2022)

---

## Abstract

This paper is to study the minimal realization theory for a fuzzy multiset language in the framework of category theory, which has already provided the tools and techniques for the advancement of several features of theoretical computer science. Specifically, by using the well-known categorical concepts, it is shown herein that there is a minimal realization (called the Nerode realization) for each fuzzy multiset language, and all minimal realizations for a given fuzzy multiset language are isomorphic to it.


---

## Body

## 1. Introduction

Multiset, in contrast to classical set, allows repetition of any object, and the number of repetitions of an object is called its multiplicity (cf. Blizard [1]). In other words, a multiset is a set with multiplicities associated with its elements in the form of natural numbers. The multiset theory or theory of bags has been established by Cerf and his coauthors [2] as an extension of classical set in 1971, which is further advanced by Petrson [3], Yager [4] and Blizard [1]. The theory of bag developed by Yager [4] and Blizard [1], explored in the fuzzy sense by Chakrabarty et al. in [5, 6] under the notion of fuzzy shadows and fuzzy bags. The multiset theory has been shown to be useful in, chemical programming [7], parallel processing [2], mathematics [8–10], parallel processing [2], data analysis [11], parallel programming [12], neural network [13], information system [14], decision making [15], decipherability of codes and information transmission [16–21], DNA computing [22], and many more for details see references in [23].An automaton (cf. Hopcroft and Ullman [24], Eilenberg [25]), a well-known model of computation, has been started to generalized using fuzzy sets theory (c.f., Zadeh [26]), by Wee [27], Wee and Fu [28], Lee and Zadeh [29], Santos [30], and Kumbhojkar & Chaudhri [31] to introduce the concept of a fuzzy automaton and fuzzy languages, which are further studied algebraically by Maliket al. [32], and Mordeson and Malik [33] under the notion of fuzzy finite machines. Wechler [34], initiated the study of fuzzy automata and fuzzy languages taking membership values in structured sets. Following Wechler [34] initiative, fuzzy automata and fuzzy languages having structure for membership values of a fuzzy set in arbitrary set [35], bipointed sets [35, 36], poset [37, 38], locally finite complete lattice [39], lattices [40, 41], lattice order monoid [42, 43], complete residuated lattices [35, 44–46], have been studied in different directions from theoretical and application point of view and became an important tool for reducing the gap between formal languages and natural languages.The multiset theory is also in closed proximity with the theory of computation. Formal power series, Petri nets, databases, logics, formal language theory, and concurrency are some areas in computer science where multiset theory frequently appears. The multiset languages (commutative languages) are sets with their objects as multisets. Crespi-Reghizzi and Mandrioli [47] used multiset grammars as a device for a formalism for generating multiset language rather than strings, and shown equivalent to vector addition systems and Petri nets model of parallel processing. Multiset languages can be characterized in terms of multiset grammar as well as multiset automata [48, 49]. The multiset language and multiset grammar have been shown helpful in membrane computing [23, 50]. The Mealy multiset automata with output have been discussed in [51]. In contrast, multiset pushdown automata and multiset languages have been studied in [52] and closure properties of multiset language families have been studied in [53].The multiset theory have been also shown to have successful application in the advancement of the theory of fuzzy automata. The recent contribution with application of multiset theory in fuzzy automata theory is due to Wang et al. [54], the authors introduced the notion of fuzzy multiset finite automata as a generalized version of multiset finite automata and studied its relationship with fuzzy multiset regular grammars. In [54], it has been pointed out that fuzzy multiset language produced by a fuzzy multiset regular grammar can be recognized by a fuzzy multiset finite automaton and vice-versa. Some operations on fuzzy multiset languages, along with closure properties of the family of fuzzy multiset finite automata languages under these operations, have also been studied in [54]. Martinek, in [55] reviewed fuzzy multiset finite automata and discussed determinism, languages, and pumping lemma, whereas in [56] the author studied some closure properties of fuzzy multiset regular languages.The deterministic automaton with a fuzzy set of final states also known as crisp deterministic fuzzy automata (cdfa) is a well-known concept studied by [39, 40, 57]. Such automaton has been considered useful due to fact that (i) some fuzzy automaton accepts a given fuzzy language iff some crisp deterministic fuzzy automaton accept the same (cf. [39, 40]), and (ii) the Nerode automaton corresponding to a fuzzy automaton is a cdfa equivalent to same fuzzy automaton (cf. [57]). The deterministic fuzzy multiset finite automata and fuzzy multiset finite automata have been shown equivalent potential in terms of acceptance of a fuzzy multiset language by Tiwari et al. [58] and in addition minimal realization of a fuzzy multiset language have also been studied by them through the right congruence relation.The minimization problem, i.e., given a behavior, how one can design a machine with the minimal number of states which recognize the given behavior, is a fundamental issue in classical automata theory and is, no doubt, a significant problem in fuzzy automata theory. Several contributions with different approaches have been reported to handle this issue (cf. [33, 35–38, 40–42, 44–46, 59–61]). Myhill-Nerode’s theory [62, 63], use the congruences on free monoid to study deterministic automata and formal languages. These congruences were found to play a critical role in minimal deterministic automaton construction recognizing a given language. The Myhill-Nerode’s theory has also been successfully addressed the minimal realization problem of fuzzy languages [33, 35, 42]. The minimization idea of Lei and Li [42] or Mordeson and malik [33] for deterministic fuzzy recognizers take in account the reduction of the number of states of a fuzzy automaton by merging indistinguishable states, similar to the algorithm for minimization of deterministic automata. But, in [35], it has been pointed out that “minimization used in [33, 42] does not mean the usual construction of the minimal one in the set of all fuzzy automata recognizing a given fuzzy language, but just the procedure of computing and merging indistinguishable states which do not necessarily result in a minimal fuzzy automaton.” Further, in [35] as well as in [33], the derivative of fuzzy languages plays a key role in the minimization procedure. The minimization problem of fuzzy multiset automata and fuzzy multiset languages having membership values in distributive lattices have been studied by Tiwari et al. [58], using the right congruence relation, a key concept of Myhill-Nerode theory, and concept of derivative of a fuzzy multiset language. Wang and Li [64] also studied the minimization problem using the right congruence relation defined on the state-set of deterministic lattice multiset automata and presented an efficient minimization algorithm where unreachable states were removed in the process of minimization.The category-theoretic tools and techniques have been used in the advancement of several features of theoretical computer science; specifically, in automata theory, the application of the categorical approach can be seen in (cf. [25, 59, 65–71]). While in the case of fuzzy automata and fuzzy languages, category-theoretic studies were reported in [36–38, 44–46, 61, 72–75]. Among these works, Močkǒr in [74] provide a method of reduction of fuzzy automata, which is analogical to a method of minimalization of classical Moore type automata. The minimal realization of classical automata and languages through a categorical approach has been carried out in [59, 65–67, 71], while minimization of fuzzy automata and fuzzy languages has been studied in [36–38, 44–46, 61, 72–75].The recent contribution to the study of fuzzy multiset automata and fuzzy multiset languages is due to Sharma et al. [76, 77], Wang and Li [64], Pal and Tiwari [78], and Tiwari et al. [79]. The authors in [76], studied algebraic aspects of fuzzy multiset automata like fuzzy multiset transformation semigroup and coverings of fuzzy multiset finite automata, while authors in [77] studied fuzzy multiset regular languages and proved pumping lemma and use it to point out mandatory condition for fuzzy multiset languages being non-constant. In [64], the method of transformation of lattice valued nondeterministic multiset automata into deterministic lattice valued multiset automata (DLMA), and then its minimization algorithm; some lattice-valued regular multiset languages accepted by some special minimal DLMA the lattice-valued regular multiset language decomposition by some simple were studied with structure for truth values of a fuzzy set as distributive lattices. In Pal and Tiwari [78], minimal realization for an L-valued multiset language is studied through Brzozowski’s algorithm; the authors show that the deterministic L-valued multiset automaton obtained by use of Brzozowski’s algorithm is minimal.We have gone through the cited literature related to the study of fuzzy multiset automata and fuzzy multiset languages and observed that(i)
all cited work associated with the study of fuzzy multiset automata and fuzzy multiset languages uses either0,1, or distributive lattices as the membership structure for fuzzy sets;(ii)
the minimal realization for given fuzzy multiset languages and minimization of fuzzy multiset automata studied so for uses (i) concept of Myhill-Nerode equivalence relation defined either on input multiset [58, 64], or through defining equivalence relation on state set of deterministic lattice valued multiset automata and removal of unreachable states [64], (ii) derivative of fuzzy languages [58], (iii) Brzozowski’s minimization algorithm [78];(iii)
except Pal and Tiwari [78], no work has been reported for studying fuzzy multiset automata and fuzzy multiset languages via categorical concept; while, the categorical approach has been shown to be helpful in the study of several aspects of classical automata and languages, as well as fuzzy automata and fuzzy languages, as mentioned above.Keeping the above-mentioned points in account, in the present work, instead of taking0,1 or distributive lattice, we have taken arbitrary sets with two distinguished elements 0 and 1 for structure of truth values of fuzzy sets as in [35] and provide a general categorical framework for minimal realization theory for a fuzzy multiset language to enrich the fuzzy multiset automata theory.The substance of the paper is as follows. In Section2, we have presented the fundamental concepts and notions related to category theory, multiset theory, fuzzy multiset automata theory, and fuzzy multiset languages, which we need in subsequent sections. In Section 3, for a fixed input alphabet Σ0, we define categories CDFMAΣ0 of crisp deterministic fuzzy multiset automata and their homomorphisms having membership values in L˜∈LSET, and then characterize the reachability and coreachability map of M∈CDFMAΣ0 as a morphism of CDFMAΣ0. In Section 4, we have provided Myhill-Nerode theory base construction for minimal realization for a given fuzzy multiset language in our sense. In Section 5, we have define a category MDYNΣ0⊕ of MΣ0⊕-dynamics and define a forgetful functor U:MDYNΣ0⊕⟶LSET having both left as well as right adjoint and introduce concept of free and cofree MΣ0⊕-dynamics. A different view of run map, reachability map and coreachability map introduced in previous section facilitate us to characterized them as a morphism of category MDYNΣ0⊕. In Section 6, we have shown that the free and cofree MΣ0⊕-dynamics are free and cofree with respect to the forgetful functor U introduced in the previous section. Finally, in Section 7, we have defined the response map of a crisp deterministic fuzzy multiset automaton. We show that a fuzzy multiset language can be fully characterized in terms of a response map. We have provided minimal realization of response map in category MDYNΣ0⊕ and conclude that for a given fuzzy multiset language, its all minimal realizations are isomorphic to its Nerode realization.


## 2. Preliminaries

In this section, we recall those concepts from category theory, multiset set theory and multiset automata theory which we need in subsequent sections. We begin with following.


### 2.1. Category Theoretic Concepts

The categorical concepts used by us are recalled here from Adámek, Herrlich, and Strecker [65], Arbib and Manes [67], and Mac Lane [80].Definition 1.
[65, 67, 68, 80] A category T consist of:(i)
a objects class (orT-objects);(ii)
for every pairX and Y of T-objects, a class TX,Y, of morphisms (or T-morphisms) with domain X and codomain Y; f∈TX,Y is written as f:X⟶Y or X⟶fY;(iii)
for eachT-object X, a morphism idX:X⟶X, called the identity morphism on X;(iv)
forT-morphisms h:X⟶Y and k:Y⟶Z, a T-morphism k°h:X⟶Z, called composition of h and k;
Such that:(a)
for allT-morphisms h:X⟶Y,k:Y⟶Z, and g:Z⟶D,g°k°h=g°k°h,(b)
for allT-morphisms h:X⟶Y,idY°h=h and h°idX=h,
Hold.
We shall represent byT, the class of object of a category T.Definition 2.
[65, 67, 68, 80] A category S is said to be a subcategory of a category T, if(i)
every object ofS is also an object of T;(ii)
∀ objects X and Y of S, S X,Y⊆TX,Y; and(iii)
S has the same composition morphisms as inT.(iv)
S has identity morphisms same as in that ofT.Definition 3.
[65, 67, 68, 80] Let T and S be two categories and F:T⟶S be a map which send each X∈T to a FX∈S and each morphism f:X⟶Y in T to a morphism Ff:FX⟶FY of S, then F is called functor provided(i)
for allT-morphisms f:X⟶Y and g:Y⟶Z,Fg°f=Fg°Ff;(ii)
for allX∈T,FidX=idFX.Definition 4.
[65, 67, 68, 80] Let T and S be categories, G:T⟶S be a functor, and Y be a S-object, then G is said to have a left adjoint, if for each T-object X, ∃ a pair X,η, where η:Y⟶GX is a morphism of S, such that for any object X′ of T, and any morphism f:Y⟶GX′ of S, ∃ a unique morphism ψ:X⟶X′ of T, which make diagram of Figure 1 commutes.Figure 1
Diagram for left adjoint.Definition 5.
[65, 67, 68, 80] Let T and S be categories. Let G:T⟶S be any functor, and Y be an object of S. We say that a pair X,η, where X is an object of T and η:Y⟶GX is a morphism of S, is free over S with respect to G, just in case η:Y⟶GX has the couniversal property that given any morphism f:Y⟶GX′ with X′ any T-object, there exists a unique T-morphism ψ:X⟶X′ such that diagram in Figure 1 commutes. We call η as the inclusion of generators and the unique ψ such that diagram in Figure 1 commute as T-morphic extension of f with respect to G.Definition 6.
[65, 67, 68, 80] Let T and S be categories, and F:T⟶S be a functor, and Y be a S-object, then F has right adjoint, if for each T-object X, there exists a pair X,ε, where ε:FX⟶Y is a S-morphism such that for any T-object X′ and any S-morphism f:FX′⟶Y, there exists a unique T-morphism ψ:X′⟶X such that diagram in Figure 2 commutes.Figure 2
Diagram for right adjoint.Definition 7.
[65, 67, 68, 80] Let T and S be categories, and F:T⟶S be a functor, and Y be a S-object. We say that a pair X,ε, where X is an object of T and ε:FX⟶Y is a morphism of S, is cofree over S with respect to F, just in case η:Y⟶FX has the universal property that given any morphism f:FX′⟶X with X′ any T-object, there exists a unique T-morphism ψ:X′⟶X such that diagram in Figure 2 commutes.


### 2.2. Multiset Concepts

Here we recall those concepts of multiset which we use in this paper. These standard concepts of multiset can be found in literature (cf. [1, 48, 54] for details).Definition 8.
[54, 78] If Σ is a finite alphabet, then α:Σ⟶N is a multiset over Σ, where N denotes the set of natural numbers including 0. The α norm of Σ is defined by α=Σx∈Σαx.
We shall denote byΣ⊕, the set of all multisets over Σ. The multiset 0Σ∈Σ⊕ is defined by 0Σx=0,∀x∈Σ. For y∈Σ, we shall denote by y, a singleton multiset, and is defined by(1)<y>x=1,ify=x,0,ify≠x.
∀a∈Σ. For a given set A, let A¯=<x>:x∈A. Assumed Σ=x,y,z, the multiset α=1/x,2/y,0/z can be denoted by x>⊕<y>⊕<z.
For two multisetsα1,α2∈Σ⊕, the operations inclusion ⊆, addition ⊕ and difference ⊖ are defined as follows:(i)
α1⊆α2 if α1x≤α2x;(ii)
α1⊕α2x=α1x+α2x; and(iii)
α1⊖α2x=max0,α1x−α2x;
∀x∈Σ. Furthermore, α1⊂α2 if α1⊆α2 and α1≠α2. Also, for A,B⊆Σ⊕, A⊕B=∪α1⊕α2:α∈A,α2∈B.
Obviously,Σ⊕ is a commutative monoid with identity element 0Σ with respect to ⊕.


### 2.3. Multiset Automata

In this section we recall some concepts related to multiset automata which we need for completeness of the paper. These concepts can be found in [54, 55, 58, 64, 78].Definition 9.
[54, 55, 58, 64, 78] A multiset automaton MA is a 5-tuple ℳ=Q,Σ,δ,q0,F, where(i)
Q and Σ are nonempty sets called the state-set and input-set, respectively;(ii)
δ:Q×Σ⊕⟶2Q is a map called transition map;(iii)
q0∈Q is called the initial state; and(iv)
F⊆Q is called the set of final states.
ℳ is called multiset finite automaton if Q is finite.
A configuration of a MA,ℳ is a pair p,α, where p and α denote current state and current multiset, respectively. The transition in a multiset automaton are described with the help of configurations. The transition from configuration p,α leads to configuration q,β if there exists a multiset γ∈Σ⊕ with γ⊆α,q∈δp,γ and β=α⊖γ, and is denoted by p,α⟶q,β. We shall denote by ⟶∗, the reflexive and transitive closure of this operation.Definition 10.
[64, 78] Let ℳ=Q,Σ,δ,q0,F be a MA. Then ℳ is said to be deterministic multiset automaton DMFA if δp,α≤1,∀p∈Q and ∀α∈Σ⊕.
Next, we recall the concept of anL-valued multiset automaton defined over distributive lattice L from [64].Definition 11.
[64] An L-valued multiset automaton LMA is a 5-tuple ℳ=Q,Σ,δ,I,τ, where(i)
Q and Σ are nonempty sets called the state-set and input-set, respectively;(ii)
δ:Q×Σ⊕×Q⟶L is a map called transition map;(iii)
I:Q⟶L is a map called the L-valued set of initial states; and(iv)
τ:Q⟶L is a map called the L-valued set of final states.
ℳ is called L-valued multiset finite automaton if Q is finite.
A configuration ofL-valued multiset automaton ℳ is a pair p,α, where p and α denote current state and current multiset, respectively. The transitions in an L-valued multiset automaton are described with the help of configurations. The transition from configuration p,α leads to configuration q,β with membership value k∈0,1 if there exists a multiset γ∈Σ⊕ with γ⊆α,δp,γ,q=k and β=α⊖γ and is denoted by p,α⟶kq,β.
⟶k′∗ denote the reflexive and transitive closure of ⟶k′, i.e., for p,α,q,β∈Q×Σ⊕, p,α⟶k′∗q,β, if for some n≥0, there exists n+1 states q0,…,qn and n+1 multisets α0,…,αn such that q0=p,qn=p′,α0=α,αn=β and qi,αi⟶kiqi+1,αi+1,∀i=0,…,n−1, where k′=k0∧k1∧…∧kn−1.” Now, we define(2)μℳp1,α⟶∗p2,β=∨k′:p,α⟶∗p′,β,μℳp1,α⟶∗p2,α=1,ifp1=p2,0,ifp1≠p2.Example 1.
[58] Let ℳ=Q,Σ,δ,I,τ be an LMA, where Q=q1,q2,q3,q4,Σ=a1,a2,a3, and the L-valued transition function is given as under:(3)δq1,<a2>,q3=0.6,δq3,<a2>⊕<a3>,q4=0.7,δq4,<a1>,q2=0.9,δq1,<a2>⊕<a3>,q3=0.4,δq3,<a2>,q4=0.5.
Ifα=<a1>⊕<a2>⊕<a2>⊕<a3> and β=0Σ. Then the transition steps q1,α⟶∗q2,β are as follows:(i)
q1,<a1>⊕<a2>⊕<a2>⊕<a3>⟶0.6q3,<a1>⊕<a2>⊕<a3>⟶0.7q4,<a1>⟶0.9q2,0Σ,(ii)
q1,<a1>⊕<a2>⊕<a2>⊕<a3>⟶0.4q3,<a1>⊕<a2>⟶0.5q4,<a1>⟶0.9q2,0Σ.
Thus(4)μℳq1,α⟶∗q2,β=∨0.6∧0.7∧0.9,0.4∧0.5∧0.9=∨0.6,0.4=0.6.Definition 12.
[64, 78](i)
For a given setΣ, an L-valued multiset language is a map f:Σ⊕⟶L.(ii)
AnL-valued multiset language f:Σ⊕⟶L is accepted by an LMA ℳ=Q,Σ,δ,I,τ if(5)fα=∨Iq∧μℳq,α⟶∗p,0Σ∧τp:q,p∈Q.
∀α∈Σ⊕. Further, an L-valued multiset language f:Σ⊕⟶L is called regular if there exists a finite LMAℳ such that f=fℳ.
Also,L-valued multiset language f, accepted by an LMAℳ, is denoted by fℳ in [64, 78].


### 2.4. Bipointed Set

Here, we recall the concept of bipointed set from [35], where fuzzy sets were taken their membership values in a structure L˜=L,0,1, where L is an arbitrary set, and 0 and 1 are two distinguished elements of L, and this structure were used to take crisp languages into consideration. In [35], no other conditions were imposed on L. In this paper, fuzzy sets will take their membership in a bipointed set L˜ in sense of [35]. A more generalized view of bipointed set has been given in [36], and it is pointed out there that the concept of bipointed set can be viewed as generlization of the notion of pointed set in [80].Definition 13.
[36] A bipointed set is a 3-tuple L˜=L,a,b, where L is an arbitrary set and a, b are two distinguished elements of L. A homomorphism between two bipointed sets L,a,b and L′,a′,b′ is a map f:L⟶L′ such that fa=a′ and fb=b′.Proposition 1.
[36] The bipointed sets and their homomorphisms form a category denoted by BSET.LetB be any arbitrary set, we identifed it as a bipointed set B˜=B′,0,1, where B′=B⊎0⊎1. It is worth to note that, the class of bipointed sets mentioned above and their morphism also forms a category, which we denote LSET. Obviously, LSET is a subcategory of BSET. Note that 1˜=0,0,1,0,1.From now onward, throughout this paper,L˜ stand for a bipointed set. For a nonempty set U, A:U⟶L˜ is called a fuzzy set over U and L˜U denotes all fuzzy subsets of a set U. The kernel of map f:U⟶V, denoted as kerf, and is defined by kerf=u,v∈U×U:fu=fv, which is an equivalence relation on U. The set U/R=u:u∈U is called the quotient set of U with respect to the equivalence relation R and its cardinality is called the index of R. The image of f, is defined as Imf=fu:u∈U which is a subset of V.


## 2.1. Category Theoretic Concepts

The categorical concepts used by us are recalled here from Adámek, Herrlich, and Strecker [65], Arbib and Manes [67], and Mac Lane [80].Definition 1.
[65, 67, 68, 80] A category T consist of:(i)
a objects class (orT-objects);(ii)
for every pairX and Y of T-objects, a class TX,Y, of morphisms (or T-morphisms) with domain X and codomain Y; f∈TX,Y is written as f:X⟶Y or X⟶fY;(iii)
for eachT-object X, a morphism idX:X⟶X, called the identity morphism on X;(iv)
forT-morphisms h:X⟶Y and k:Y⟶Z, a T-morphism k°h:X⟶Z, called composition of h and k;
Such that:(a)
for allT-morphisms h:X⟶Y,k:Y⟶Z, and g:Z⟶D,g°k°h=g°k°h,(b)
for allT-morphisms h:X⟶Y,idY°h=h and h°idX=h,
Hold.
We shall represent byT, the class of object of a category T.Definition 2.
[65, 67, 68, 80] A category S is said to be a subcategory of a category T, if(i)
every object ofS is also an object of T;(ii)
∀ objects X and Y of S, S X,Y⊆TX,Y; and(iii)
S has the same composition morphisms as inT.(iv)
S has identity morphisms same as in that ofT.Definition 3.
[65, 67, 68, 80] Let T and S be two categories and F:T⟶S be a map which send each X∈T to a FX∈S and each morphism f:X⟶Y in T to a morphism Ff:FX⟶FY of S, then F is called functor provided(i)
for allT-morphisms f:X⟶Y and g:Y⟶Z,Fg°f=Fg°Ff;(ii)
for allX∈T,FidX=idFX.Definition 4.
[65, 67, 68, 80] Let T and S be categories, G:T⟶S be a functor, and Y be a S-object, then G is said to have a left adjoint, if for each T-object X, ∃ a pair X,η, where η:Y⟶GX is a morphism of S, such that for any object X′ of T, and any morphism f:Y⟶GX′ of S, ∃ a unique morphism ψ:X⟶X′ of T, which make diagram of Figure 1 commutes.Figure 1
Diagram for left adjoint.Definition 5.
[65, 67, 68, 80] Let T and S be categories. Let G:T⟶S be any functor, and Y be an object of S. We say that a pair X,η, where X is an object of T and η:Y⟶GX is a morphism of S, is free over S with respect to G, just in case η:Y⟶GX has the couniversal property that given any morphism f:Y⟶GX′ with X′ any T-object, there exists a unique T-morphism ψ:X⟶X′ such that diagram in Figure 1 commutes. We call η as the inclusion of generators and the unique ψ such that diagram in Figure 1 commute as T-morphic extension of f with respect to G.Definition 6.
[65, 67, 68, 80] Let T and S be categories, and F:T⟶S be a functor, and Y be a S-object, then F has right adjoint, if for each T-object X, there exists a pair X,ε, where ε:FX⟶Y is a S-morphism such that for any T-object X′ and any S-morphism f:FX′⟶Y, there exists a unique T-morphism ψ:X′⟶X such that diagram in Figure 2 commutes.Figure 2
Diagram for right adjoint.Definition 7.
[65, 67, 68, 80] Let T and S be categories, and F:T⟶S be a functor, and Y be a S-object. We say that a pair X,ε, where X is an object of T and ε:FX⟶Y is a morphism of S, is cofree over S with respect to F, just in case η:Y⟶FX has the universal property that given any morphism f:FX′⟶X with X′ any T-object, there exists a unique T-morphism ψ:X′⟶X such that diagram in Figure 2 commutes.


## 2.2. Multiset Concepts

Here we recall those concepts of multiset which we use in this paper. These standard concepts of multiset can be found in literature (cf. [1, 48, 54] for details).Definition 8.
[54, 78] If Σ is a finite alphabet, then α:Σ⟶N is a multiset over Σ, where N denotes the set of natural numbers including 0. The α norm of Σ is defined by α=Σx∈Σαx.
We shall denote byΣ⊕, the set of all multisets over Σ. The multiset 0Σ∈Σ⊕ is defined by 0Σx=0,∀x∈Σ. For y∈Σ, we shall denote by y, a singleton multiset, and is defined by(1)<y>x=1,ify=x,0,ify≠x.
∀a∈Σ. For a given set A, let A¯=<x>:x∈A. Assumed Σ=x,y,z, the multiset α=1/x,2/y,0/z can be denoted by x>⊕<y>⊕<z.
For two multisetsα1,α2∈Σ⊕, the operations inclusion ⊆, addition ⊕ and difference ⊖ are defined as follows:(i)
α1⊆α2 if α1x≤α2x;(ii)
α1⊕α2x=α1x+α2x; and(iii)
α1⊖α2x=max0,α1x−α2x;
∀x∈Σ. Furthermore, α1⊂α2 if α1⊆α2 and α1≠α2. Also, for A,B⊆Σ⊕, A⊕B=∪α1⊕α2:α∈A,α2∈B.
Obviously,Σ⊕ is a commutative monoid with identity element 0Σ with respect to ⊕.


## 2.3. Multiset Automata

In this section we recall some concepts related to multiset automata which we need for completeness of the paper. These concepts can be found in [54, 55, 58, 64, 78].Definition 9.
[54, 55, 58, 64, 78] A multiset automaton MA is a 5-tuple ℳ=Q,Σ,δ,q0,F, where(i)
Q and Σ are nonempty sets called the state-set and input-set, respectively;(ii)
δ:Q×Σ⊕⟶2Q is a map called transition map;(iii)
q0∈Q is called the initial state; and(iv)
F⊆Q is called the set of final states.
ℳ is called multiset finite automaton if Q is finite.
A configuration of a MA,ℳ is a pair p,α, where p and α denote current state and current multiset, respectively. The transition in a multiset automaton are described with the help of configurations. The transition from configuration p,α leads to configuration q,β if there exists a multiset γ∈Σ⊕ with γ⊆α,q∈δp,γ and β=α⊖γ, and is denoted by p,α⟶q,β. We shall denote by ⟶∗, the reflexive and transitive closure of this operation.Definition 10.
[64, 78] Let ℳ=Q,Σ,δ,q0,F be a MA. Then ℳ is said to be deterministic multiset automaton DMFA if δp,α≤1,∀p∈Q and ∀α∈Σ⊕.
Next, we recall the concept of anL-valued multiset automaton defined over distributive lattice L from [64].Definition 11.
[64] An L-valued multiset automaton LMA is a 5-tuple ℳ=Q,Σ,δ,I,τ, where(i)
Q and Σ are nonempty sets called the state-set and input-set, respectively;(ii)
δ:Q×Σ⊕×Q⟶L is a map called transition map;(iii)
I:Q⟶L is a map called the L-valued set of initial states; and(iv)
τ:Q⟶L is a map called the L-valued set of final states.
ℳ is called L-valued multiset finite automaton if Q is finite.
A configuration ofL-valued multiset automaton ℳ is a pair p,α, where p and α denote current state and current multiset, respectively. The transitions in an L-valued multiset automaton are described with the help of configurations. The transition from configuration p,α leads to configuration q,β with membership value k∈0,1 if there exists a multiset γ∈Σ⊕ with γ⊆α,δp,γ,q=k and β=α⊖γ and is denoted by p,α⟶kq,β.
⟶k′∗ denote the reflexive and transitive closure of ⟶k′, i.e., for p,α,q,β∈Q×Σ⊕, p,α⟶k′∗q,β, if for some n≥0, there exists n+1 states q0,…,qn and n+1 multisets α0,…,αn such that q0=p,qn=p′,α0=α,αn=β and qi,αi⟶kiqi+1,αi+1,∀i=0,…,n−1, where k′=k0∧k1∧…∧kn−1.” Now, we define(2)μℳp1,α⟶∗p2,β=∨k′:p,α⟶∗p′,β,μℳp1,α⟶∗p2,α=1,ifp1=p2,0,ifp1≠p2.Example 1.
[58] Let ℳ=Q,Σ,δ,I,τ be an LMA, where Q=q1,q2,q3,q4,Σ=a1,a2,a3, and the L-valued transition function is given as under:(3)δq1,<a2>,q3=0.6,δq3,<a2>⊕<a3>,q4=0.7,δq4,<a1>,q2=0.9,δq1,<a2>⊕<a3>,q3=0.4,δq3,<a2>,q4=0.5.
Ifα=<a1>⊕<a2>⊕<a2>⊕<a3> and β=0Σ. Then the transition steps q1,α⟶∗q2,β are as follows:(i)
q1,<a1>⊕<a2>⊕<a2>⊕<a3>⟶0.6q3,<a1>⊕<a2>⊕<a3>⟶0.7q4,<a1>⟶0.9q2,0Σ,(ii)
q1,<a1>⊕<a2>⊕<a2>⊕<a3>⟶0.4q3,<a1>⊕<a2>⟶0.5q4,<a1>⟶0.9q2,0Σ.
Thus(4)μℳq1,α⟶∗q2,β=∨0.6∧0.7∧0.9,0.4∧0.5∧0.9=∨0.6,0.4=0.6.Definition 12.
[64, 78](i)
For a given setΣ, an L-valued multiset language is a map f:Σ⊕⟶L.(ii)
AnL-valued multiset language f:Σ⊕⟶L is accepted by an LMA ℳ=Q,Σ,δ,I,τ if(5)fα=∨Iq∧μℳq,α⟶∗p,0Σ∧τp:q,p∈Q.
∀α∈Σ⊕. Further, an L-valued multiset language f:Σ⊕⟶L is called regular if there exists a finite LMAℳ such that f=fℳ.
Also,L-valued multiset language f, accepted by an LMAℳ, is denoted by fℳ in [64, 78].


## 2.4. Bipointed Set

Here, we recall the concept of bipointed set from [35], where fuzzy sets were taken their membership values in a structure L˜=L,0,1, where L is an arbitrary set, and 0 and 1 are two distinguished elements of L, and this structure were used to take crisp languages into consideration. In [35], no other conditions were imposed on L. In this paper, fuzzy sets will take their membership in a bipointed set L˜ in sense of [35]. A more generalized view of bipointed set has been given in [36], and it is pointed out there that the concept of bipointed set can be viewed as generlization of the notion of pointed set in [80].Definition 13.
[36] A bipointed set is a 3-tuple L˜=L,a,b, where L is an arbitrary set and a, b are two distinguished elements of L. A homomorphism between two bipointed sets L,a,b and L′,a′,b′ is a map f:L⟶L′ such that fa=a′ and fb=b′.Proposition 1.
[36] The bipointed sets and their homomorphisms form a category denoted by BSET.LetB be any arbitrary set, we identifed it as a bipointed set B˜=B′,0,1, where B′=B⊎0⊎1. It is worth to note that, the class of bipointed sets mentioned above and their morphism also forms a category, which we denote LSET. Obviously, LSET is a subcategory of BSET. Note that 1˜=0,0,1,0,1.From now onward, throughout this paper,L˜ stand for a bipointed set. For a nonempty set U, A:U⟶L˜ is called a fuzzy set over U and L˜U denotes all fuzzy subsets of a set U. The kernel of map f:U⟶V, denoted as kerf, and is defined by kerf=u,v∈U×U:fu=fv, which is an equivalence relation on U. The set U/R=u:u∈U is called the quotient set of U with respect to the equivalence relation R and its cardinality is called the index of R. The image of f, is defined as Imf=fu:u∈U which is a subset of V.


## 3. Crisp Deterministic Fuzzy Multiset Automata and Fuzzy Multiset Language

Fuzzy automata and fuzzy languages having membership values in bipointed set have been studied in [35]. Myhill-Nerode theory have been used there for minimization of fuzzy languages. Here, we define category of crisp deterministic fuzzy multiset automata, introduce the notion of fuzzy multiset languages over bipointed sets, and construct a minimal realization for a given fuzzy multiset language in sense of [35], but approach is categorical.Definition 14.
A crisp deterministic fuzzy multiset automatonCDFMA is a 5-tuple ℳ=Q,Σ,δℳ,q0,βℳ, where(i)
Q and Σ are nonempty sets called the state-set and the input-set, respectively.(ii)
δℳ:Q×Σ⊕⟶Q is a map called transition map.(iii)
βℳ:Q⟶L˜ is a map called fuzzy set of final states.(iv)
q0∈Q is a fixed state called the initial state.
A configuration of aCDFMA is same as in the case of a multiset automaton.Remark 1.
Here 1 stand for one point set0. The initial state q0 is identified by a map τ:1⟶Q defined by τ0=q0.Definition 15.
Letℳ=Q,Σ,δℳ,q0,βℳ and ℳ′=Q′,Σ′,δℳ′,q0′,βℳ′ be CDFMA. A pair of maps a,b=f:ℳ⟶ℳ′ where a:Σ⊕⟶Σ′⊕ and b:Q⟶Q′ is said to be homomorphism from ℳ to ℳ′, if the diagrams in Figure 3 commute.
Note that mapτ send 0 to q0 and τ′ send 0 to q0′. In case f is onto, ℳ′ is said to be homomorphic image of ℳ.Figure 3
Commuting diagram of Definition15.Proposition 2.
TheCDFMA and their homomorphisms form a category under componentwise composition of maps.Proof.
Letℳ=Q,Σ,δℳ,q0,βℳ, ℳ′=Q′,Σ′,δℳ′,q0′,βℳ′ and ℳ″=Q″,Σ″,δℳ″,q0″,βℳ″ be CDFMA and f=a,b and f′=a′,b′ be homomorphisms between ℳ,ℳ′, and ℳ′ and ℳ″, respectively, we only need to show that the diagrams (A), (B) and (C) in Figure 4 commute.
The commutativity of Square (A) and Triangles (B) & (C) in Figure4 follows from commutativity of upper and lower squares in Diagrams (i), and upper and lower triangles in Diagrams (ii) & (iii) in Figure 5, respectively. The diagrams in Figure 5 commute because f and f′ are homomorphisms.
We represent the category described above byCDFMA, and its object-class is denoted by CDFMA.Figure 4
Commuting diagrams for composition of homomorphisms in Proposition1.Figure 5
Commuting diagrams showing commutativity of diagrams in Figure4.Figure 6
Commuting diagrams forCDFMAΣ0⊕-morphism of Remark 2 (ii).Remark 2.
(i)
The objects class of CDFMA having fixed input set of alphabetsΣ0 and their morphisms as all CDFMA-morphisms of type idΣ0⊕,b form a category denoted by CDFMAΣ0, its object class is denoted by CDFMAΣ0. Definitely, the category so obtained is a subcategory of CDFMA.(ii)
A morphismΣ0⊕,b from ℳ=Q,Σ0,δℳ,q0,βℳ to ℳ′=Q′,Σ0,δℳ′,q0′,βℳ′∈CDFMAΣ0, is simply a map b:Q⟶Q′, which make the diagrams in Figure 6 commute.
Throughout, this paperΣ0⊕ denotes the set of all multisets over a fixed input set Σ0. We shall denote by 0Σ0, the identity element of Σ0⊕. Now, we define fuzzy multiset language having membership values in bipointed sets L˜.Definition 16.
For a given fixed finite alphabetΣ0, a fuzzy multiset language is a map f:Σ0⊕⟶L˜.Definition 17.
(i)
Givenℳ=Q,Σ0,δℳ,q0,βℳ in CDFMAΣ0 with crisp initial state q0. A fuzzy multiset language fq, accepted by ℳ in the state q, is a map fq:Σ0⊕⟶L˜ defined by fqα=βℳδℳq,α, ∀α∈Σ0⊕.(ii)
A fuzzy multiset language, accepted byℳ∈CDFMAΣ0, in state q0 (i.e., fq0) is simply called the fuzzy multiset language accepted by ℳ, which we denote by fℳ. Further, a fuzzy multiset language f:Σ0⊕⟶L˜ is called regular if there exists a finite ℳ∈CDFMAΣ0 such that f=fℳ.Definition 18.
Letℳ=Q,Σ0,δℳ,q0,βℳ in CDFMAΣ0. The reachability map rℳ of ℳ is a map rℳ:Σ0⊕⟶Q defined as rℳα=δℳq0,α,∀α∈Σ0⊕.Remark 3.
It can also be easily seen that(i)
rℳ0Σ0=q0,(ii)
rℳα⊕γ=δℳrℳα,γ,∀α,γ∈Σ0⊕.Remark 4.
Reachability ofℳ=Q,Σ0,δℳ,q0,βℳ in CDFMAΣ0 means for each q∈Q,∃α∈Σ0⊕ such that δℳq0,α=q. Thus reachability of ℳ can be characterized in terms of reachability map as “ℳ is called reachable if rℳ is onto.”Definition 19.
(i)
Givenℳ=Q,Σ0,δℳ,q0,βℳ in CDFMAΣ0, the coreachability map σℳ of ℳ is a map σℳ:Q⟶L˜Σ0⊕ defined by σℳq=fq,∀q∈Q.(ii)
ℳ is said to be coreachable if σℳ is one-one.Remark 5.
(i)
It is important to note that,σℳq0=fq0, where fq0α=βℳ°rℳα=βℳrℳα=βℳδℳq0,α, ∀α∈Σ0⊕.(ii)
The coreachability map ofℳ=Q,Σ0,δℳ,q0,βℳ in CDFMAΣ0 tells that corresponding to distinct states there are different fuzzy multiset languages associated with it.Definition 20.
ℳ=Q,Σ0,δℳ,q0,βℳ in CDFMAΣ0 is called realization for fuzzy multiset language f if fα=βℳδℳq0,α, for all α∈Σ0⊕. Further, the realization ℳ is called minimal, if ℳ is reachable as well as coreachable.
Now, letℳ=Q,Σ0,δℳ,q0,βℳ in CDFMAΣ0 which accepts fuzzy multiset language f. Define a map μℳ1:Σ0⊕×Σ0⊕⟶Σ0⊕ such that μℳ1α,<γ>=α⊕<γ>,∀α,<γ>∈Σ0⊕. Then ℳ1=Σ0⊕,Σ0,μℳ1,0Σ0,f∈CDFMAΣ0, which accepts the fuzzy multiset language f. Now, we have the following.Proposition 3.
Letℳ,ℳ1∈CDFMAΣ0 be as defined above. The reachability map rℳ of ℳ is a CDFMAΣ0-morphism from ℳ1 to ℳ.Proof.
To show that the reachability maprℳ:Σ0⊕⟶Q of ℳ is a CDFMAΣ0-morphism from ℳ1 to ℳ, we need to show only that the diagrams in Figure 7 commute.
Sincerℳ°μℳ1α,<γ>=rℳμℳ1α,<γ>=rℳα⊕<γ>=δℳrℳα,<γ>=δℳ°rℳ,idΣ0⊕α,<γ>, ∀α,<γ>∈Σ0⊕, whereby Square A in Figure 7 holds.The Triangle B in Figure 7 holds because rℳ°τ10=rℳ0Σ0=q0=τ20. The Triangle (C) in Figure 7 holds as βℳ°rℳα=βℳδq0,α=fα,∀α∈Σ0⊕.
Again, letℳ=Q,Σ0,δℳ,q0,βℳ in CDFMAΣ0 which accepts a given fuzzy multiset language f. We define the maps π:L˜Σ0⊕×Σ0⊕⟶L˜Σ0⊕ such that πh,<γ>=hγ, where hγα=hα⊕<γ>, ∀h∈L˜Σ0⊕,∀α,<γ>∈Σ0⊕ and θ:L˜Σ0⊕⟶L˜ such that θh=h0Σ0. Then ℳ2=L˜Σ0⊕,Σ0,π,f,θ is also a member of CDFMAΣ0, which accepts the fuzzy multiset language f. Now, we have the following.Figure 7
Commuting diagrams for Proposition3.Proposition 4.
The coreachability mapσℳ of ℳ=Q,Σ0,δℳ,q0,βℳ∈CDFMAΣ0 is a CDFMAΣ0-morphism from ℳ to ℳ2=L˜Σ0⊕,Σ0,π,f,θ.Proof.
To show that the coreachability mapσℳ:Q⟶L˜Σ0⊕ is a CDFMAΣ0-morphism from ℳ to ℳ2, we need to show that the diagrams in Figure 8 hold.
Letq,α be an arbitrary element of Q×Σ0⊕, then π°σℳ,idΣ0⊕q,α=πσℳq,α=πfq,α=fqα, σℳ°δℳq,α=σℳδℳq,α=fδℳq,α, and for all γ∈Σ0⊕, fqαγ=fqα⊕γ=βℳδℳq,α⊕γ=βℳδℳδℳq,α,γ=fδℳq,αγ, whereby Square A in Figure 8 holds, Since σℳ°τ10=σℳq0=fq0=τ20, the Triangle B in Figure 8 holds. Finally, to show that the Triangle (C) in Figure 8 holds, let q∈Q be arbitrary, then θ°σℳq=θfq=fq0Σ0=βℳδℳq,0Σ0=βℳq.
The coreachability mapσℳ1:Σ0⊕⟶L˜Σ0⊕ℳ1=Σ0⊕,Σ0,μℳ1,0Σ0,f∈CDFMAΣ0 is defined as for all α∈Σ0⊕, σℳ1α=fα, where fαγ=fμℳ1α,γ=fα⊕γ,∀γ∈Σ0⊕. Now, we have the following.Figure 8
Commuting diagrams of Proposition4.Proposition 5.
The coreachability mapσℳ1 of ℳ1 is a CDFMAΣ0-morphism from ℳ1 to ℳ2.Proof.
Follows from commutativity of diagrams in Figure9 below.Figure 9
Commuting diagrams of Proposition5.


## 4. Myhill-Nerode Theory Based Minimal Realization for a Fuzzy Multiset Language

The minimal realization theory for a given fuzzy language was introduced in [35] by using Myhill Nerode theory. Herein, we present the same for fuzzy multiset language using Myhill Nerode theoretic concept and the concepts of reachability and coreachability map.Proposition 6.
For a fuzzy multiset languagef:Σ0⊕⟶L˜ over a fixed alphabet Σ0, ∃ a minimal realization Nf∈CDFMAΣ0 for f.Proof.
Letf:Σ0⊕⟶L˜ be a given fuzzy multiset language over a fixed alphabet Σ0. Let α1,α2∈Σ0⊕. Define a relation R over Σ0⊕ as R=α1,α2:fα1⊕γ=fα2⊕γ,∀γ∈Σ0⊕. This relation is called Myhill-Nerode relation on Σ0⊕. One can examine that R is an equivalence relation on Σ0⊕. The equivalence class of an element α1∈Σ0⊕ with respect to R is denoted by α1 and is defined as α1=α2∈Σ0⊕:fα1⊕γ=fα2⊕γ,∀γ∈Σ0⊕: The set Σ0⊕/R=α:α∈Σ0⊕ is called factor set of Σ0⊕ with respect to R. Now, let Qf=Σ0⊕/R=α:α∈Σ0⊕, and define the maps δf:Qf×Σ0⊕⟶Qf and βf:Qf⟶L˜ such that δfα1,α2=α1⊕α2 and βfα=fα, ∀α,α1,α2∈Σ0⊕. These maps δf and βf are well defined as shown under. Let α1,α2∈Σ0⊕ be such that α1=α2, then we have(6)α1=α2⇒α1Rα2⇒fα1⊕γ=fα2⊕γ,∀γ∈Σ0⊕⇒fα1⊕α⊕γ=fα2⊕α⊕γ,∀α,γ∈Σ0⊕⇒α1⊕αRα1⊕α⇒α1⊕α=α1⊕α⇒δfα1,α=δfα2,α,where by δf is well defined. Again,(7)α1=α2⇒α1Rα2⇒fα1⊕γ=fα2⊕γ,∀γ∈Σ0⊕⇒fα1⊕0Σ0=fα2⊕0Σ0,for identity0Σ0∈Σ0⊕⇒fα1=fα2⇒βfα1=βfα2.
And soβf is also well defined. Thus Nf=Qf,Σ0,δf,0Σ0f,βf∈CDFMAΣ0. Now, let α∈Σ0⊕. Then(8)fα=βfα=βfδf0Σ0f,α.
HenceNf realizes f.
Now, to establish thatNf is minimal, we must show that the reachability map rNf:Σ0⊕⟶Qf of Nf is onto and coreachability map σNf:Qf⟶L˜Σ0⊕ of Nf is one-one. Let α∈Qf, then rNfα=δf0Σ0,α=α. Thus rNf:Σ0⊕⟶Qf is onto, and so Nf is reachable. Also, let α1,α2∈Σ0⊕ such that σNfα1=σNfα2. Then fα1=fα2. Now, for all α∈Σ0⊕,(9)fα1=fα2⇒fα1α=fα2α⇒βfδfα1,α=βfδfα2,α⇒βfα1⊕α=βfα2⊕α⇒fα1⊕α=fα2⊕α⇒α1Rα2⇒α1=α2,where by σNf is one-one. Hence Nf is minimal.Remark 6.
Hereafter, we callNf, the Nerode realization.
The derivative of a language have been used as a tool for minimization by Rabin and Scott [81], while in fuzzy scenario this concept have been shown useful by Mordeson and Malik [33], Petković [82], and Ignjatović et al. [35]. In this section, we have introduce the concept of derivative of a fuzzy multiset language over a bipointed set, and provide some useful results associated with interconnectivity of regular-ness, the set of derivatives, and Myhill-Neroode equivalence of a fuzzy multiset language.Definition 21.
For a fuzzy multiset languagef:Σ0⊕⟶L˜, and α∈Σ0⊕, a fuzzy multiset language fα:Σ0⊕⟶L˜ defined by (10)fαγ=fα⊕γ.
∀γ∈Σ0⊕, is called a derivative of f w.r.t. α.Proposition 7.
Letσℳ1:Σ0⊕⟶L˜Σ0⊕ be the coreachability map ℳ1=Σ0⊕,Σ0,μℳ1,0Σ0,f∈CDFMAΣ0. Let Df denote set of all derivatives of f, Then,(i)
kerσℳ1 is the Myhill-Nerode relation on Σ0⊕(ii)
Imσℳ1=Df.(iii)
σℳ°rℳ=σℳ1.Proof.
(i)
kerσℳ1=α1,α2:σℳ1α1=σℳ1α2=α1,α2:fα1=fα2=α1,α2:fα1γ=fα2γ,∀γ∈Σ0⊕=α1,α2:fα1⊕γ=fα2⊕γ,∀γ∈Σ0⊕. This is nothing but Myhill-Nerode relation on multiset Σ0⊕.(ii)
Imσℳ1=σℳ1α1:α1∈Σ0⊕=fα1:fα1α2=fα1⊕α2,α1,α2∈Σ0⊕=Df,(iii)
For allα1∈Σ0⊕, σℳ°rℳα1=σℳrℳα1=σℳδℳq0,α1=fδℳq0,α1. Also, ∀α2∈Σ0⊕, fδℳq0,α1α2=βℳδℳδℳq0,α1,α2=βℳδℳq0,α1⊕α2=fα1⊕α2. Thus σℳ°rℳ=σℳ1.Proposition 8.
Letf:Σ0⊕⟶L˜ be fuzzy multiset language and Df be set of all derivatives of f and Df be set of all its derivatives. Then the following are equivalent.(i)
f is regular.(ii)
Df is finite.(iii)
The Myhill-Nerode equivalence has finite index.Proof.
(i)
⇒ (ii): Let f be a fuzzy multiset regular language. Then ∃ a ℳ=Q,Σ0,δℳ,q0,βℳ∈CDFMAΣ0 which accepts f, and therefore ℳ1=Σ0⊕,Σ0,μℳ1,0Σ0,f∈CDFMAΣ0 accepts f. Now, Imσℳ1=σℳ1α:α∈Σ0⊕=σℳrℳα:α∈Σ0⊕, is finite since rℳα∈Q,∀α∈Σ0⊕ and Q is finite. Thus Imσℳ1, i.e., the set of derivatives of f is finite.(ii)
⇒ (iii): Follows from the definition of Imσℳ1 and kerσℳ1.(iii)
⇒ (i): Let the Myhill-Nerode equivalence has finite index. Then ∃ a Nf=Qf,Σ0,δf,0Σ0f,βf∈CDFMAΣ0 which accepts f. Hence f is regular.


## 5. Categorical View of Crisp Deterministic Fuzzy Multiset Automata Theoretic Concepts

In Section3, corresponding to ℳ=Q,Σ0,δℳ,q0,βℳ∈CDFMAΣ0 accepting fuzzy multiset language f, we have defined two CDFMAΣ0-objects ℳ1=Σ0⊕,Σ0,μℳ1,0Σ0,f and ℳ2=L˜Σ0⊕,Σ0,π,f,θ accepting the same fuzzy multiset language f. We then characterized the reachability map rℳ:Σ0⊕⟶Q and coreachability map σℳ:Q⟶L˜Σ0⊕ of ℳ as a CDFMAΣ0-morphisms. Herein, we introduce the category MDYNΣ0⊕ of multiset Σ0⊕-dynamics (ℳΣ0⊕-dynamics) along with their homomorphism. We then introduce a functor U between the category MDYNΣ0⊕ and the category LSET and demonstrate the existence of left adjoint as well as right adjoint for the functor U. We then characterize the run map δℳ:Q×Σ0⊕⟶Q of ℳ∈CDFMAΣ0 as a unique MDYNΣ0⊕-morphism. Interestingly, the reachability map rℳ of ℳ∈CDFMAΣ0 viewed here as rℳ:1×Σ0⊕⟶Q rather than Σ0⊕⟶Q, this representation facilitate us to characterized rℳ as a unique MDYNΣ0⊕-morphism. Also, we have shown here that the coreachability map σℳ:Q⟶L˜Σ0⊕ of ℳ∈CDFMAΣ0 is a unique MDYNΣ0⊕-morphism. All these characterizations have been carried out in purely arrow theoretic representation.Definition 22.
For a fixed finite alphabetΣ0 and corresponding multiset Σ0⊕. We define a map δM:Q×Σ0⊕⟶Q, for any arbitrary state set Q. The map δM or the pair Q,δM is called MΣ0⊕-dynamics. The set of all MΣ0⊕-dynamics is denoted by MDYNΣ0⊕=Q,δM:δM:Q×Σ0⊕⟶Q. For a given MΣ0⊕-dynamics Q,δM the map δM defined inductively by δMq,0Σ0⊕=q,∀q∈Q and δMq,α⊕<γ>=δMδMq,α,<γ>,∀q∈Q,α,<γ>∈Σ0⊕ is called its run map.Definition 23.
A morphism from aMΣ0⊕-dynamics Q,δℳ to a MΣ0⊕-dynamics Q′,δℳ′ is simply a map b:Q⟶Q′ which make diagram of Figure 10 commutes.Figure 10
Diagram for homomorphism between twoMDYNΣ0⊕ Definition 23.Proposition 9.
TheMΣ0⊕-dynamics along with their morphisms, under component wise composition of maps, form a category.Proof.
We need to show that(i)
MDYNΣ0⊕-morphisms b:Q,δℳ⟶Q′,δℳ′ and b′:Q,′δℳ′⟶Q″,δℳ″ are composable, which follows from commutativity of diagrams in Figure 11The Diagram (A) in Figure11 commute since for all q∈Q, α∈Σ0⊕, we have b′°b,idΣ0⊕q,α=b′°bq,α=b′bq,idΣ0⊕α=b′,idΣ0⊕°b,idΣ0⊕q,α. The Diagrams (B) and (D) commute because b and b′ are homomorphisms and Diagram C is definition of b′°b. Thus the commutativity of perimeter of Diagram (i) in Figure 11 hold, i.e., the Diagram (ii) in Figure 11 commute.(ii)
given a MDYNΣ0⊕ and a bijection h:Q⟶Q′∃ a unique δℳ′ such that b:Q,δℳ⟶Q′,δℳ′ and b−1:Q′,δℳ′⟶Q,δℳ are morphisms. This is true because the diagrams in Figure 12, where upper Square (A) is identical with lower Square (B), uniquely hold by setting δ′q′,x=bδb−1q′,α,∀q′∈Q′ and α∈Σ0⊕.
We represent the category ofMΣ0⊕-dynamics and their morphisms by MDYNΣ0⊕.Figure 11
Commutative diagrams for Proposition9.Figure 12
Commutative diagrams for Proposition9.Remark 7.
It is worth to note thatCDFMAΣ0-morphism b:ℳ⟶ℳ′ is a MDYNΣ0⊕-morphism b for which diagram in Figure 13 commutes.Figure 13
Diagram for Remark7.Proposition 10.
LetU:MDYNΣ0⊕⟶LSET be such that ∀Q,π∈MDYNΣ0⊕, UQ,π=Q˜, and ∀MDYNΣ0⊕-morphism h:Q,πℳ⟶Q′,πℳ′,Uh=h˜, where h˜:Q˜⟶Q′˜ is a map satisfying h˜0=0 and h˜1=1. Then U is a functor.Proposition 11.
The functorU:MDYNΣ0⊕⟶LSET has a left adjoint.Proof.
We need to establish existence of a pairℳ,ηQ˜ corresponding to every Q˜∈LSET, where ℳ∈MDYNΣ0⊕ and ηQ˜:Q˜⟶Uℳ is a LSET-morphism with property that for any N∈MDYNΣ0⊕, and any LSET-morphism f:Q˜⟶UN, ∃ a unique MDYNΣ0⊕-morphism ψ:ℳ⟶N which make the diagram in Figure 14 commutes.
Letℳ=Q×Σ0⊕,δQ∈MDYNΣ0⊕, where δQ:Q×Σ0⊕×Σ0⊕⟶Q×Σ0⊕ is a map defined by δQq,α,<γ>=q,α⊕<γ>, ∀q∈Q,α,<γ>∈Σ0⊕. Let N=Q′,δN∈MDYNΣ0⊕ be arbitrary, and ηQ˜:Q˜⟶Q×Σ0⊕˜ be a map defined as ηQ˜q=q,0Σ0,∀q∈Q, ηQ˜0=0 and ηQ˜1=1. Then ηQ˜:Q˜⟶Q×Σ0⊕˜ is a morphism of LSET, and diagram in Figure 14 reduces to the diagram in Figure 15.
Now, defineψ:ℳ⟶N satisfying(a)
ψq,0Σ0=fq, and(b)
ψq,α⊕<γ>=δNψq,α,<γ>, ∀q∈Q,α,<γ>∈Σ0⊕.
Then the following diagram in Figure16 commutes, which means ψ is a morphism of MDYNΣ0⊕.
The fact thatψ be unique is trivial. Further, definition of ψ makes diagram in Figure 13 commute, whereby U has a left adjoint.Figure 14
Diagram for left adjoint Proposition11.Figure 15
Diagram equivalent to diagram in Figure14 Proposition 11.Figure 16
Diagram forMDYNΣ0⊕-morphism ψ.Remark 8.
In Proposition11, we have defined a map δQ:Q×Σ0⊕×Σ0⊕⟶Q×Σ0⊕ by δQq,α,<γ>=q,α⊕<γ>, ∀q∈Q,α,<γ>∈Σ0⊕. The pair Q×Σ0⊕,δQ is a MΣ0⊕-dynamics or in other words Q×Σ0⊕,δQ∈MDYNΣ0⊕. We call the MΣ0⊕-dynamics Q×Σ0⊕,δQ the free MΣ0⊕-dynamics on Q˜ generators.
Now, the run map of aCDFMAΣ0-object can be characterized as follows.Corollary 1.
The run mapδℳ of ℳ=Q,Σ0,δℳ,q0,βℳ∈CDFMAΣ0 is a unique morphism ψ:Q×Σ0⊕,δQ⟶Q,δℳ of MDYNΣ0⊕ satisfying δℳ˜°ηQ˜=idQ˜.Proof.
LetN=Q,δℳ and f=idQ˜ in proof of Proposition 11. Then diagrams below in Figure 17 commute,
Which meansψq,0Σ0=q, and ψq,α⊕<γ>=δℳψq,α,<γ>, ∀q∈Q,α,<γ>∈Σ0⊕. Moreover, ψ=δℳ, and δℳ˜°ηQ˜=idQ˜ hold by Definition 4 and by the fact that ψ is unique.
Reachability maprℳ:Σ0⊕⟶Q of ℳ=Q,Σ0,δℳ,q0,βℳ∈CDFMAΣ0 can also be viewed as the map rℳ:1×Σ0⊕⟶Q such that rℳ0,0Σ0=q0 and rℳ0,α⊕γ=δℳrℳ0,α,γ, ∀α,γ∈Σ0⊕. Viewing rℳ rather than a map rℳ:1×Σ0⊕⟶Q than Σ0⊕⟶Q, we have another characterization of rℳ in MDYNΣ0⊕.Figure 17
MDYNΣ0⊕ -morphism ψ as run map δℳ.Corollary 2.
The reachability maprℳ of ℳ=Q,Σ0⊕,δℳ,q0,βℳ∈CDFMAΣ0 is a unique MDYNΣ0⊕-morphism rℳ:1×Σ0⊕,δ1⟶Q,δℳ satisfying rℳ˜°η1˜=τ.Proof.
In Proposition11, we set N=Q,δℳ, and f=τ. We get commutative diagrams shown in Figure 18,
Which imply thatψ0,0Σ0=q0 and ψ0,α⊕<γ>=δℳψ0,α,<γ>,∀α,<γ>∈Σ0⊕. Now, by definition of reachability map and uniqueness of ψ, we conclude ψ=rℳ and rℳ˜°η1˜=τ˜.Figure 18
MDYNΣ0⊕-morphism ψ as reachability map rℳ.Remark 9.
In Remark4, we says reachability of ℳ=Q,Σ0,δℳ,q0,βℳ∈CDFMAΣ0 means every states of ℳ should be reached starting from its initial state, i.e., ℳ is called reachable, if for every q∈Q,∃α∈Σ0⊕ satisfying δℳq0,α=q, i.e., for every q∈Q, there is an rℳα=δℳq0,α, for some α∈Σ0⊕.
In categorical term, and in context of our discussion Remark9 gives following.Definition 24.
AMDYNΣ0⊕-object Q,δℳ with initial state q0 is called reachable if its reachability map rℳ is epimorphism.Proposition 12.
The functorU:MDYNΣ0⊕⟶LSET has a right adjoint.Proof.
We must show that corresponding to everyL˜∈LSET , ∃ a pair ε,ℳ, with ℳ an object of MDYNΣ0⊕, and ε:Uℳ⟶L˜ a morphism of LSET with property that for any object N=Q,δ of MDYNΣ0⊕ and for any morphism g:UN⟶L˜ of LSET, the diagram below in Figure 19 commutes.
LetL˜Σ0⊕,δL˜=ℳ be a member of MDYNΣ0⊕, where the map δL˜:L˜Σ0⊕×Σ0⊕⟶L˜Σ0⊕ is defined as δL˜f,α=fNα with Nα:Σ0⊕⟶Σ0⊕ is a map such that Nαγ=α⊕γ. Also, let us define a map ε:L˜Σ0⊕˜⟶L˜ as εf=f0Σ0, ε0=0 and ε1=1. Then the diagram in Figure 19 take the form of diagram in Figure 20.
Now, define a mapψ:Q⟶L˜Σ0⊕ satisfying ψq=fq, so that the diagram in Figure 21 commutes,
The commutative diagram of Figure22 implies that ψ:ℳ⟶N is a MDYNΣ0⊕-morphism. Also, the fact that ψ is unique, is trivial. Further, the definition of ψ make Figure 21 commute, whereby U has a right adjoint.Figure 19
Diagram for right adjoint Proposition12.Figure 20
Diagram equivalent to diagram in Figure19.Figure 21
Diagram forψ as CDFMSA Σ0-morphism.Figure 22
Commutative diagram for Proposition13.Remark 10.
In Proposition12 we have define a map δL˜:L˜Σ0⊕×Σ0⊕⟶L˜Σ0⊕ by δL˜f,α=fNα, where Nα:Σ0⊕⟶Σ0⊕ is a map such that Nαγ=α⊕γ. In other words L˜Σ0⊕,δL˜ is a MΣ0⊕-dynamics or L˜Σ0⊕,δL˜∈MDYNΣ0⊕, we call L˜Σ0⊕,δL˜ the cofree MΣ0⊕-dynamics on L˜ generators and σℳ:Q,δℳ⟶L˜Σ0⊕,δL˜ is a MΣ0⊕-dynamics.
Now, we characterize coreachability map ofℳ∈CDFMAΣ0 in category MDYNΣ0⊕ as follows.Corollary 3.
The coreachability mapσℳ of ℳ=Q,Σ0,δℳ,q0,βℳ∈CDFMAΣ0 is a unique morphism σℳ:Q,δℳ⟶L˜Σ0⊕,δL˜ of MDYNΣ0⊕ satisfying ε°σℳ˜=βℳ˜.Proof.
In proof of Proposition12, we set g=βℳ˜, we have commutative diagrams in Figure 23
Which providesψqα=βℳδℳq,α,∀α∈Σ0⊕. This with use of Definitions 18 and 20, Remark 3 and uniqueness of ψ implies ψ=σℳ with property that ε°σℳ˜=βℳ˜.Figure 23
MDYNΣ0⊕-morphism ψ as coreachability map σℳ.


## 6. Free and CofreeMΣ0⊕-Dynamics and Their Nature with respect to Forgetful Functor U

In previous section, we have defined a forgetful functorU:MDYNΣ0⊕⟶LSET having left as well as right adjoint, meanwhile, in Remark 9 and 10, we have mentioned that Q×Σ0⊕,δQ is free MΣ0⊕-dynamics on Q˜ generators and L˜Σ0⊕,δL˜ is cofree MΣ0⊕-dynamics on L˜ generators, respectively. Consider the functor U:MDYNΣ0⊕⟶LSET, if every Q˜∈LSET has a free ℳ,ηQ˜ (where ℳ=Q×Σ0⊕,δQ∈MDYNΣ0⊕ and ηQ˜:Q˜⟶Q×Σ0⊕˜ is a LSET-morphism, see Proposition 11), with respect to the functor U, then we can introduce a functor V:LSET⟶MDYNΣ0⊕ for which VQ˜ is free over Q˜. Such a functor V is said to be left adjoint of the functor U. In category theory, every concept has its dual concept, so dually, if every member in LSET has a cofree object, then there is a cofree object constructing functor called the right adjoint of U. Thus we conclude that U:MDYNΣ0⊕⟶LSET has a left adjoint if every Q˜∈LSET has a pair ℳ,ηQ˜ free over Q˜, and that V has a right adjoint if corresponding to every element ℳ∈MDYNΣ0⊕ there is a pair Q˜,η cofree over ℳ . Now, we have following.Proposition 13.
LetU:MDYNΣ0⊕⟶LSET be a functor with property that to every Q˜∈LSET, there corresponds a free object, which we call VQ˜,ηQ˜ so that ηQ˜:Q˜⟶UVQ˜. Given any f˜:Q˜⟶Q˜ in LSET. Define a morphism Vf:VQ˜⟶VQ′˜ by the diagram in Figure 24Then the collection of mapsV:LSET⟶MDYNΣ0⊕ so defined is a functor (it is to be noted here that the object map is unique up to isomorphism, and morphism maps is also fixed uniquely) called the left adjoint of U.Figure 24
Diagram for Proposition13.Proof.
In order to show thatV:LSET⟶MDYNΣ0⊕ is a functor. We have to show that VidQ˜=idVQ˜ and Vg°f=Vg°Vf. From uniqueness property, the commutativity of diagram in Figure 22 below clearly implies that VidQ˜=idVQ˜.
Also, for any twoLSET morphisms f˜,g˜ and the fact that U:MDYNΣ0⊕⟶LSET is a functor, the diagrams in Figure 25 commute.
And so uniqueness ofU ensure us that Vg˜°f˜=Vg˜°Vf˜. Hence V is a functor.
Dually, we haveFigure 25
Commutative diagrams for Proposition13.Proposition 14.
LetV:LSET⟶MDYNΣ0⊕ be a functor with the property that to every ℳ∈MDYNΣ0⊕, there correspond a cofree object, which we call Uℳ,εℳ (so that εℳ:VUℳ⟶ℳ). Given any f:ℳ′⟶ℳ in MDYNΣ0⊕, define a morphism Uf:Uℳ′⟶Uℳ by the diagram in Figure 26.ThenU is a functor, which we call right adjoint of V.Figure 26
Diagrams for Proposition14.Proof.
Similar to Proposition13.
In Proposition11, we have defined a MΣ0⊕-dynamics δQ:Q×Σ0⊕×Σ0⊕⟶Q×Σ0⊕ defined by δQq,α,γ=q,α⊕γ, for all q∈Q,α,γ∈Σ0⊕, which we call free MΣ0⊕-dynamics on Q˜ generators and associate a map ηQ˜:Q˜⟶Q×Σ0⊕˜ defined by ηQ˜q=q,0Σ0,∀q∈Q, ηQ˜0=0 and ηQ˜1=1. In next proposition, we have shown that the free MΣ0⊕-dynamics on Q˜ generators is free with respect to forgetful functor U:MDYNΣ0⊕⟶LSET, i.e., the pair ℳ,ηQ˜, (where ℳ=Q×Σ0⊕,δQ∈MDYNΣ0⊕ and ηQ˜ are defined as above) is free over Q˜ with respect to forgetful functor U.Proposition 15.
Let us consider the forgetful functorU:MDYNΣ0⊕⟶LSET, and let Q˜ be any member of LSET. Then the pair ℳ,ηQ˜ defined above is free over Q˜ with respect to U. Thus U has a left adjoint.Proof.
We must have to show that, given anyMΣ0⊕-dynamics δ:S×Σ0⊕⟶S, and any map f˜:Q˜⟶S˜, there exists a unique MΣ0⊕-dynamorphism or MDYNΣ0⊕-morphism ψ:Q×Σ0⊕,δQ⟶S×Σ0⊕, (i.e., ψ:δQ⟶δ) such that f˜=Uψ°ηQ˜, i.e., a unique map ψ:Q×Σ0⊕⟶S such that the diagrams in Figure 27 commutes.
The DiagramA in Figure 27 just says that ∀q∈Q,ηQ˜q=q,0Σ0, ηQ˜0=0, and ηQ˜1=1, ψ˜q,0Σ0=f˜q, f˜0=0, f˜1=1, while Diagram (B) in Figure 27 says that ψq,α⊕<γ>=δψq,α,<γ>, for all q∈Q,α,<γ>∈Σ0⊕. Now, in view of Definition 22 of the run map δ of MΣ0⊕-dynamics S,δ, the above equations implies that ψq,α=δfq,α,∀q∈Q,α∈Σ0⊕. Since a unique map ψ thus exists, the pair δQ,ηQ˜ is indeed free over Q˜ with respect to forgetful functor U.
In proof of Proposition12, we have defined a MΣ0⊕-dynamics L˜Σ0⊕,δL˜ (= N say), where δL˜:L˜Σ0⊕×Σ0⊕⟶L˜Σ0⊕ is defined by δL˜f,α=fNα, and Nα:Σ0⊕⟶Σ0⊕ is a map such that Nαγ=α⊕γ. In other words N=L˜Σ0⊕,δL˜∈MDYNΣ0⊕, we call N to be the cofree MΣ0⊕-dynamics on L˜ generators, and we have also defined a map ε:L˜Σ0⊕˜⟶L˜ there. In next proposition, we shall show that the cofree MΣ0⊕-dynamics δL˜ on L˜ generators is cofree with respect to the forgetful functor U:MDYNΣ0⊕⟶LSET, i.e., the pair N,ε is cofree with respect to the forgetful functor U.Figure 27
Commutative diagrams for Proposition15.Proposition 16.
Let us consider the forgetful functorU:MDYNΣ0⊕⟶LSET, and let Q˜ be any member of LSET. Then the pair N,ε as defined above is cofree over L˜ with respect to U. Thus U has a right adjoint.Proof.
We have to just show that, given anyMΣ0⊕-dynamics R,ϱ and any map h:R˜⟶L˜, ∃ a unique MDYNΣ0⊕-morphism ϕ:R,ϱ⟶L˜Σ0⊕,δL˜ such that h=ε°Uϕ˜, i.e., a unique map ϕ:R⟶L˜Σ0⊕ such that the diagrams in Figure 28 commutes.
But the Diagram (A) in Figure28 just says that εf=f0Σ0, ε0=0, ε1=1; ϕ0=0 and ϕ1=1; h0=0, h1=1 and ∀q∈R,ϕq=fq and ε°ϕq=εϕq=εfq=fq0Σ0=hq, while Diagram (B) in Figure 28 means δL˜°ϕ,idΣ0⊕q,<γ>⊕α=δL˜ϕq,<γ>⊕α=ϕ°ϱq,<γ>⊕α,∀q∈R,<γ>,α∈Σ0⊕. In other word δL˜f,α=fNα with Nα:Σ0⊕⟶Σ0⊕ is a map such that Nαγ=α⊕γ. These equations imply that fqα=hϱq,α,∀q∈R,α∈Σ0⊕. Since a unique ϕ exists, N,ε is indeed cofree over L˜ with respect to forgetful functor U.
We conclude that the free and cofreeMΣ0⊕-dynamics are free and cofree with respect to the forgetful functor U:MDYNΣ0⊕⟶LSET.Figure 28
Diagram for Proposition16.


## 7. A Categorical View of Minimal Realization Theory for a Fuzzy Multiset Language

In Section3, we have defined the category CDFMAΣ0. In the subsequent section, Section 4, we have provided Myhill-Nerode theoretic minimal realization of a fuzzy multiset language, whereas, in Section 5, we have introduced the category MDYNΣ0⊕ of MΣ0⊕-dynamics and their morphisms. In this section, we introduce the notion of response of a member ℳ∈CDFMAΣ0. It has been pointed out here that every fuzzy multiset language can be expressed in terms of the response of a ℳ∈CDFMAΣ0. We have shown that the response f^ℳ of ℳ∈CDFMAΣ0 is a MDYNΣ0⊕-morphism. Interestingly, it has been shown here that every MDYNΣ0⊕-morphism has a minimal realization. This section provides another view of minimal realization theory for a fuzzy multiset language in a pure arrow-based categorical theoretic setup. Finally, it is proved here that all the minimal realization of MDYNΣ0⊕-morphism as a response map (or equivalently, for a fuzzy multiset language) is isomorphic to Nerode realization for a fuzzy multiset language.Definition 25.
(a)
Letℳ=Q,Σ0,δℳ,q0,βℳ be a member of CDFMAΣ0 having its reachability map rℳ:1×Σ0⊕⟶Q and coreachability map σℳ:Q⟶L˜Σ0⊕. Then a map f^ℳ=σℳ°rℳ:1×Σ0⊕⟶L˜Σ0⊕ is defined to be a response of ℳ.(b)
Aℳ∈CDFMAΣ0 is said to be a realization of a map g:1×Σ0⊕⟶L˜Σ0⊕, if g is a response of CDFMAΣ0-object ℳ.Remark 11.
(a)
For allα∈Σ0⊕, we shall denote f^ℳ0,α by f^ℳα.(b)
Forα∈Σ0⊕, f^ℳα∈L˜Σ0⊕ and f^ℳα=σℳ°rℳα=σℳδℳq0,α=fδℳq0,α. Also, for α∈Σ0⊕, f^ℳαγ=fδℳq0,αγ=fδℳq0,α⊕γ=fq0α⊕γ, or, in particular, f^ℳ0Σ0=fq0.(c)
Every fuzzy multiset languagef:Σ0⊕⟶L˜ can be represented as f=f^ℳ0Σ0, for some response f^ℳ of a ℳ∈CDFMAΣ0. Therefore, it is interesting to see that the realization theory of a fuzzy multiset language is totally captured in the above introduced realization theory.Proposition 17.
Letb:ℳ⟶ℳ′ be a CDFMAΣ0-morphism between the CDFMAΣ0-object ℳ=Q,Σ0,δℳ,q0,βℳ and ℳ′=Q′,Σ0,δℳ′,q0′,βℳ′. Then ℳ as well as ℳ′ have identical response.Proof.
FromCorollaries 2 and 3 with assumption that b:ℳ⟶ℳ′ is a CDFMAΣ0-morphism, i.e., the diagram in Figure 16 commute, we have the commutative diagrams in Figure 29.
These diagrams just says thatb˜°rℳ˜°η1˜=Uτ′ and ε°σℳ′˜°b˜=βℳ˜, or, in particular, b°rℳ°η1=τ′ and ε°σℳ′°b=βℳ. But by Corollaries 2 and 3, we have b°rℳ=rℳ′ and σℳ′°b=σℳ. Finally, let ℳ,ℳ′∈CDFMAΣ0andf^ℳ be response of ℳ and f^ℳ′ be the responses of ℳ′. Then(11)f^ℳ=σℳ°rℳ=σℳ′°b°rℳ=σℳ′°b°rℳ=σℳ′°rℳ′=f^ℳ′.
Hence responses ofℳ and ℳ′ are identical.Figure 29
Commutative diagrams for Proposition17.Proposition 18.
The responsef^ℳ of a ℳ=Q,Σ0,δℳ,q0,βℳ∈CDFMAΣ0 is a MDYNΣ0⊕-morphism f^ℳ:1×Σ0⊕,δ1⟶L˜Σ0⊕,δL˜.Proof.
Follows from commuting diagrams in Figure30. The commutativity of diagrams in Figure 30 follows from the fact that f^ℳ=σℳ°rℳ, where rℳ:1×Σ0⊕,δ1⟶Q,δℳ and σℳ:Q,δℳ⟶L˜Σ0⊕,δL˜ are MDYNΣ0⊕-morphisms.Figure 30
Commutative diagrams for Proposition18.Proposition 19.
Leth:Q,δℳ⟶Q′,δℳ′ be a morphism of MDYNΣ0⊕, ζ:Q⟶hQ,ξ:hQ⟶Q′ be an onto map, ξ be a one-one map, and h=ξ°ζ. Then, ∃ a unique object hQ,δ″ of MDYNΣ0⊕ satisfying ζ:Q,δℳ⟶hQ,δ″ is an epimorphism in MDYNΣ0⊕ and ξ:hQ,δ″⟶Q′,δℳ′ is a monomorphism in MDYNΣ0⊕.Proof.
Ash=ξ°ζ, ∃ a MDYNΣ0⊕-object hQ,δ″ such that ξ:hQ,δ″⟶Q′,δℳ′ is a monomorphism and γ:Q,δℳ⟶hQ,δ″ is a epimorphism making the diagrams in Figure 31 commute.
The combativeness of SquareA in Figure 31 implies ζ is a morphism of MDYNΣ0⊕, while the commutativieness of Square B in Figure 31 implies ξ is a morphism of MDYNΣ0⊕. Whereby, ζ and ξ are a MDYNΣ0⊕-epimorphism and a MDYNΣ0⊕-monomorphism, respectively.Figure 31
Commutative diagrams for Proposition19.Proposition 20.
Letℳ1=Q1,Σ0,δℳ1,q0,βℳ1,ℳ2=Q2,Σ0,δℳ2,q0′,βℳ2 and ℳ3=Q3,Σ0,δℳ3,q0″,βℳ3∈CDFMAΣ0. Let k:Q1⟶Q2 and h:Q2⟶Q3 be the maps with property that k:Q1,δ1⟶Q2,δ2 and h°k:Q1,δ1⟶Q3,δ3 are MDYNΣ0⊕-morphism. Then, if k is onto, h:Q2,δ2⟶Q3,δ3 be a MDYNΣ0⊕-morphism.Proof.
Letk:Q1,δℳ1⟶Q2,δℳ2 and h°k:Q1,δℳ1⟶Q3,δℳ3 be MDYNΣ0⊕-morphisms. Then the upper Square (A) of diagram in Figure 32 and diagram in Figure 33 (i.e., the outer diagram of Figure 32) commute.
To show thath:Q2,δℳ2⟶Q3,δℳ3 is a morphism of MDYNΣ0⊕, we need to show that lower Square (B) in Figure 32 must commutes.
Now, letq′∈Q2 and α∈Σ0⊕. Then(12)δℳ3°h,idΣ0⊕q′,α=δℳ3°h,idΣ0⊕kq,αby ontoness of k∃q∈Q1such thatkq=q′=δℳ3h°k,idΣ0⊕q,α=h°k°δℳ1q,αsince diagam in Figure32commutes=hk°δℳ1q,α=hδℳ2°k,idΣ0⊕q,αsince SquareAin Figure33commutes=h°δ2kq,α=h°δ2q′,α.
Henceh:Q2,δℳ2⟶Q3,δℳ3 is a MDYNΣ0⊕-morphism.
Now, we need following from [80], for our next results.Figure 32
Commutative diagram for Proposition20.Figure 33
Commutative diagram for Proposition20.Proposition 21.
LetR,S,X,Y be arbitrary sets, e:R⟶S be an onto map and m:X⟶Y be an one-one map. Also, let the maps f:R⟶X and g:S⟶Y make the diagram in Figure 34 commutes.Then∃ a unique map k:S⟶X satisfying k°e=f and m°k=g.Figure 34
Diagram for Proposition21.Proposition 22.
Letℳ∈ CDFMA Σ0 and ℳ′∈ CDFMA Σ0 be reachable and coreachable realization of a response map f^. Then ∃ a unique morphism from ℳ to ℳ′ in CDFMA Σ0.Proof.
Letℳ=Q,Σ0,δℳ,q0,βℳ, ℳ′=Q′,Σ0,δℳ′,q0′,βℳ′∈CDFMAΣ0 having rℳ,rℳ′ as their reachability maps and σℳ,σℳ′ as their coreachability maps, respectively. Then, reachability of ℳ and coreachability of ℳ′ implies rℳ is onto and σℳ′ is one-one. So Proposition 21, ensure that ∃ a unique map b:Q⟶Q′ which make diagram in Figure 35 commutes.
Now, asrℳ and rℳ′=b°rℳ are morphisms of MDYNΣ0⊕ and rℳ is onto, b is a MDYNΣ0⊕-morphism (cf. Proposition 20). The fact that b is a morphism of CDFMA Σ0, follows from commutativity of square of the diagram in Figure 36.
bτ0=bq0=q0′=τ′0. Also, from Figure 36, σℳ′°b=σℳ and from Corollary 3, ε°σℳ′=βℳ′. Thus ε°σℳ′°b=βℳ′°b, or that, ε°σℳ=βℳ′°b. Again from Corollary 3, ε°σℳ=βℳ, whereby βℳ=βℳ′°b.Figure 35
Diagram for Proposition22.Figure 36
Diagram forCDFMAΣ0-morphism b Proposition 22.Proposition 23.
EveryMDYNΣ0⊕-morphism f^:1×Σ0⊕,δ1⟶L˜Σ0⊕,δL˜ has a minimal realization.Proof.
LetQf^ be a set such that rf^:1×Σ0⊕⟶Qf^ is an onto map, σf^:Qf^⟶L˜Σ0⊕ is a one-one map and f^=σf^°rf^. Then ∃ a unique MDYNΣ0⊕-object Qf^,δf^ such that the diagrams in Figure 37 commute,
i.e., bothrf^:1×Σ0⊕,δ1⟶Qf^,δf^ and σf^:Qf^,δf^⟶L˜Σ0⊕,δL˜ are MDYNΣ0⊕-morphisms. Now, define the maps τf^:1⟶Qf^ and βf^:Qf^⟶L˜ as shown in Figure 38.
Thenℳf^=Qf^,X0,δf^,qf^,βf^ is a CDFMAΣ0-object, where qf^=τf^0. Moreover, Corollaries 2 and 3, tells that rf^ is reachability map of ℳf^ and σf^ is coreachability map of ℳf^ and σf^, whereby σf^°rf^=f^. Thus ℳf^ is a realization of f^. Also, as rf^ is onto and σf^ is one-one, so ℳf^ is minimal realization for f^.
Let for fixed input setΣ0, RCDFMA Σ0 denotes reachable class of CDFMA Σ0-objects having morphisms same as morphism of CDFMA Σ0. Then RCDFMA Σ0 also form a category. It is obvious that RCDFMA Σ0 is a subcategory of CDFMA Σ0.
Now, Definition20 in addition with Proposition 22, tells that for a given MDYNΣ0⊕-morphism its minimal realization can have following interpretation.Figure 37
Commutative diagrams showingrf^ and σf^ are MDYNΣ0⊕ morphism.Figure 38
Commutative diagrams for Proposition23.Definition 26.
Given aMDYNΣ0⊕-morphism f^:1×Σ0⊕,δ1⟶L˜Σ0⊕,δL˜, a realization N of f^ is minimal if N∈RCDFMAΣ0 and for any other realization ℳ∈RCDFMAΣ0 of f^∃ a unique RCDFMAΣ0-morphism b:N⟶ℳ.
From the above definition, it is obvious that a minimal realization off^:1×Σ0⊕,δ1⟶L˜Σ0⊕,δL˜, a MDYNΣ0⊕-morphism, is a terminal object in the category RCDFMAΣ0. Also, as the terminal objects in a category are unique up to isomorphism.Proposition 24.
A minimal realizationN of response map f^ (whenever it exists) is unique up to isomorphism. In other words, if both N1=Q1,Σ0,δ1,q0,β1 and N2=Q2,Σ0,δ2,q0′,β2 are minimal realizations of response map f^, then ∃ a unique RCDFMAΣ0-morphism b1:N1⟶N2 and b2:N2⟶N1 such that b2°b1=idQ1 and b1°b2=idQ2.Finally, we conclude that:Proposition 25.
All minimal realizations for total response mapf^ (or equivalently fuzzy multiset language f) are isomorphic to the Nerode realization of fuzzy multiset language f=f^0Σ0.Proof.
Follows from Proposition22 and 23.Remark 12.
From the above proposition, it is clear that the minimal realizations obtained either through Brzozowski’s algorithm [78] or derivative of fuzzy multiset language [58] are isomorphic to Nerode realization of that fuzzy multiset language.


## 8. Conclusion

In this paper, we have introduced a general categorical framework for the realization theory of fuzzy multiset language. Specifically, we have studied the crisp deterministic fuzzy multiset automata and fuzzy multiset languages over bipointed sets and provided purely arrow theoretic categorical interpretation of several concepts associated with a crisp deterministic fuzzy multiset automaton and fuzzy multiset language. In between, we have shown that the reachability and coreachability maps of a CDFMAΣ0 can be viewed as a CDFMA Σ0, as well as MDYNΣ0⊕-morphisms rather than viewing them simply as a map. Furthermore, we have defined response map of CDFMA Σ0 and associated it with fuzzy multiset language, and viewed the response map of CDFMA Σ0 as a MDYNΣ0⊕-morphism and showed that every MDYNΣ0⊕-morphism has a minimal realization. Interestingly, it is shown here that the minimal realizations for a fuzzy multiset language are isomorphic to the Nerode realization of the fuzzy multiset language. In other words, the proposed theory (i) provides a platform to connect different minimal realization techniques (Brzozowski’s algorithm [78], derivative of fuzzy multiset language [58]), and (ii) leads us to conclude that whatsoever the algorithms or approaches used to construct the minimal realization, the resultant will be isomorphic to the Nerode realization.It is pertinent to mention that the study carried out herein is based on the structure which generalizes the theory of ordinary fuzzy sets. As ordinary fuzzy representation provides a limited platform for approximating the meaning of words and is not able to capture linguistic uncertainty, a formal interval type-2 fuzzy model of computing with words by generalizing the existing ordinary fuzzy sets-based model to an interval type-2 fuzzy environment has been studied in [83]. Further, interval type-3 fuzzy sets [84] introduced recently have been shown superior because the upper and lower bound of the footprint-of-uncertainty are not constant but fuzzy sets. Also, the secondary membership in such fuzzy sets is an interval type-2 fuzzy set, whereas it is an ordinary fuzzy set in the case of type-2 fuzzy sets. Such advancement in the theory of fuzzy sets may be used further to enrich the proposed study of this paper.



---

*Source: 2798898-2022-07-30.xml*