Elementary, Finite and Linear vN-Regular Cellular Automata
Alonso Castillo-Ramirez and Maximilien Gadouleau

arXiv:1804.00511v1 [] 22 Mar 2018

April 3, 2018

Abstract
Let G be a group and A a set. A cellular automaton (CA) τ over AG is von Neumann
regular (vN-regular) if there exists a CA σ over AG such that τ στ = τ , and in such case,
σ is called a generalised inverse of τ . In this paper, we investigate vN-regularity of various
kinds of CA. First, we establish that, over any nontrivial configuration space, there always
exist CA that are not vN-regular. Then, we obtain a partial classification of elementary
vN-regular CA over {0, 1}Z; in particular, we show that rules like 128 and 254 are vNregular (and actually generalised inverses of each other), while others, like the well-known
rules 90 and 110, are not vN-regular. Next, when A and G are both finite, we obtain a full
characterisation of vN-regular CA over AG . Finally, we study vN-regular linear CA when
A = V is a vector space over a field F; we show that every vN-regular linear CA is invertible
when V = F and G is torsion-free elementary amenable (e.g. when G = Zd , d ∈ N), and
that every linear CA is vN-regular when V is finite-dimensional and G is locally finite with
char(F) ∤ o(g) for all g ∈ G.
Keywords: Cellular automata, elementary cellular automata, finite cellular automata, linear cellular automata, monoids, von Neumann regularity, generalised inverse.

1

Introduction

In this paper we follow the general setting for cellular automata (CA) presented in [7]. For any
group G and any set A, the configuration space AG is the set of all functions from G to A. A
cellular automaton over AG is a transformation of AG defined via a finite memory set and a
local function (see Definition 2 for the precise details). Most of the classical literature on CA
focus on the case when G = Zd , for d ≥ 1, and A is a finite set (see [14]), but important results
have been obtained for larger classes of groups (e.g., see [7] and references therein).
Recall that a semigroup is a set equipped with an associative binary operation, and that a
monoid is a semigroup with an identity element. If M is a group, or a monoid, write K ≤ M
if K is a subgroup, or a submonoid, of M , respectively.
Let CA(G; A) be the set of all CA over AG . It turns out that, equipped with the composition
of functions, CA(G; A) is a monoid. In this paper we apply functions on the right; hence, for
τ, σ ∈ CA(G; A), the composition τ ◦ σ, denoted simply by τ σ, means applying first τ and then
σ.
A cellular automaton τ ∈ CA(G; A) is invertible, or reversible, or a unit, if there exists
σ ∈ CA(G; A) such that τ σ = στ = id. In such case, σ is called the inverse of τ and denoted
by σ = τ −1 . When A is finite, it may be shown that τ ∈ CA(G; A) is invertible if and only if it
is a bijective function (see [7, Theorem 1.10.2]). Denote the set of all invertible CA over AG by
ICA(G; A); this is in fact a group, called the group of units of CA(G; A).
We shall consider the notion of regularity that, as cellular automata, was introduced by
John von Neumann, and has been widely studied in both semigroup and ring theory. A cellular
automaton τ ∈ CA(G; A) is von Neumann regular (vN-regular) if there exists σ ∈ CA(G; A)
such that τ στ = τ ; in this case, σ is called a weak generalised inverse of τ . Equivalently,
1

τ ∈ CA(G; A) is vN-regular if and only if there exists σ ∈ CA(G; A) mapping every configuration
in the image of τ to one of its preimages under τ (see Lemma 1). Clearly, the notion of vNregularity generalises reversibility.
In general, for any semigroup S and a, b ∈ S, we say that b is a weak generalised inverse of
a if
aba = a.
We say that b is a generalised inverse (often just called an inverse) of a if
aba = a and bab = b.
An element a ∈ S may have none, one, or more (weak) generalised inverses. It is clear that any
generalised inverse of a is also a weak generalised inverse; not so obvious is that, given the set
W (a) of weak generalised inverses of a we may obtain the set V (a) of generalised inverses of a
as follows (see [8, Exercise 1.9.7]):
V (a) = {bab′ : b, b′ ∈ W (a)}.
Thus, an element a ∈ S is vN-regular if it has at least one generalised inverse (which is equivalent
of having at least one weak generalised inverse). The semigroup S itself is called vN-regular if
all of its elements are vN-regular. Many of the well-known types of semigroups are vN-regular,
such as idempotent semigroups (or bands), full transformation semigroups, and Rees matrix
semigroups. Among various advantages, vN-regular semigroups have a particularly manageable
structure which may be studied using the Green’s relations. For further basic results on vNregular semigroups see [8, Section 1.9].
Another generalisation of reversible CA has appeared in the literature before [18, 19] using
the concept of Drazin inverse [10]. However, as Drazin invertible elements are a special kind of
vN-regular elements, our approach turns out to be more general and natural.
In the following sections we study the vN-regular elements in monoids of CA. First, in
Section 2 we present some basic results and examples, and we establish that, except for the
trivial cases |G| = 1 and |A| = 1, the monoid CA(G; A) is not vN-regular.
In Section 3, we obtain a partial classification of the vN-regular elementary CA in CA(Z; {0, 1}).
We divide the 256 elementary CA into 48 equivalence classes that preserve vN-regularity: this
is an extension of the usual division of elementary CA into 88 equivalence classes that preserve dynamical properties. Among various results, we show that rules like 128 and 254 are
vN-regular (and actually generalised inverses of each other), while others, like the well-known
rules 90 and 110, are not vN-regular. Our classification is only partial as the vN-regularity of
11 classes could not be determined (see Table 1).
In Section 4, we study the vN-regular elements of CA(G; A) when G and A are both finite;
in particular, we characterise them and describe a vN-regular submonoid.
Finally, in Section 5, we study the vN-regular elements of the monoid LCA(G; V ) of linear
CA, when V is a vector space over a field F. Specifically, using results on group rings, we show
that, when G is torsion-free elementary amenable (e.g., G = Zd ), τ ∈ LCA(G; F) is vN-regular
if and only if it is invertible, and that, for finite-dimensional V , LCA(G; V ) itself is vN-regular
if and only if G is locally finite and char(F) ∤ |hgi|, for all g ∈ G. Finally, for the particular
case when G ∼
= Zn is a cyclic group, V := F is a finite field, and char(F) | n, we count the total
number of vN-regular elements in LCA(Zn ; F).
The present paper is an extended version of [5]. Besides improving the general exposition,
Theorem 1, Section 3 and Theorem 6 are completely new, and Theorem 7 is corrected (as the
proof of Theorem 5 in [5] is flawed).

