We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Computer Science


Publication details for Dr Maximilien Gadouleau

Castillo-Ramirez, Alonso & Gadouleau, Maximilien (2016). Ranks of finite semigroups of one-dimensional cellular automata. Semigroup Forum 93(2): 347-362.

Author(s) from Durham


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