Transformation of an automaton group under the action of a~feedback operation that admits more than two values

V. D. Anosov

Diskretnaya Matematika, Tome 3 (1991) no. 4, pp. 47-51.

Résumé

The main result of the paper is that for any transitive permutation group $G$ there exists a connected permutational automaton $\mathfrak A$ with an interior group $G$ from which the multiple application of a feedback operation [B. V. Kudryavtsev, S. V. Aleshin and A. S. Podkolzin, Introduction to the theory of automata (Russian), “Nauka”, Moscow, 1985; RZhMat 1986:4 G45K], defined by a function that admits more than two values, can produce an automaton with an interior group coinciding with an arbitrary given subgroup of the group of all permutations of the state set of the automaton $\mathfrak A$. The validity of the statement for the group $G\neq Z_p$ – a cyclic group of prime order – can be obtained from a result of a paper of V. I. Malygin [Diskret. Mat. 2 (1990), no. 3, 81–89; RZhMat 1991:2 G407], in which he considered the case of using a feedback function that admits two values. Note that in this case for $\mathbb Z_p$ the statement does not hold: from an automaton with an interior group $\mathbb Z_p$, by applying a feedback operation given by a function that admits two values, one can obtain only automata with an interior group coinciding with $\mathbb Z_p$ or with the unit group. At the expense of using the possibility of a feedback function to have more than two values, we give a uniform proof of the validity of the above-mentioned statement for an arbitrary transitive group $G$ that is simpler than the proof of the statement when $G\ne\mathbb Z_p$ from the above-mentioned paper of Malygin.