# On Finite Monoids of Cellular Automata

Abstract : For any group G and set A, a cellular automaton over G and A is a transformation $\tau :{A}^{G}\to {A}^{G}$ defined via a finite neighbourhood $S\subseteq G$ (called a memory set of $\tau$) and a local function $\mu :{A}^{S}\to A$. In this paper, we assume that G and A are both finite and study various algebraic properties of the finite monoid $\mathrm{C}\mathrm{A}\left(G,A\right)$ consisting of all cellular automata over G and A. Let $\mathrm{I}\mathrm{C}\mathrm{A}\left(G;A\right)$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 $\mathrm{I}\mathrm{C}\mathrm{A}\left(G;A\right)$ in terms of direct and wreath products. In the second part, we study generating sets of $\mathrm{C}\mathrm{A}\left(G;A\right)$. In particular, we prove that $\mathrm{C}\mathrm{A}\left(G,A\right)$ 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\subseteq \mathrm{C}\mathrm{A}\left(G;A\right)$ such that $\mathrm{C}\mathrm{A}\left(G;A\right)=⟨\mathrm{I}\mathrm{C}\mathrm{A}\left(G;A\right)\cup V⟩$.
Keywords :
Type de document :
Communication dans un congrès
Matthew Cook; Turlough Neary. 22th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2016, Zurich, Switzerland. Lecture Notes in Computer Science, LNCS-9664, pp.90-104, 2016, Cellular Automata and Discrete Complex Systems. 〈10.1007/978-3-319-39300-1_8〉
Domaine :

Littérature citée [12 références]

https://hal.inria.fr/hal-01435036
Contributeur : Hal Ifip <>
Soumis le : vendredi 13 janvier 2017 - 15:24:12
Dernière modification le : jeudi 19 juillet 2018 - 16:58:10
Document(s) archivé(s) le : vendredi 14 avril 2017 - 20:30:52

### Fichier

##### Accès restreint
Fichier visible le : 2019-01-01

Connectez-vous pour demander l'accès au fichier

### Citation

Alonso Castillo-Ramirez, Maximilien Gadouleau. On Finite Monoids of Cellular Automata. Matthew Cook; Turlough Neary. 22th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2016, Zurich, Switzerland. Lecture Notes in Computer Science, LNCS-9664, pp.90-104, 2016, Cellular Automata and Discrete Complex Systems. 〈10.1007/978-3-319-39300-1_8〉. 〈hal-01435036〉

### Métriques

Consultations de la notice