Automata with restricted memory and shift endomorphisms (Q2754789)

Every automaton transformation \(\pi\) over an alphabet \(X\) can be defined by its table of the form \(u_\pi=[\sigma_1,\sigma_2(x_1),\sigma_3(x_1,x_2),\dots]\), where \(\sigma_1\in T_X\), \(\sigma_i(\overline x_{i-1})=\sigma_i(x_1,\dots, x_{i-1})\in (T_X)^{X^{i-1}}\) (\(i>1\)), and \(T_X\) is the semigroup of all everywhere defined transformations on the symbols of \(X\) (see \textit{O. G. Ganyushkin} and \textit{V. I. Sushchanskij} [Dopov. Nats. Akad. Nauk Ukr., Mat. Pryr. Tekh. Nauky 1998, No. 6, 15-18 (1998; Zbl 0931.18003)]). If the \(k\)-th coordinate \(\sigma_k(\overline x_{k-1})\) of the table \(u_\pi\) depends explicitly only on the variables \(x_{k-n-1},x_{k-n},\dots,x_{k-1}\), then the automaton transformation is said to have memory of volume \(n\). The authors prove that the set \(AF(X)\) of all automaton transformations over the alphabet \(X\) with finite memory (i.e. with memory \(n\) for any \(n\)) and the set \(AU(X)\) of all uniform automaton transformations are subsemigroups of the semigroup of all automaton transformations over the alphabet \(X\). It is shown that the semigroup \(AF(X)\) acts transitively on the set of all \(\omega\)-words (infinite to the right) and on each set of all words of the same length. It is also proved that the semigroup \(AF(X)\) (in particular \(AU(X)\)) is residually finite and contains free subgroups of arbitrary finite rank. The semigroup of shift endomorphisms is also considered and some results about its subsemigroup of all endomorphisms without memory are obtained.