Ranks of finite semigroups of one-dimensional cellular automata (Q343476)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Ranks of finite semigroups of one-dimensional cellular automata |
scientific article |
Statements
Ranks of finite semigroups of one-dimensional cellular automata (English)
0 references
28 November 2016
0 references
A cellular automaton over a group \(G\) and a set \(A\) is a mapping \(A^G\to A^G\) which is determined by the action of \(G\) on itself by right multiplication within a fixed finite neighborhood. Such cellular automata constitute a semigroup \(\mathrm{CA}(G;A)\) under composition of mappings. When both \(G\) and \(A\) are finite, which is the case of interest in the paper, \(\mathrm{CA}(G;A)\) is the centralizer of a certain set of transformations of \(A^G\). The aim of the paper is to compute the rank, in the sense of the minimum cardinality of a generating set, for the semigroups \(\mathrm{CA}(G;A)\) when \(G=\mathbb{Z}_n\) is a cyclic group. Explicit formulas are established when \(n\) is a prime, a power of 2, or a power of 2 times a prime, while lower and upper bounds are given in the general case.
0 references
cellular automata
0 references
finite semigroups
0 references
smallest generating set
0 references