Since first introduced by John von Neumann, the notion of cellular automaton has grown into audkey concept in computer science, physics and theoretical biology. In its classical setting, a cellularudautomaton is a transformation of the set of all configurations of a regular grid such that the imageudof any particular cell of the grid is determined by a fixed local function that only depends on a fixedudfinite neighbourhood. In recent years, with the introduction of a generalised definition in terms ofudtransformations of the form τ : AG → AG (where G is any group and A is any set), the theory ofudcellular automata has been greatly enriched by its connections with group theory and topology. Inudthis paper, we begin the finite semigroup theoretic study of cellular automata by investigating theudrank (i.e. the cardinality of a smallest generating set) of the semigroup CA(Zn; A) consisting ofudall cellular automata over the cyclic group Zn and a finite set A. In particular, we determine thisudrank when n is equal to p, 2k or 2kp, for any odd prime p and k ≥ 1, and we give upper and lowerudbounds for the general case.
展开▼