2

2

vN-regular cellular automata

For any set X, let Tran(X), Sym(X), and Sing(X), be the sets of all functions, all bijective
functions, and all non-bijective (or singular) functions of the form τ : X → X, respectively.
Equipped with the composition of functions, Tran(X) is known as the full transformation
monoid on X, Sym(X) is the symmetric group on X, and Sing(X) is the singular transformation semigroup on X. When X is a finite set of size α, we simply write Tranα , Symα , and
Singα , in each case.
We shall review the broad definition of CA that appears in [7, Sec. 1.4]. Let G be a group
and A a set. Denote by AG the configuration space, i.e. the set of all functions of the form
x : G → A. The group G acts on the configuration space AG as follows: for each g ∈ G and
x ∈ AG , the configuration x · g ∈ AG is defined by
(h)x · g := (hg −1 )x,

∀h ∈ G.

The following definitions shall be usefuls in the rest of this paper.
Definition 1. Let G be a group and A a set.
1. For any x ∈ AG , the G-orbit of x in AG is xG := {x · g : g ∈ G}.
2. For any x ∈ AG , the stabiliser of x in G is Gx := {g ∈ G : x · g = x}.
3. A subshift of AG is a subset X ⊆ AG that is G-invariant, i.e. for all x ∈ X, g ∈ G, we
have x · g ∈ X, and closed in the prodiscrete topology of AG .
Definition 2. Let G be a group and A a set. A cellular automaton over AG is a transformation
τ : AG → AG satisfying the following: there is a finite subset S ⊆ G, called a memory set of τ ,
and a local function µ : AS → A such that, for all x ∈ AG , g ∈ G,
(g)(x)τ = ((x · g −1 )|S )µ,
where (x · g−1 )|S is the restriction to S of x · g −1 ∈ AG .
We emphasise that we apply functions on the right, while [7] applies functions on the left.
A transformation τ : AG → AG is G-equivariant if, for all x ∈ AG , g ∈ G,
(x · g)τ = ((x)τ ) · g.
Any cellular automaton is G-equivariant, but the converse is not true in general. A generalisation
of Curtis-Hedlund Theorem (see [7, Theorem 1.8.1]) establishes that, when A is finite, τ : AG →
AG is a CA if and only if τ is G-equivariant and continuous in the prodiscrete topology of AG ;
in particular, when G and A are both finite, G-equivariance completely characterises CA over
AG .
A configuration x ∈ AG is called constant if (g)x = k, for a fixed k ∈ A, for all g ∈ G. In
such case, we denote x by k ∈ AG .
Remark 1. It follows by G-equivariance that any τ ∈ CA(G; A) maps constant configurations
to constant configurations.
Recall from Section 1 that τ ∈ CA(G; A) is invertible if there exists σ ∈ CA(G; A) such that
τ σ = στ = id, and that τ ∈ CA(G; A) is vN-regular if there exists σ ∈ CA(G; A) such that
τ στ = τ . Clearly, every invertible CA is vN-regular. We now present some examples of CA
that are vN-regular but not invertible.
Example 1. If τ ∈ CA(G; A) is idempotent (i.e. τ 2 = τ ), then it is vN-regular as τ τ τ = τ .
3

Example 2. Let G be any nontrivial group and A any set with at least two elements. Let
σ ∈ CA(G; A) be a CA with memory set {s} ⊆ G and local function µ : A → A that is nonbijective. Clearly, σ is not invertible. As Sing(A) is a vN-regular semigroup (see [13, Theorem
II]), there exists µ′ : A → A such that µµ′ µ = µ. If σ ′ is the CA with memory set {s−1 } and
local function µ′ , then σσ ′ σ = σ. Hence σ is vN-regular.
Example 3. Suppose that A = {0, 1, . . . , q − 1}, with q ≥ 2. Consider τ1 , τ2 ∈ CA(Z; A) with
memory set S := {−1, 0, 1} and local functions
(x)µ1 = min{(−1)x, (0)x, (1)x} and (x)µ2 = max{(−1)x, (0)x, (1)x},
respectively, for all x ∈ AS . In particular, when q = 2, τ1 and τ2 are the elementary CA known
as Rules 128 and 254, respectively. Clearly, τ1 and τ2 are not invertible, but we show that
they are generalised inverses of each other, i.e. τ1 τ2 τ1 = τ1 and τ2 τ1 τ2 = τ2 , so they are both
vN-regular. We prove only the first of the previous identities, as the second one is symmetrical.
Consider
x ∈ AZ , y := (x)τ1 , z := (y)τ2 , and a := (z)τ1 .
We want to show that y = a. By equivariance, it is enough to show that (0)y = (0)a. For
ǫ ∈ {−1, 0, 1}, we have
(ǫ)y = min{(ǫ − 1)x, (ǫ)x, (ǫ + 1)x} ≤ (0)x.
Hence,
(0)z = max{(−1)y, (0)y, (1)y} ≤ (0)x.
Similarly (−1)z ≤ (−1)x and (1)z ≤ (1)x, so
(0)a = min{(−1)z, (0)z, (1)z} ≤ (0)y = min{(−1)x, (0)x, (1)x}.
Conversely, we have (−1)z, (0)z, (1)z ≥ (0)y, so (0)a ≥ (0)y.
The following lemma gives an equivalent definition of vN-regular CA. Note that this result
still holds if we replace CA(G; A) with any monoid of transformations.
Lemma 1. Let G be a group and A a set. Then, τ ∈ CA(G; A) is vN-regular if and only if
there exists σ ∈ CA(G; A) such that for every y ∈ (AG )τ there is ŷ ∈ AG with (ŷ)τ = y and
(y)σ = ŷ.
Proof. If τ ∈ CA(G; A) is vN-regular, there exists σ ∈ CA(G; A) such that τ στ = τ . Let
x ∈ AG be such that (x)τ = y (which exists because y ∈ (AG )τ ) and define ŷ := (y)σ. Now,
(ŷ)τ = (y)στ = (x)τ στ = (x)τ = y.
Conversely, assume there exists σ ∈ CA(G; A) satisfying the statement of the lemma. Then, for
any x ∈ AG with y := (x)τ we have
(x)τ στ = (y)στ = (ŷ)τ = y = (x)τ.
Therefore, τ is vN-regular.
The following is a powerful tool to show that a CA is not vN-regular.
Theorem 1. Let G be a group, A a set, and τ ∈ CA(G; A). Suppose there exists x ∈ AG such
that
x ∈ (AG )τ, but x 6= (y)τ for all y ∈ AG such that Gx = Gy .
Then, τ is not vN-regular.
4

