On Finite Monoids of Cellular Automata

摘要

For any group G and set A, a cellular automaton over G and A is a transformation r : A~G → A~G defined via a finite neighbourhood S is contained in G (called a memory set of τ) and a local function μ : A~S → A. In this paper, we assume that G and A are both finite and study various algebraic properties of the finite monoid CA(G, A) consisting of all cellular automata over G and A. Let ICA(G; A) be the group of invertible cellular automata over G and A. In the first part, using information on the conjugacy classes of subgroups of G, we give a detailed description of the structure of ICA(G; A) in terms of direct and wreath products. In the second part, we study generating sets of CA(G; A). In particular, we prove that CA(G, A) cannot be generated by cellular automata with small memory set, and, when G is finite abelian, we determine the minimal size of a set V is contained in CA(G; A) such that CA(G; A) = 〈ICA(G; A)∪V〉.