Categories of quantale-valued fuzzy automata: determinization and minimization (Q2053055)

The paper introduces quantale-valued fuzzy automata and their category. Important subcategories of this category and functors between them are studied. In related works, studies were carried out on fuzzy automata and languages with membership values for different lattice structures. \textit{D. Qiu} [Sci. China, Ser. F. 44, No. 6, 419--429 (2001; Zbl 1125.68383); Sci. China, Ser. F. 45, No. 6, 442--452 (2002; Zbl 1161.68549)] established the fundamental structure of fuzzy automata and languages with membership values for a complete residue lattice. Fuzzy automata and languages with lattice-ordered monoid membership values were initiated by \textit{Y. Li} and \textit{W. Pedrycz} [Fuzzy Sets Syst. 156, No. 1, 68--92 (2005; Zbl 1083.68059)] and studied in [Fuzzy Sets Syst. 158, No. 13, 1423--1436 (2007; Zbl 1123.68063)]. In [\textit{R. Bělohlávek}, Inf. Sci. 143, No. 1-4, 205--209 (2002; Zbl 1018.68040)] and [\textit{J. Ignjatović} et al., Inf. Sci. 178, No. 1, 164-180 (2008; Zbl 1128.68047)] the problem of determinization of fuzzy automata was studied. The problem of minimizing fuzzy automata was studied in [\textit{H. Lei, Y. Li}, Inf. Sci. 177, No. 6, 1413--1421 (2007; Zbl 1109.68058)], [\textit{Y. Li} and \textit{W. Pedrycz}, Fuzzy Sets Syst. 158, No. 13, 1423--1436 (2007; Zbl 1123.68063)], [\textit{S.P. Tiwari} et al., J. Intell. Fuzzy Syst. 30, No. 2, 1057--1065 (2016; Zbl 1361.68127)], [\textit{L. Wu} and \textit{D. Qiu}, Fuzzy Sets Syst. 161, No. 12, 1635--1656 (2010); Zbl 1192.68426]. It is usually solved after the determination of the fuzzy automaton, as it is done in the refereed paper. Section 2 is devoted to quantale-valued fuzzy automata and its category. A quantale is a complete lattice \(Q=(Q, \vee, \wedge, 0, 1)\) with an associative binary operation \(*\) satisfying: \(q*(\vee_{i\in I}q_i)= \vee_{i\in I}(q*q_i)\), and \((\vee_{i\in I}q_i)*q= \vee_{i\in I}(q_i*q)\) for any set \(I\) and \(q, q_i\in Q\) for all \(i\in I\). [\textit{K. I. Rosenthal}, Quantales and their applications. Pitman Research Notes in Mathematics Series, 234. Harlow: Longman Scientific \& Technical; New York: John Wiley \& Sons, Inc. (1990; Zbl 0703.06007), Definition 2.1.1] The definition of a left \(Q\)-semimodule and a morphism of left \(Q\)-semimodules is introduced in [\textit{M.K. Dubey et al.}, ``On the cateogy of quantale-semimodules'' in: Progress in Advanced Computing and Intelligent Engineering. Advances in Intelligent Systems and Computing, vol. 714. Springer, Singapore (2019)]. These morphisms are called homomorphisms in the paper under review. The aper deals with commutative \(Q\), so the word left is omitted. The \(Q\)-semimodules and \(Q\)-semimodule homomorphisms form a category (Proposition 2.1). Definition 2.5. A \(Q\)-valued fuzzy automaton is a 5-tupe \({\mathcal A}= (M, \Sigma, \mu, \sigma, \tau)\), where \noindent (i) \(M\) is a \(Q\)-semimodule, called state semimodule,\\ (ii) \(\Sigma\) is set of input symbols, called input set,\\ (iii) \(\sigma, \tau: M\to Q\) are \(Q\)-valued maps, called \(Q\)-sets of initial states and final states respectively, and\\ (iv) \(\mu: M\times \Sigma\times M\to Q\), is a map called \(Q\)-valued transition map. The map \(\mu: M\times \Sigma \times M\to Q\) is exteded to the map \(\mu^*: M\times \Sigma^*\times M\to Q\). Let \({\mathcal A}= (M, \Sigma, \mu_{{\mathcal A}}, \sigma_{{\mathcal A}}, \tau_{{\mathcal A}})\) and \({\mathcal B}= (N, \Sigma, \mu_{{\mathcal B}}, \sigma_{{\mathcal B}}, \tau_{{\mathcal B}})\) be a \(Q\)-valued automata. A homomorphism from \({\mathcal A}\) to \({\mathcal B}\) is a \(Q\)-semimodule homomorphism \(\beta: M \to N\) such that \(\mu_{{\mathcal A}}\leq \mu_{{\mathcal B}}\circ (\beta\times I_{\Sigma}\times \beta)\), \(\sigma_{{\mathcal A}}\leq \sigma_{{\mathcal B}}\circ \beta\) and \(\tau_{{\mathcal A}}\leq \tau_{{\mathcal B}}\circ \beta\) (Definition 2.6). The \(Q\)-valued fuzzy automata and their homomorphisms form a category (Proposition 2.2). This category over a fixed input set \(\Sigma\) (or \(\Sigma^*\)) is denoted by \(QVFA(\Sigma)\) (corr. \(QVFA(\Sigma^*)\)). There exists a functor \(QVFA(\Sigma)\to QVFA(\Sigma^*)\) (Proposition 2.6) and a functor \(QVFA(\Sigma^*)\to QVFA(\Sigma)\) (Corollary 2.1). Section 3 is devoted to determinization of \(Q\)-valued fuzzy automata. Definition 3.1. A deterministic \(Q\)-valued fuzzy automaton \({\mathcal D}\) over a monoid \(\Sigma^*\) is a 4-tuple \({\mathcal D}= (M, \gamma, m_0, \lambda)\), where \\ (i) \(M\) is a \(Q\)-semimodule, called the state-semimodule.\\ (ii) \(\gamma: M\times \Sigma^*\to M\) is a map, called the state transition map.\\ (iv) \(\lambda: M\to Q\) is a Q-valued map, called Q-set of final states. (v) \(m_0\in M\) is fixed state called the initial state. (Item numbering missing number (iii).) Definition 3.3. Let \({\mathcal D}= (M, \Sigma^*, \gamma, m_0, \lambda)\) be a determiniseic \(Q\)-valued fuzzy automaton. A \(Q\)-valued fuzzy language \(\rho_m: \Sigma^*\to Q\) is said to be accepted by \({\mathcal D}\) in state \(m\) if \(\rho_m(u)= \lambda(\gamma(m,u))\), for all \(u\in \Sigma^*\). The \(Q\)-valued fuzzy language \(\rho\) accepted by \({\mathcal D}\) in state \(m_0\) is called the \(Q\)-valued fuzzy language accepted by \({\mathcal D}\). The designation \(DQVFA(\Sigma^*,\rho)\) indicates the full subcategory in \(DQVFA(\Sigma^*)\) consisting of objects having the fixed input monoid \(\Sigma^*\) accepting the \(Q\)-valued language \(\rho\) (Remark 3.2). Definition 3.4. Two deterministic \(Q\)-valued fuzzy automata \({\mathcal D}\) and \({\mathcal D}'\) are said to be equivalent if \(\rho_{{\mathcal D}}=\rho_{{\mathcal D}'}\). Algorithm 3.1 has been developed which, for a given \(Q\)-valued fuzzy automaton builds a deterministic \(Q\)-valued fuzzy automaton equivalent to it. The input of this algorithm is \({\mathcal A}= (M, \mu, \sigma, \tau)\in QVFA(\Sigma^*)\) and the output is \({\mathcal D}= (Q^M, \overline{\mu}, \sigma, \overline{\tau})\in DQVFA(\Sigma^*)\) such that \({\mathcal D}\) is equivalent to \({\mathcal A}\). In Section 4, using the notions of reachability and observability, the concept of constructing a minimal deterministic \(Q\)-valued fuzzy automaton corresponding to a given \({\mathcal D}\in DQVFA(\Sigma^*, \rho)\) is considered in a purely categorical form. Definition 4.1. (a) Let \({\mathcal D}= (M, \gamma, m_0, \lambda)\in DQVFA(M)\). The reachability map \(r\) of \({\mathcal D}\) is a map \(r: \Sigma^*\to M\) such that \\ \text{ } (i) \(r(e)= m_0\), \(e\) is an identity element of \(M\),\\ \text{ } (ii) \(r(uv)= \gamma(r(u),v)\), \(\forall u,v\in \Sigma^*\).\\ (b) \({\mathcal D}\) is called reachable, if \(r\) is onto. Definition 4.2. (a) \({\mathcal D}= (M, \gamma, m_0, \lambda)\in DQVFA(\Sigma^*)\), the observability map \(o\) of \({\mathcal D}\) is a map \(o: \to Q^{\Sigma^*}\) such that \(o(m) = \rho m, \forall m \in M\). (b) \({\mathcal D}\) is called observable if \(o\) is one-one. Let \(rDQVFA(\Sigma^*, \rho)\) be the full subcategory in \(DQVFA(\Sigma^*, \rho)\) consisting of reachable automata, and \(oDQVFA(\Sigma^*, \rho)\) be the full subcategory in \(DQVFA(\Sigma^*, \rho)\) consisting of observable automata. Denote \(mDQVFA(\Sigma^*, \rho):= rDQVFA(\Sigma^*, \rho)\cap oDQVFA(\Sigma^*, \rho)\). Object class inclusions gives the following diagram of full category embeddings: \[ \begin{matrix} DQVGA(\Sigma^*, \rho) & \overset{I_2}{\leftarrow} & oDQVFA(\Sigma^*, \rho) \\ { I_1} \uparrow & & \uparrow I_3\\ rDQVFA(\Sigma^*, \rho) & \overset{I_4}{\leftarrow} & mDQVFA(\Sigma^*, \rho) \end{matrix} \] It follows from Proposition 4.2 and Proposition 4.3 that all these embeddings have right adjoint functors. It is concluded that the composition assigns to each deterministic fuzzy automaton \(A\) a terminal object in a slice category \(I\downarrow A\). Theorem 4.1. For each \({\mathcal D}\in DQVGA(\Sigma^*, \rho)\) there exists a minimal deterministic \(Q\)-valued fuzzy automation. To construct a category of minimal deterministic quantale-valued fuzzy automata \(mDQVFA(\Sigma^*, \rho)\), the following minimization algorithm is given: \(DQVFA(\Sigma^*, \rho) \xrightarrow{R} rDQVFA(\Sigma^*, \rho) \xrightarrow{O} mDQVFA(\Sigma^*, \rho)\). Here \(R\) and \(O\) are right adjoint to inclusion functors. The order of execution of \(R\) and \(O\) can be changed.