%0 Conference Proceedings
%T Bounding the Minimal Number of Generators of Groups and Monoids of Cellular Automata
%+ Centro Universitario de Ciencias Exactas e Ingenierías (CUCEI)
%A Castillo-Ramirez, Alonso
%A Sanchez-Alvarez, Miguel
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 25th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA)
%C Guadalajara, Mexico
%Y Alonso Castillo-Ramirez
%Y Pedro P. B. de Oliveira
%I Springer International Publishing
%3 Cellular Automata and Discrete Complex Systems
%V LNCS-11525
%P 48-61
%8 2019-06-26
%D 2019
%R 10.1007/978-3-030-20981-0_4
%K Monoid of cellular automata
%K Invertible cellular automata
%K Minimal number of generators
%Z Computer Science [cs]Conference papers
%X 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.
%G English
%Z TC 1
%Z WG 1.5
%2 https://inria.hal.science/hal-02312616/document
%2 https://inria.hal.science/hal-02312616/file/484947_1_En_4_Chapter.pdf
%L hal-02312616
%U https://inria.hal.science/hal-02312616
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-WG1-5
%~ IFIP-AUTOMATA
%~ IFIP-LNCS-11525