We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

On finite monoids of cellular automata.

Castillo-Ramirez, Alonso and Gadouleau, Maximilien (2016) 'On finite monoids of cellular automata.', in Cellular automata and discrete complex systems : 22nd IFIP WG 1.5 International Workshop, AUTOMATA 2016, Zurich, Switzerland, June 15-17, 2016. Proceedings. Cham: Springer, pp. 90-104. Lecture notes in computer science. (9664).


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⟩.

Item Type:Book chapter
Full text:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Publisher statement:The final publication is available at Springer via
Date accepted:20 March 2016
Date deposited:29 November 2016
Date of first online publication:02 June 2016
Date first made open access:02 June 2017

Save or Share this output

Look up in GoogleScholar