On the finiteness problem for automaton (semi)groups.
By a Mealy automaton the authors mean a quadruple \((A,\Sigma,\delta,\rho)\) where \(A\) and \(\Sigma\) are finite non-empty states (called, respectively, the state set and the alphabet) and \(\delta\colon A\times\Sigma\to A\) and \(\rho\colon A\times\Sigma\to\Sigma\) are totally defined functions. If \(\mathcal A=(A,\Sigma,\delta,\rho)\) is a Mealy automaton, then each state \(x\in A\) defines the function \(\rho_x\colon\Sigma\to\Sigma\) by \(\rho_x(i)=\rho(x,i)\) and each letter \(i\in\Sigma\) defines the function \(\delta_i\colon A\to A\) by \(\delta_i(x)=\delta(x,i)\). The function \(\rho_x\) extends to \(\Sigma^*\) in a natural way: if \(i\in\Sigma\) and \(u\in\Sigma^*\), then \(\rho_x(iu)=\rho_x(i)\rho_{\delta_i(x)}(u)\). The semigroup of all mappings from \(\Sigma^*\) to \(\Sigma^*\) generated by all the functions \(\rho_x\) with \(x\in A\) is called the semigroup of \(\mathcal A\) and is denoted by \(\langle\mathcal A\rangle_+\). If all functions \(\rho_x\colon\Sigma\to\Sigma\) happen to be bijective, the group of all mappings from \(\Sigma^*\) to \(\Sigma^*\) generated by the extensions of \(\rho_x\)'s with \(x\in A\) to \(\Sigma^*\) is called the group of \(\mathcal A\) and is denoted by \(\langle\mathcal A\rangle\).\N\N The authors study the following finiteness problem: given a Mealy automaton, determine whether its (semi)group is finite.\N\N If \(\mathcal A=(A,\Sigma,\delta,\rho)\) is a Mealy automaton, its dual \(\mathfrak d(\mathcal A)\) is the Mealy automaton obtained by switching the roles of \(A\) and \(\Sigma\). \textit{D. Savchuk} and \textit{Y. Vorobets} [J. Algebra 336, No. 1, 53-66 (2011; Zbl 1239.20032)] have shown that the semigroup \(\langle\mathcal A\rangle_+\) is finite if and only if so is the semigroup \(\langle\mathfrak d(\mathcal A)\rangle_+\). The authors observe that the minimization of a Mealy automaton does not change its semigroup but the minimization of an automaton with a minimal dual can make the dual automaton non-minimal. Therefore they suggest alternatingly minimize and dualize a given automaton until both the resulting automaton and its dual become minimal. If this process leads to the automaton with one state over a one-letter alphabet, then the semigroup of the initial automaton is finite. This sufficient condition for finiteness is not necessary but its implementation has allowed the authors to establish finiteness for a number of automaton semigroups whose analysis was not possible with previously known finiteness conditions.\N\N The helix graph of a Mealy automaton \(\mathcal A=(A,\Sigma,\delta,\rho)\) is the directed graph with nodes \(A\times\Sigma\) and arcs \((x,i)\to(\delta_i(x),\rho_x(i))\) for all \((x,i)\). The authors show that if all functions \(\rho_x\) and \(\delta_i\) are bijective and the group \(\langle\mathcal A\rangle\) is finite, then the helix graph of \(\mathcal A\) must be a union of disjoint cycles. This necessary condition for finiteness is not sufficient but again its implementation has proved to be superior over previously known finiteness conditions.
This page was built for publication: On the finiteness problem for automaton (semi)groups.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6828981)
