Automaton semigroups: the two-state case. (Q290910)

A Mealy automaton \((A,\Sigma,\delta=(\delta_i\colon A\to A)_{i\in\Sigma},\rho=(\rho_x\colon\Sigma\to\Sigma)_{x\in A})\) is invertible if the output functions \(\rho_x\) are permutations of the input-output alphabet \(\Sigma\) and reversible if the state transition functions \(\delta_i\) are permutations of the set of states \(A\). The output functions \(\rho_x\), \(x\in A\), can in natural way be extended to mappings \(\Sigma^*\to\Sigma^*\); it is proved, that the semigroup of a two-state reversible Mealy automaton generated by these mappings is either finite or free; for invertible automaton is presented also an effective decision procedure.