Conference Papers Year : 2016

On Finite Monoids of Cellular Automata

Alonso Castillo-Ramirez
  • Function : Author
  • PersonId : 998314
Maximilien Gadouleau
  • Function : Author
  • PersonId : 982315

Abstract

For any group G and set A, a cellular automaton over G and A is a transformation τ:AGAG defined via a finite neighbourhood SG (called a memory set of τ) and a local function μ:ASA. 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)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 VCA(G;A) such that CA(G;A)=ICA(G;A)V.

Fichier principal
Vignette du fichier
395687_1_En_8_Chapter.pdf (319) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

hal-01435036 , version 1 (13-01-2017)

Licence

Identifiers

Cite

Alonso Castillo-Ramirez, Maximilien Gadouleau. On Finite Monoids of Cellular Automata. 22th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2016, Zurich, Switzerland. pp.90-104, ⟨10.1007/978-3-319-39300-1_8⟩. ⟨hal-01435036⟩
147 View
77 Download

Share

  • More