On Finite Monoids of Cellular Automata

Castillo-Ramirez, Alonso; Gadouleau, Maximilien

doi:10.1007/978-3-319-39300-1_8

On Finite Monoids of Cellular Automata

Castillo-Ramirez, Alonso; Gadouleau, Maximilien

Authors

Alonso Castillo-Ramirez

Dr Maximilien Gadouleau m.r.gadouleau@durham.ac.uk
Associate Professor

Contributors

Matthew Cook
Editor

Turlough Neary
Editor

Abstract

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

Citation

Castillo-Ramirez, A., & Gadouleau, M. (2016). On Finite Monoids of Cellular Automata. In M. Cook, & T. Neary (Eds.), Cellular automata and discrete complex systems : 22nd IFIP WG 1.5 International Workshop, AUTOMATA 2016, Zurich, Switzerland, June 15-17, 2016. Proceedings (90-104). https://doi.org/10.1007/978-3-319-39300-1_8

Conference Name	International workshop on cellular automata and discrete complex systems
Conference Location	Zurich, Switzerland
Start Date	Jun 15, 2016
End Date	Jun 17, 2016
Acceptance Date	Mar 20, 2016
Online Publication Date	Jun 2, 2016
Publication Date	Jun 2, 2016
Deposit Date	Nov 28, 2016
Publicly Available Date	Jun 2, 2017
Pages	90-104
Series Title	Lecture notes in computer science
Series Number	9664
Series ISSN	0302-9743,1611-3349
Book Title	Cellular automata and discrete complex systems : 22nd IFIP WG 1.5 International Workshop, AUTOMATA 2016, Zurich, Switzerland, June 15-17, 2016. Proceedings.
ISBN	9783319392998
DOI	https://doi.org/10.1007/978-3-319-39300-1_8
Public URL	https://durham-repository.worktribe.com/output/1149278