Induced permutation automata and coverings of strongly connected automata (Q1283800)

An automaton \(\mathcal A\) is a triple \((S,\Sigma,\delta)\) where \(S\) is a finite non-empty set of states, \(\Sigma\) is a finite non-empty alphabet and \(\delta\colon S\times\Sigma\to S\) is a mapping. Let \(\delta^*\colon S\times\Sigma^*\to S\) denote the extension of \(\delta\) with \(\delta^*(s,\alpha\beta)=\delta^*(\delta^*(s,\alpha),\beta)\) for all \(s\in S\) and all \(\alpha ,\beta\in\Sigma^*\). An automaton is strongly connected if for any pair \((s,t)\in S\times S\) there exists \(\alpha\in\Sigma^*\) with \(\delta^*(s,\alpha)=t\). A family \(\pi=\{H_i\}_{i\in I}\) of subsets of \(S\) is an admissible system if for every \(\sigma\in\Sigma\) and every \(i\in I\) there exists \(j\in I\) with \(\{\delta(x,\sigma)\mid x\in H_i\}\subseteq H_j\). We say that an automaton \((\pi,\Sigma,\delta')\) is a generalized factor automaton of \(\mathcal A\) by \(\pi\) if \(\{\delta(x,\sigma)\mid x\in H_i\}\subseteq\delta'(H_i,\sigma)\) for all \(\sigma\in\Sigma\) and all \(H_i\in\pi\). The set \({\mathcal S}({\mathcal A})=\{\delta^*(-,\alpha)\colon S\to S\mid\alpha\in\Sigma^*\}\) is closed under composition and thus it is a semigroup. For a minimal idempotent \(e\) of \({\mathcal S}({\mathcal A})\), an automaton \((Se,e{\mathcal S}({\mathcal A})e,\delta')\) such that \(\delta'(se,efe)=sefe\) is called an induced permutation automaton of \(\mathcal A\). An automaton \((S_1\times S_2,\Sigma_2,\delta_3)\) is a cascade product of automata \((S_1,\Sigma_1,\delta_1)\) and \((S_2,\Sigma_2,\delta_2)\) with respect to a mapping \(\omega\colon S_2\times\Sigma_2\to S_1\) if \(\delta_3((s_1,s_2),\sigma)=(\delta_1(s_1,\omega(s_2,\sigma)),\delta_2(s_2,\sigma))\) for all \(\sigma\in\Sigma\) and all \((s_1,s_2)\in S_1\times S_2\). An automaton \((S_1,\Sigma,\delta_1)\) covers an automaton \((S_2,\Sigma,\delta_2)\) if there exists a surjective mapping \(\varphi\colon S_1\to S_2\) with \(\varphi(\delta_1(s,\sigma))=\delta_2(\varphi(s),\sigma)\) for all \(s\in S_1\) and all \(\sigma\in\Sigma\). The following modification of classical Krohn-Rhodes theorem is proved: Let \({\mathcal A}=(S,\Sigma,\delta)\) be a strongly connected automaton. Then \(\pi=\{Se\}\) where \(e\) is taken over all minimal idempotents of \({\mathcal S}({\mathcal A})\) is an admissible system of \(\mathcal A\) and \(\mathcal A\) is covered by a cascade product of an induced permutation automaton of \(\mathcal A\) and a generalized factor automaton of \(\mathcal A\) by \(\pi\).