On the finiteness problem for automaton (semi)groups. (Q6828981)

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.