Publication details for Dr Maximilien GadouleauCastillo-Ramirez, Alonso & Gadouleau, Maximilien (2016), On Finite Monoids of Cellular Automata, in Cook, Matthew & Neary, Turlough eds, Lecture Notes in Computer Science, 9664 International workshop on cellular automata and discrete complex systems. Zurich, Switzerland, Springer, 90-104.
- Publication type: Conference Paper
- ISSN/ISBN: 9783319392998, 9783319393001, 0302-9743
- DOI: 10.1007/978-3-319-39300-1_8
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
Author(s) from Durham
For any group G and set A, a cellular automaton over G and A is a transformation τ:AG→AGτ:AG→AG defined via a finite neighbourhood S⊆GS⊆G (called a memory set of ττ) and a local function μ:AS→Aμ:AS→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)CA(G,A) consisting of all cellular automata over G and A. Let ICA(G;A)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)ICA(G;A) in terms of direct and wreath products. In the second part, we study generating sets of CA(G;A)CA(G;A). In particular, we prove that CA(G,A)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⊆CA(G;A)V⊆CA(G;A) such that CA(G;A)=⟨ICA(G;A)∪V⟩CA(G;A)=⟨ICA(G;A)∪V⟩.