# Bounding the Minimal Number of Generators of Groups and Monoids of Cellular Automata

Abstract : For a group G and a finite set A, denote by $\mathrm {CA}(G;A)$ the monoid of all cellular automata over $A^G$ and by $\mathrm {ICA}(G;A)$ its group of units. We study the minimal cardinality of a generating set, known as the rank, of $\mathrm {ICA}(G;A)$. In the first part, when G is a finite group, we give upper bounds for the rank in terms of the number of conjugacy classes of subgroups of G. The case when G is a finite cyclic group has been studied before, so here we focus on the cases when G is a finite dihedral group or a finite Dedekind group. In the second part, we find a basic lower bound for the rank of $\mathrm {ICA}(G;A)$ when G is a finite group, and we apply this to show that, for any infinite abelian group H, the monoid $\mathrm {CA}(H;A)$ is not finitely generated. The same is true for various kinds of infinite groups, so we ask if there exists an infinite group H such that $\mathrm {CA}(H;A)$ is finitely generated.
Keywords :
Document type :
Conference papers
Domain :

Cited literature [12 references]

https://hal.inria.fr/hal-02312616
Contributor : Hal Ifip <>
Submitted on : Friday, October 11, 2019 - 11:33:51 AM
Last modification on : Friday, October 11, 2019 - 11:39:23 AM

### File

##### Restricted access
To satisfy the distribution rights of the publisher, the document is embargoed until : 2022-01-01

### Citation

Alonso Castillo-Ramirez, Miguel Sanchez-Alvarez. Bounding the Minimal Number of Generators of Groups and Monoids of Cellular Automata. 25th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2019, Guadalajara, Mexico. pp.48-61, ⟨10.1007/978-3-030-20981-0_4⟩. ⟨hal-02312616⟩

Record views