On multistochastic automata

From MaRDI portal





A multistochastic automaton \(A = (S,\{M_1,\ldots, M_k\},\pi,f)\) is a generalization of a finite probabilistic automaton, where several transition functions \((M_1,\ldots,M_k)\) are allowed and the transition matrices \(M_i(\lambda)\) for the empty word need not be identity matrices \(E\). The multistochastic language \(L(A,\eta)\) accepted by \(A\) with a cut-point \(\eta\) is defined as follows. For each word \(P\in I^*\), denote \[ \eta(P) =\mathrm{lub}\left\{\pi M_{i_1}(y_1)M_{i_2}(y_2)\ldots M_{i_r}(y_r) f\mid P=y_1\ldots y_r,\;y_j\in I\cup\{\lambda\}\right\}. \] Then \(L(A,\eta) = \{P\in I^*\mid \eta(p)>\eta\}\). Denote by \(\mathcal L_i^\lambda\) the family of all languages of this form with \(k=i\). If it is required that \(M_1(\lambda),\ldots,M_i(\lambda)\) are deterministic then the corresponding subfamily \(\mathcal L_i^\lambda\) is denoted by \(\mathcal L_{\text{id}}^\lambda\). Moreover, if \(M_1(\lambda)=\ldots=M_i(\lambda) =E\), then we obtain a subfamily of \(\mathcal L_{\text{id}}^\lambda\) denoted by \(\mathcal L_i\). Let \(\mathcal L=\bigcup_{i=1}^\infty \mathcal L_i\) and \(\mathcal L^\lambda=\bigcup_{i=1}^\infty \mathcal L_i^\lambda\). It is proved that \[ \mathcal L_1\subset\mathcal L_2\subseteq\mathcal L\subseteq\mathcal L_{\text{id}}^\lambda\subseteq\mathcal L_1^\lambda\subseteq\mathcal L_2^\lambda=\mathcal L^\lambda \] where the first inclusion is proper. (Note that \(\mathcal L_1\) is the family of all stochastic languages. In a forthcoming paper we shall show that \(\mathcal L=\mathcal L_{\text{id}}^\lambda=\mathcal L_i^\lambda\) for any \(i\).) It is proved that \(\mathcal L^\lambda\) \((\mathcal L)\) is closed under (\(\lambda\)-free) regular substitutions and, hence, under (\(\lambda\)-free) homomorphisms. (We have proved earlier [Ann. Univ. Turku., Ser. A I 133, 6 p. (1970; Zbl 0188.33303)] that the family \(\mathcal L_1\) of all stochastic languages is not closed under \(\lambda\)-free homomorphisms.) Moreover, it is established that \(\mathcal L^\lambda\) \((\mathcal L)\) is the family of all homomorphic images (under \(\lambda\)-free homomorphisms) of all stochastic languages. In fact, every language in \(\mathcal L^\lambda\) \((\mathcal L)\) is obtained from a stochastic language by deleting the occurrence of two letters (one letter). Several closure properties of the above families are established. Finally, it is proved that \(\mathcal L_i^\lambda\) \((\mathcal L_i)\) is the family of the output languages of all asynchronous stochastic sequential machines with \(i\) inputs (where \(\lambda\) is not allowed as an output).











This page was built for publication: On multistochastic automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5678783)