Proof. First, note that for any σ ∈ CA(G; A) and z ∈ AG we have Gz ≤ G(z)σ . Indeed, for any
g ∈ Gz we have (z)σ · g = (z · g)σ = (z)σ, so g ∈ G(z)σ .
For a contradiction, suppose that τ is vN-regular. By Lemma 1, there exists σ ∈ CA(G; A)
mapping x to one of its preimages under τ : say z ∈ AG satisfies (z)τ = x and (x)σ = z. By the
above paragraph, Gz ≤ G(z)τ = Gx and Gx ≤ G(x)σ = Gz , so Gz = Gx . This contradicts the
hypothesis. Thus, τ is not vN-regular.
Corollary 1. Let G be a group and A a set. Let τ ∈ CA(G; A), and suppose there is a constant
configuration k ∈ (AG )τ such that k 6= (s)τ for all constant configurations s ∈ AG . Then τ is
not vN-regular.
Proof. This follows by Theorem 1 and the fact that x ∈ AG is constant if and only if Gx = G.
In the following examples we see how Corollary 1 may be used to show that some well-known
CA are not vN-regular.
Example 4. Let φ ∈ CA(Z; {0, 1}) be the Rule 110 elementary CA, and consider the constant
configuration 1. Define x := . . . 10101010 · · · ∈ {0, 1}Z , and note that (x)φ = 1. Since (1)φ = 0
and (0)φ = 0, Corollary 1 implies that φ is not vN-regular.
Example 5. Let τ ∈ CA(Z2 ; {0, 1}) be Conway’s Game of Life, and consider the constant
configuration 1 (all cells alive). By [7, Exercise 1.7.], 1 is in the image of τ ; since (1)τ = 0 (all
cells die from overpopulation) and (0)τ = 0, Corollary 1 implies that τ is not vN-regular.
The following theorem applies to CA over arbitrary groups and sets, and it shows that,
except for the trivial cases, CA(G; A) always contains elements that are not vN-regular.
Theorem 2. Let G be a group and A a set. The monoid CA(G; A) is vN-regular if and only if
|G| = 1 or |A| = 1.
Proof. If |G| = 1 or |A| = 1, then CA(G; A) = Tran(A) or CA(G; A) is the trivial monoid with
one element, respectively. In both cases, CA(G; A) is vN-regular (see [8, Exercise 1.9.1]).
Assume that |G| ≥ 2 and |A| ≥ 2. Suppose that {0, 1} ⊆ A. Let S := {e, g, g −1 } ⊆ G, where
e is the identity of G and e 6= g ∈ G (we do not require g 6= g −1 ). For i = 1, 2, let τi ∈ CA(G; A)
be the cellular automaton defined by the local function µi : AS → A defined by
(
(e)x if (e)x = (g)x = (g−1 )x,
(x)µ1 :=
0
otherwise;
(
1
if (e)x = (g)x = (g−1 )x = 0,
(x)µ2 :=
(e)x otherwise,
for any x ∈ AS . We shall show that τ := τ2 τ1 ∈ CA(G; A) is not vN-regular.
Consider the constant configurations 0, 1 ∈ AG . Let z ∈ AG be defined by
(
m mod (2) if h = gm , m ∈ N minimal,
(h)z :=
0
otherwise.
Figure 1 illustrates the images z, 0, 1, and k 6= 0, 1 (in case it exists) under τ1 and τ2 .
Clearly,
(0)τ = (0)τ2 τ1 = (1)τ1 = 1.
In fact,
(k)τ =

(

1 if k = 0,
k otherwise.
5

τ2

z
τ1 , τ2

τ1
τ1

0

k
τ2
τ1 , τ2

1

Figure 1: Images of τ1 and τ2 .
Furthermore,
(z)τ = (z)τ2 τ1 = (z)τ1 = 0.
Hence, 0 is a constant configuration in the image of τ but with no preimage among the constant
configurations. By Corollary 1, τ is not vN-regular.
Now that we know that CA(G; A) always contains some elements that are vN-regular and
some that are not vN-regular (when |G| ≥ 2 and |A| ≥ 2), an interesting problem is to find a
criterion that describes all vN-regular CA. In the following sections, we study this problem in
three particular cases: the elementary, the finite and the linear cases.

3

Elementary cellular automata

Throughout this section, let A = {0, 1}. An elementary cellular automaton is an element
τ ∈ CA(Z, A) with memory set S = {−1, 0, 1}. These are labeled as ‘Rule M ’, where M is a
number from 0 to 255. In each case, the local rule µM : AS → A is determined as follows: let
M1 . . . M8 be the binary representation of M and write the elements of AS in lexicographical
descending order, i.e. 111, 110, . . . , 000; then, the image of the i-th element of AS under µM is
Mi .
In Example 3, we showed that Rules 128 and 254 are both vN-regular, while, in Example
4, we saw that Rule 110 is not vN-regular. A natural goal is to classify which ones of the 256
elementary cellular automata are vN-regular. In other words, we ask the following question:
Question 1. For which elementary cellular automata τ ∈ CA(Z; A) there exists σ ∈ CA(Z; A)
(not necessarily elementary) such that τ στ = τ ?
In order to achieve this goal, it is convenient to define some equivalence relations between
elementary CA that are preserved by vN-regularity. In general, τ1 , τ2 ∈ CA(G; A) are said to be
conjugate if there exists φ ∈ ICA(G; A) such that τ2 = φ−1 τ1 φ. It is clear that in this situation,
τ1 is vN-regular if and only if τ2 is vN-regular: indeed, if σ ∈ CA(G; A) is such that τ1 στ1 = τ1 ,
then



τ2 = φ−1 τ1 φ = φ−1 τ1 φ φ−1 σφ φ−1 τ1 φ = τ2 σ ′ τ2 ,
where σ ′ = φ−1 σφ ∈ CA(G; A).
There is another symmetry among elementary CA known as the mirrored rule. In order
to describe this, for any x ∈ AZ , denote by xrev the reflection of x through 0; in other words,
(k)xrev = (−k)x, for all k ∈ Z. Now, for any τ ∈ CA(Z; A), define τ ⋆ : AZ → AZ by
(x)τ ⋆ = ((xrev )τ )rev , ∀x ∈ AZ .

6

Proposition 1. The map τ ⋆ : AZ → AZ is a cellular automaton. Moreover, if τ ∈ CA(Z; A) is
elementary, then τ ⋆ is elementary.
Proof. The function rev : AZ → AZ is continuous as its composition with the projection to
k ∈ Z is equal to the projection to −k ∈ Z (which is continuous in the prodiscrete topology
of AZ ). Hence τ ⋆ , being the composition of continuous functions, is also continuous. Observe
that, for all k, r ∈ Z, x ∈ AZ , we have
(k)(x · r)rev = (−k)(x · r) = (−k − r)x = (k + r)xrev = (k)xrev · (−r).
Thus,
(x · r)τ ⋆ = ((x · r)rev )τ )rev = ((xrev )τ )rev · (−(−r)) = (x)τ ⋆ · r.
This proves that τ ⋆ is Z-equivariant, and, by Curtis-Hedlund theorem, τ ⋆ ∈ CA(Z; A).
If τ is elementary, it is easy to see that τ ⋆ has memory set contained in {−1, 0, 1}, so it is
also elementary.
Proposition 2. Let τ ∈ CA(Z; A). Then:
1. (τ ⋆ )⋆ = τ .
2. (τ ◦ σ)⋆ = τ ⋆ ◦ σ ⋆ , for any σ ∈ CA(Z; A).
3. τ is vN-regular if and only if τ ⋆ is vN-regular.
Proof. It is clear that, for all x ∈ AZ ,
(x)(τ ⋆ )⋆ = ((xrev )τ ⋆ )rev = ((xrev

rev

)τ )rev

rev

= (x)τ.

Now,
(x)τ ⋆ ◦ σ ⋆ = (((xrev )τ )rev )σ ⋆ = (((xrev )τ )rev

rev

)σ)rev = ((xrev )τ ◦ σ)rev = (x)(τ ◦ σ)⋆ .

The last part follows because τ στ = τ if and only if τ ⋆ σ ⋆ τ ⋆ = τ ⋆ .
Let φ51 ∈ CA(Z; A) be Rule 51. This CA is invertible with (φ51 )−1 = φ51 , its minimal
memory set is {0}, and can be thought as the transformation of AZ that interchanges 0’s and
1’s.
Proposition 3. Let τ ∈ CA(Z; A). The following are equivalent:
1. τ is elementary and vN-regular.
2. φ51 τ is elementary and vN-regular.
3. τ φ51 is elementary and vN-regular.
Proof. By [7, Proposition 1.4.8], a memory set for φ51 τ is {0} + S = S, where S is a memory
set for τ . Hence, τ is elementary if and only if φ51 τ is elementary, and the other equivalence is
shown similarly.
Suppose τ is vN-regular and let σ ∈ CA(Z; A) be such that τ στ = τ . Then
(φ51 τ )(σφ51 )(φ51 τ ) = φ51 τ στ = φ51 τ,
so φ51 τ is vN-regular. Conversely, if φ51 τ is vN-regular, let σ ′ ∈ CA(Z; A) be such that
(φ51 τ )σ ′ (φ51 τ ) = φ51 τ . Canceling φ51 , we obtain that τ (σ ′ φ51 )τ = τ , so τ is vN-regular.
The other equivalence is shown similarly.

7

Rep.

Equivalent rules

Reg.

Rep.

Equivalent rules

Reg.

0

255

R

29

71, 184, 226

R

1

127, 128, 254

R

30

86, 106, 120, 135, 149, 169, 225

NR

2

8, 16, 64, 191, 239, 247, 253

R

33

123, 132, 222

-

3

17, 63, 119, 136, 192, 238, 252

R

35

49, 59, 115, 140, 196, 206, 220

R

4

32, 223, 251

R

36

219

NR

5

95, 160, 250

R

37

91, 164, 218

NR

6

20, 40, 96, 159, 215, 235, 249

-

38

44, 52, 100, 155, 203, 211, 217

NR

7

21, 31, 87, 168, 224, 234, 248

-

41

97, 107, 121, 134, 148, 158, 214

-

9

65, 111, 125, 130, 144, 190, 246

-

43

113, 142, 212

R

10

80, 175, 245

R

45

75, 89, 101, 154, 166, 180, 210

NR

11

47, 81, 117, 138, 174, 208, 244

R

46

116, 139, 209

NR

12

34, 48, 68, 187, 207, 221, 243

R

50

76, 179, 205

R

13

69, 79, 93, 162, 176, 186, 242

R

51

204

R

14

42, 84, 112, 143, 171, 213, 241

R

54

108, 147, 201

NR

15

85, 170, 240

R

57

99, 156, 198

-

18

72, 183, 237

NR

58

78, 92, 114, 141, 163, 177, 197

-

19

55, 200, 236

R

60

102, 153, 195

NR

22

104, 151, 233

NR

62

110, 118, 124, 131, 137, 145, 193

NR

23

232

-

73

109, 146, 182

NR

24

66, 189, 231

NR

77

178

-

25

61, 67, 103, 152, 188, 194, 230

NR

90

165

NR

26

74, 82, 88, 167, 173, 181, 229

NR

94

122, 133, 161

NR

27

39, 53, 83, 172, 202, 216, 228

-

105

150

NR

28

56, 70, 98, 157, 185, 199, 227

-

126

129

NR

Table 1: vN-regularity of elementary CA
In the literature, two elementary CA τ1 and τ2 are said to be equivalent if τ1 = τ2 , or
τ1 = (τ2 )⋆ , or τ1 = φ51 τ2 , or τ1 = φ51 (τ2 )⋆ . This defines 88 equivalence classes of elementary
cellular automata (see [16, Table 1]). Here, we extend this notion of equivalence.
Definition 3. Let hφ51 i = {id, φ51 }. Two elementary CA τ1 and τ2 are said to be equivalent if
τ1 ∈ hφ51 iτ2 hφ51 i, or τ1 ∈ hφ51 i(τ2 )⋆ hφ51 i.
Thus, according to our definition, the equivalence class of an elementary CA τ is
[τ ] = {τ, τ φ51 , φ51 τ, φ51 τ φ51 , τ ⋆ , τ ⋆ φ51 , φ51 τ ⋆ , φ51 τ ⋆ φ51 }.
Note that some of the elements in the above set might be equal. We could, potentially, try to
increase this equivalence class by conjugating by another invertible CA. Let ξ be the shift map
of AZ . It is known (see [16, Sec. 4.16]) that the invertible elementary CA are rules 15, 51, 85,
170, 204, and 240, which correspond to ξφ51 , φ51 , ξ −1 φ51 , ξ −1 , id, and ξ, respectively. As ξ
commutes with every CA, conjugation by one of the previous does not add anything new to [τ ],
e.g. (ξφ51 )τ (φ51 ξ −1 ) = φ51 τ φ51 . As (φ51 )⋆ = φ51 , the equivalence class [τ ] cannot be increased
by further applying the mirrored rule.

8

Our notion of equivalence defines 48 equivalence classes of elementary CA (see Table 1) with
the property that if an element of the class is vN-regular, then all other elements of the class
are vN-regular.
Lemma 2. The equivalence classes of the following rules are not vN-regular: 18, 22, 24, 25,
26, 30, 36, 37, 38, 45, 46, 54, 60, 62, 73, 90, 105, 122 and 126.
Proof. This result follows by the repeated use of Theorem 1. We define configurations yi ∈
{0, 1}Z as follows:
(i)y1 = 1, ∀i ∈ Z
(
1 if i is even
(i)y2 =
0 otherwise
(
1 if i is multiple of 3
(i)y3 =
0 otherwise.
For each rule, Table 2 gives which configuration yi satisfies the hypothesis of Theorem 1.
Rule

x

Rule

x

Rule

x

Rule

x

18

y2

26

y2

45

y2

73

y2

22

y1

30

y1

46

y1

90

y2

24

y2

36

y1

54

y1

105

y3

25

y2

37

y2

60

y1

122

y1

38

y1

62

y1

126

y1

Table 2: Elementary CA that are not vN-regular

Lemma 3. The equivalence classes of the following rules are vN-regular: 0, 2, 4, 5, 10, 11, 12,
13, 14, 15, 29, 35, 43, 51, 76, 128, 192 and 200.
Proof. Rules 15 and 51 are vN-regular because they are invertible. Rules 0, 4, 12, 76 and 200
are idempotent (i.e. τ 2 = τ , see [11, Table 1]). By [11, Table 1], rules 5 and 29 satisfy that
τ 3 = τ , so they both are vN-regular. Rule 128 is vN-regular by Example 3. Rule 192 has local
rule (x)µ = min{(−1)x, (0)x}; similar calculations as in Example 3 show that Rule 238, with
local rule (x)µ = max{(0)x, (1)x}, is a generalized inverse of Rule 192.
Computer calculations obtained generalised inverses for rules 2, 10, 11, 13, 14, 35 and 43.
These are given in Table 3.
Rule

Gen. Inv.

Rule

Gen. Inv.

Rule

Gen. Inv.

0

0

12

12

43

113

2

16

13

21

51

51

4

4

14

85

76

76

5

5

15

85

128

254

10

80

29

29

192

238

11

85

35

49

200

200

Table 3: Elementary CA that are vN-regular

9

This leaves 11 classes for which we could not decide whether they were regular or not.
Computer calculations show that no member of those classes has an elementary weak inverse.

4

Finite cellular automata

In this section we characterise the vN-regular elements in the monoid CA(G; A) when G and A
are both finite (Theorem 4). In order to achieve this, we summarise some of the notation and
results obtained in [3, 4, 6].
In the case when G and A are both finite, every subset of AG is closed in the prodiscrete
topology, so the subshifts of AG are simply unions of G-orbits. Moreover, as every map τ :
AG → AG is continuous in this case, CA(G; A) consists of all the G-equivariant maps of AG .
Theorem 3 is easily deduced from Lemmas 3, 9 and 10 in [6].
Theorem 3. Let G be a finite group of size n ≥ 2 and A a finite set of size q ≥ 2. Let x, y ∈ AG .
(i) Let τ ∈ CA(G; A). If (x)τ ∈ (xG), then τ |xG ∈ Sym(xG).
(ii) There exists τ ∈ ICA(G; A) such that (x)τ = y if and only if Gx = Gy .
(iii) There exists τ ∈ CA(G; A) such that (x)τ = y if and only if Gx ≤ Gy .
The following result shows that the converse of Theorem 1 holds for finite CA.
Theorem 4. Let G be a finite group and A a finite set of size q ≥ 2. Let τ ∈ CA(G; A). Then,
τ is vN-regular if and only if for every y ∈ (AG )τ there is x ∈ AG such that (x)τ = y and
Gx = Gy .
Proof. The “only if” part follows by the contrapositive of Theorem 1.
Conversely, suppose that for every y ∈ (AG )τ there is x ∈ AG such that (x)τ = y and
Gx = Gy . Choose pairwise distinct G-orbits y1 G, . . . , yℓ G such that
(AG )τ =

ℓ
[

yi G.

i=1

For each i, fix yi′ ∈ AG such that (yi′ )τ = yi and Gyi = Gyi′ . We define φ : AG → AG as follows:
for any z ∈ AG ,
(
z
if z 6∈ (AG )τ,
(z)φ :=
yi′ · g if z = yi · g ∈ yi G.
The map φ is well-defined because
yi · g = yi · h ⇐⇒ hg −1 ∈ Gyi = Gyi′ ⇐⇒ yi′ · g = yi′ · h.
Clearly, φ is G-equivariant, so φ ∈ CA(G; A). Now, for any x ∈ AG with (x)τ = yi · g,
(x)τ φτ = (yi · g)φτ = (yi′ · g)τ = (yi′ )τ · g = yi · g = (x)τ.
This proves that τ φτ = τ , so τ is vN-regular.
Our goal now is to find a vN-regular submonoid of CA(G; A) and describe its structure (see
Theorem 5). In order to achieve this, we need some further terminology and basic results.
Say that two subgroups H1 and H2 of G are conjugate in G if there exists g ∈ G such that
−1
g H1 g = H2 . This defines an equivalence relation on the subgroups of G. Denote by [H] the
conjugacy class of the subgroup H of G. Define the box in AG corresponding to [H], where
H ≤ G, by
B[H] (G; A) := {x ∈ AG : [Gx ] = [H]}.
10

As any subgroup of G is the stabiliser of some configuration in AG , the set {B[H] (G; A) : H ≤ G}
is a partition of AG . Note that B[H] (G; A) is a subshift of AG (because G(x·g) = g −1 Gx g) and, by
the Orbit-Stabiliser Theorem, all the G-orbits contained in B[H] (G; A) have equal sizes. When
G and A are clear from the context, we write simply B[H] instead of B[H] (G; A).
Example 6. For any finite group G and finite set A of size q, we have
B[G] = {k ∈ AG : k is constant}.
Let α[H] (G; A) be the number of G-orbits inside the box B[H] ; for example, α[G] (G; A) = |A|,
as every constant configuration defines an orbit of size 1.
A submonoid R ≤ M is called maximal vN-regular if there is no vN-regular monoid K such
that R < K < M .
Theorem 5. Let G be a finite group and A a finite set of size q ≥ 2. Let

R := σ ∈ CA(G; A) : Gx = G(x)σ for all x ∈ AG .

(i) R = σ ∈ CA(G; A) : (B[H] )σ ⊆ B[H] , ∀H ≤ G .

(ii) ICA(G; A) ≤ R.

(iii) R is a vN-regular monoid.
(iv) R is not a maximal vN-regular submonoid of CA(G; A).
Proof. Parts (i) and (ii) follow by Theorem 3, while part (ii) follows by Theorem 4.
For part (iv), let x, y ∈ AG be such that Gx < Gy , so x and y are in different boxes.
Define τ ∈ CA(G; A) such that (x)τ = y, (B[Gy ] )τ = yG, and τ fixes any other configuration
in AG \ (B[Gy ] ∪ {xG}). It is clear by Theorem 4 that τ is vN-regular. We will show that
K := hR, τ i is a vN-regular submonoid of CA(G; A). Let σ ∈ K and z ∈ (AG )σ. If σ ∈ R, then
it is obviously vN-regular, so assume that σ = ρ1 τ ρ2 with ρ1 ∈ K and ρ2 ∈ R. If z ∈ AG \(B[Gy ] ),
it is clear that z has a preimage in its own box; otherwise (B[Gy ] )σ = (yG)ρ2 = zG and z has a
preimage in B[Gy ] . Hence σ is vN-regular and so is K.
For any integer α ≥ 2 and any group C, the wreath product of C by Tranα is the monoid
C ≀ Tranα := {(v, f ) : v ∈ C α , f ∈ Tranα }
equipped with the operation
(v, f ) · (w, g) = (v(f · w), f ◦ g), for any v, w ∈ C α , f, g ∈ Tranα ,
where f acts on the left on w as follows:
f · w = f · (w1 , w2 , . . . , wα ) := (w(1)f , w(2)f , . . . , w(α)f ).
For a more detailed description of the wreath product of monoids see [1, Sec. 2].
For any H ≤ G, let NG (H) := {g ∈ G : gHg−1 = H} be the normaliser of H in G.
Theorem 6. Let G be a finite group, A a finite set of size q ≥ 2 and R ≤ CA(G; A) as given
by Theorem 5. Let H1 , H2 , . . . , Hr be a complete list of representatives for the conjugacy classes
of subgroups of G. Then:
r
Y
∼
(NG (Hi )/Hi ) ≀ Tranαi ,
R=
i=1

where αi = α[Hi ] (G; A).

11

Q
Proof. By Theorem 5 (i), we see that R may be embedded in ni=1 Tran(B[Hi ] ). Any CA
preserves the uniform partition of B[Hi ] into G-orbits, so by [1, Lemma 2.1], the projection of
R to Tran(B[Hi ] ) is contained in Tran(O) ≀ Tranα , where O is a fixed orbit contained in B[H] .
Any CA acts on the orbit O by NG (Hi )/Hi and it may induce any transformation among orbits
(c.f. the proof of Theorem 3 in [6]). Thus, the projection of R to Tran(B[Hi ] ) is precisely
(NG (Hi )/Hi ) ≀ Tranαi .

5

Linear cellular automata

Let V a vector space over a field F. For any group G, the configuration space V G is also a
vector space over F equipped with the pointwise addition and scalar multiplication. Denote by
EndF (V G ) the set of all F-linear transformations of the form τ : V G → V G . Define
LCA(G; V ) := CA(G; V ) ∩ EndF (V G ).
Note that LCA(G; V ) is not only a monoid, but also an F-algebra (i.e. a vector space over F
equipped with a bilinear binary product), because, again, we may equip LCA(G; V ) with the
pointwise addition and scalar multiplication. In particular, LCA(G; V ) is also a ring.
As in the case of semigroups, vN-regular rings have been widely studied and many important
results have been obtained. In this chapter, we study the vN-regular elements of LCA(G; V )
under some natural assumptions on the group G.
First, we introduce some preliminary results and notation. The group ring R[G] is the set
of all functions f : G → R with finite support (i.e. the set {g ∈ G : (g)f 6= 0} P
is finite).
Equivalently, the group ring R[G] may be defined as the set of all formal finite sums g∈G ag g
with ag ∈ R. The multiplication in R[G] is defined naturally using the multiplications of G and
R:
X
X
X
ag g
ah h =
ag ah gh.
g∈G

h∈G

g,h∈G

If we let R := EndF (V ), it turns out that EndF (V )[G] and LCA(G; V ) are isomorphic as Falgebras (see [7, Theorem 8.5.2]).
Define the order of g ∈ G by o(g) := |hgi| (i.e. the size of the subgroup generated by g).
The group G is torsion-free if the identity is the only element of finite order; for instance, the
groups Zd , for d ∈ N, are torsion-free groups. The group G is elementary amenable if it may
be obtained from finite groups or abelian groups by a sequence of group extensions or direct
unions.
In the following theorem we characterise the vN-regular linear cellular automata over fields
and torsion-free elementary amenable groups (such as Zd , d ∈ N).
Theorem 7. Let G be a torsion-free elementary amenable group and let V = F be any field. A
non-zero element τ ∈ LCA(G; F) is vN-regular if and only if it is invertible.
Proof. It is clear that any invertible element is vN-regular. Let τ ∈ LCA(G; F) be non-zero
vN-regular. In this case, EndF (F) ∼
= F, so LCA(G; F) ∼
= F[G]. By definition, there exists
σ ∈ LCA(G; V ) such that τ στ = τ . As LCA(G; V ) is a ring, the previous is equivalent to
τ (στ − 1) = 0,
where 1 = 1e and 0 = 0e are the identity and zero endomorphisms, respectively. Since τ 6= 0,
either στ − 1 = 0, in which case τ is invertible, or στ − 1 is a zero-divisor. However, it was
established in [15, Theorem 1.4] that F[G] has no zero-divisors whenever G is a torsion-free
elementary amenable group. Hence, τ is invertible.

12

The argument of the previous result works as long as the group ring F[G] has no zero-divisor.
This is connected with the well-known Kaplansky’s conjecture which states that F[G] has no
zero-divisors when G is a torsion-free group.
The characteristic of a field F, denoted by char(F), is the smallest k ∈ N such that
1| + 1 +
{z· · · + 1} = 0,
k times

where 1 is the multiplicative identity of F. If no such k exists we say that F has characteristic
0.
A group G is locally finite if every finitely generated subgroup of G is finite; in particular,
the order of every element of G is finite. Examples of such groups are finite groups and infinite
direct sums of finite groups.
Theorem 8. Let G be a group and let V be a finite-dimensional vector space over F. Then,
LCA(G; V ) is vN-regular if and only if G is locally finite and char(F) ∤ o(g), for all g ∈ G.
Proof. By [9, Theorem 3] (see also [2, 17]), we have that a group ring R[G] is vN-regular if and
only if R is vN-regular, G is locally finite and o(g) is a unit in R for all g ∈ G. In the case
of LCA(G; V ) ∼
= EndF (V )[G], since dim(V ) := n < ∞, the ring R := EndF (V ) ∼
= Mn×n (F) is
vN-regular (see [12, Theorem 1.7]. The condition that o(g), seen as the matrix o(g)In , is a unit
in Mn×n (F) is satisfied if and only if o(g) is nonzero in F, which is equivalent to char(F) ∤ o(g),
for all g ∈ G.
Corollary 2. Let G be a group and let V be a finite-dimensional vector space over a field F of
characteristic 0. Then, LCA(G; V ) is vN-regular if and only if G is locally finite.
Henceforth, we focus on the vN-regular elements of LCA(G; V ) when V is a one-dimensional
vector space (i.e. V is just the field F). In this case, EndF (F) ∼
= F, so LCA(G; F) and F[G] are
isomorphic as F-algebras.
A non-zero element a of a ring R is called nilpotent if there exists n > 0 such that an = 0.
The following basic result will be quite useful in the rest of this section.
Lemma 4. Let R be a commutative ring. If a ∈ R is nilpotent, then a is not a vN-regular
element.
Proof. Let R be a commutative ring and a ∈ R a nilpotent element. Let n > 0 be the smallest
integer such that an = 0. Suppose a is a vN-regular element, so there is x ∈ R such that
axa = a. By commutativity, we have a2 x = a. Multiplying both sides of this equation by an−2
we obtain 0 = an x = an−1 , which contradicts the minimality of n.
Example 7. Suppose that G is a finite abelian group and let F be a field such that char(F) | |G|.
By Theorem
8, LCA(G; F) must have elements that are not vN-regular. For example, let
P
s := g∈G g ∈ F[G]. As sg = s, for all g ∈ G, and char(F) | |G|, we have s2 = |G|s = 0.
Clearly, F[G] is commutative because G is abelian, so, by Lemma 4, s is not a vN-regular
element.
We finish this section with the special case when G is the cyclic group Zn and F is a finite
field with char(F) | n. By Theorem 8, not all the elements of LCA(Zn ; F) are vN-regular, so
how many of them are there? In order to count them we need a few technical results about
commutative rings.
An ideal I of a commutative ring R is a subring such that rb ∈ I for all r ∈ R, b ∈ I. For
any a ∈ R, the principal ideal generated by a is the ideal hai := {ra : r ∈ R}. A ring is called
local if it has a unique maximal ideal.

13

Denote by F[x] the ring of polynomials with coefficients in F. When G ∼
= Zn , we have the
following isomorphisms as F-algebras:
LCA(Zn ; F) ∼
= F[Zn ] ∼
= F[x]/hxn − 1i,
where hxn − 1i is a principal ideal in F[x].
Theorem 9. Let n ≥ 2 be an integer, and let F be a finite field of size q such that char(F) | n.
Consider the following factorization of xn − 1 into irreducible elements of F[x]:
xn − 1 = p1 (x)m1 p2 (x)m2 . . . pr (x)mr .
For each i = 1, . . . r, let di := deg(pi (x)). Then, the number of vN-regular elements in
LCA(Zn ; F) is exactly
r 

Y
(q di − 1)q di (mi −1) + 1 .
i=1

Proof. Recall that

LCA(Zn ; F) ∼
= F[x]/hxn − 1i.

By the Chinese Remainder Theorem,
F[x]/hxn − 1i ∼
= F[x]/hp1 (x)m1 i × F[x]/hp2 (x)m2 i × · · · × F[x]/hpr (x)mr i.
An element a = (a1 , . . . , ar ) in the right-hand side of the above isomorphism is a vN-regular
element if and only if ai is a vN-regular element in F[x]/hpi (x)mi i for all i = 1, . . . , r.
Fix m := mi , p(x) = pi (x), and d := di . Consider the principal ideals A := hp(x)i and
B := hp(x)m i in F[x]. Then, F[x]/B is a local ring with unique maximal ideal A/B, and
each of its nonzero elements is either nilpotent or a unit (i.e. invertible): in particular, the
set of units of F[x]/B is precisely (F[x]/B) − (A/B). By the Third Isomorphism Theorem,
(F[x]/B)/(A/B) ∼
= (F[x]/A), so
|A/B| =

q dm
|F[x]/B|
= d = q d(m−1) .
|F[x]/A|
q

Thus, the number of units in F[x]/B is
|(F[x]/B) − (A/B)| = q dm − q d(m−1) = (q d − 1)q d(m−1) .
As nilpotent elements are not vN-regular by Lemma 4, every vN-regular element of F[x]/hpi (x)mi i
is zero or a unit. Thus, the number of vN-regular elements in F[x]/hpi (x)mi i is (q di −1)q di (mi −1) +
1.

6

Conclusions and future work

We studied generalised inverses and von Neumann regular cellular automata over configuration
spaces AG . Our main results are the following:
1. All cellular automata over AG are vN-regular if and only if |G| = 1 or |A| = 1 (Theorem
2).
2. Out of the 256 elementary cellular automata over {0, 1}Z , at least 96 are vN-regular and
92 are not vN-regular (Table 1).
3. If G and A are finite, a cellular automaton τ over AG is vN-regular if and only if for every
y ∈ (AG )τ there is x ∈ AG such that (x)τ = y and Gx = Gy (Theorem 4).
14

4. If G is a torsion-free elementary amenable group and A is a field, a non-zero linear cellular
automaton τ over AG is vN-regular if and only if it is invertible (Theorem 7).
5. If A is a finite-dimensional vector space over a field of characteristic 0, all linear cellular
automata over AG are vN-regular if and only if G is locally finite (Corollary 2).
It could not be determined whether 68 elementary cellular automata (grouped in 11 equivalence classes) are vN-regular or not. A clear direction for future work is to examine in more
detail these cases. In order to decide their vN-regularity, we need new tools to find generalised
inverses and an exhaustive analysis of their behavior on periodic orbits (in order to be able to
use Theorem 1).

7

Acknowledgment

We thank Alberto Dennunzio, Enrico Formenti, Luca Manzoni, Luca Mariot and Antonio E.
Porreca for the successful organisation of the 23rd International Workshop on Cellular Automata
and Discrete Complex Systems (AUTOMATA 2017), in which some of the results of this paper
were presented and discussed.

References
[1] Araújo, J., Schneider, C.: The rank of the endomorphism monoid of a uniform partition.
Semigroup Forum 78, 498–510 (2009).
[2] Auslander, M.: On regular group rings. Proc. Amer. Math. Soc. 8, 658 – 664 (1957).
[3] Castillo-Ramirez, A., Gadouleau, M.: Ranks of finite semigroups of one-dimensional cellular
automata. Semigroup Forum 93, 347–362 (2016).
[4] Castillo-Ramirez, A., Gadouleau, M.: On Finite Monoids of Cellular Automata. In: Cook,
M., Neary, T. (eds.) Cellular Automata and Discrete Complex Systems. AUTOMATA 2016.
LNCS 9664, pp. 90–104, Springer International Publishing Switzerland (2016).
[5] Castillo-Ramirez, A., Gadouleau, M.: Von Neumann Regular Cellular Automata. In: Dennunzio, Formenti, Manzoni, Porreca (eds.) Cellular Automata and Discrete Complex Systems. AUTOMATA 2017. LNCS 10248, pp. 44–55, Springer International Publishing
(2017).
[6] Castillo-Ramirez, A., Gadouleau, M.: Cellular Automata and Finite Groups. Nat. Comput.
(Online First, 2017) 1–14.
[7] Ceccherini-Silberstein, T., Coornaert, M.: Cellular Automata and Groups. Springer Monographs in Mathematics, Springer-Verlag Berlin Heidelberg (2010).
[8] Clifford, A.H., Preston, G. B.: The Algebraic Theory of Semigroups, Volume 1. Mathematical Surveys of the American Mathematical Society 7, Providence, R.I. (1961).
[9] Connell, I.G.: On the Group Ring. Canad. J. Math. 15, 650 – 685 (1963).
[10] Drazin, M.P.: Pseudo-Inverses in Associative Rings and Semigroups. Amer. Math. Mon.
65, 506–514 (1958).
[11] Epperlein, J.: Classification of Elementary Cellular Autimata Up to Topological Conjugacy.
In: Kari, J. (eds.) Cellular Automata and Discrete Complex Systems. AUTOMATA 2015.
LNCS 9099, pp. 99-112, Springer, Berlin, Heidelberg (2015).
15

[12] Goodearl, K. R.: Von Neumann Regular Rings. Monographs and Studies in Mathematics
4. Pitman Publishing Ltd. (1979).
[13] Howie, J. M.: The Subsemigroup Generated by the Idempotents of a Full Transformation
Semigroup. J. London Math. Soc. s1-41, 707–716 (1966).
[14] Kari, J.: Theory of cellular automata: A Survey. Theoret. Comput. Sci. 334, 3–33 (2005).
[15] Kropholler, P.H., Linnell, P.A., Moody, J.A.: Applications of a new K-theoretic theorem
to soluble group rings. Proc. Amer. Math. Soc. 104 (3), 675–684 (1988).
[16] Martı́nez, G. J.: A Note on Elementary Cellular Automata Classification. J. Cellular Automata 8, 233–259 (2013).
[17] McLaughlin, J.E.: A note on regular group rings. Michigan Math. J. 5, 127–128 (1958).
[18] Zhang, K., Zhang, L.: Generalized Reversibility of Cellular Automata with Boundaries.
Proceedings of the 10th World Congress on Intelligent Control and Automation, Beijing,
China (2012).
[19] Zhang, K., Zhang, L.: Generalized Reversibility of Topological Dynamical Systems and
Cellular Automata. J. Cellular Automata 10, 425–434 (2015).
A. Castillo-Ramirez (Corresponding author), Universidad de Guadalajara, CUCEI, Departamento de
Matemáticas, Guadalajara, México.
Email: alonso.castillor@academicos.udg.mx
M. Gadouleau, Department of Computer Science, Durham University, South Road, Durham DH1
3LE, U.K.
Email: m.r.gadouleau@durham.ac.uk

16

