Bounding the Minimal Number of Generators of Groups and Monoids of Cellular Automata - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2019

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

Résumé

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.
Fichier principal
Vignette du fichier
484947_1_En_4_Chapter.pdf (305.95 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02312616 , version 1 (11-10-2019)

Licence

Paternité

Identifiants

Citer

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⟩
39 Consultations
8 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More