Elementary, finite and linear vN-regular cellular automata

. 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}^{m a t h b b Z}

; in particular, 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. Next, when

A

and

G

are both finite, we obtain a full characterisation of vN-regular CA over

A^{G}

. Finally, we study vN-regular linear CA when

A = V

is a vector space over a field

m a t h b b F

; we show that every vN-regular linear CA is invertible when

V = m a t h b b F

and

G

is torsion-free elementary amenable (e.g. when

G = m a t h b b Z^{d}, d i n m a t h b b N

), and that every linear CA is vN-regular when

V

is finite-dimensional and

G

is locally finite with

C h a r (m a t h b b F) m i d o (g)

for all

g i n G

.

Review text

Let \(G\) be any group and \(A\) be any set. The set of all functions from \(G\) to \(A\) is denoted by \(A^G\). Let \(\operatorname{CA}(G; A)\) be the set of all CA over \(A^G\). A cellular automaton \(\tau\in\operatorname{CA}(G; A)\) is von Neumann regular (vN-regular) if there exists \(\sigma\in\operatorname{CA}(G; A)\) such that \(\tau\sigma\tau=\tau\). In the present paper, the authors are interested in the vN-regular elements in monoids of CA. The authors present some basic results and examples, and they establish that the monoid \(\operatorname{CA}(G; A)\) is not vN-regular. The authors obtain a partial classification of the vN-regular elementary CA over \(\{0, 1\}^{\mathbb{Z}}\). The authors prove that the monoid \(\operatorname{CA}(G; A)\) is vN-regular if and only if \(|G| = 1\) or \(|A| = 1\). The authors study whether elementary cellular automata (ECAs) are vN-regular. The authors prove that rules like 128 and 254 are vN-regular, while others, like the well-known rules 90 and 110, are not vN-regular. Then, the authors study the vN-regular elements of \(\operatorname{CA}(G; A)\) when \(G\) and \(A\) are both finite; in particular, the authors characterize them and describe a vN-regular submonoid. The vN-regular elements of the monoid \(\operatorname{LCA}(G; V)\) of linear CA are studied when \(V\) is a vector space over a field \(\mathbb{F}\). Let \(G\) be torsion-free elementary amenable (e.g., \(G =\mathbb{Z}^d\)), under some conditions the authors prove that \(\tau \in \operatorname{LCA}(G; \mathbb{F})\) is vN-regular if and only if it is invertible.

Recommendations

Cites work

Cited in

(7)

This page was built for publication: Elementary, finite and linear vN-regular cellular automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2201792)