Skip to main content

Research Repository

Advanced Search

Elementary, finite and linear vN-regular cellular automata

Castillo-Ramirez, Alonso; Gadouleau, Maximilien

Elementary, finite and linear vN-regular cellular automata Thumbnail


Alonso Castillo-Ramirez


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 weak generalised inverse of . In this paper, we investigate vN-regularity of various kinds of CA. First, we establish that, over any nontrivial conguration space, there always exist CA that are not vN-regular. Then, we obtain a partial classication of elementary vN-regular CA over f0; 1gZ; 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 nite, 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 eld 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 2 N), and that every linear CA is vN-regular when V is nite-dimensional and G is locally nite with char(F) - o(g) for all g 2 G.


Castillo-Ramirez, A., & Gadouleau, M. (2020). Elementary, finite and linear vN-regular cellular automata. Information and Computation, 274, Article 104533.

Journal Article Type Article
Online Publication Date Mar 2, 2020
Publication Date Oct 2, 2020
Deposit Date Mar 3, 2020
Publicly Available Date Mar 2, 2021
Journal Information and Computation
Print ISSN 0890-5401
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 274
Article Number 104533


You might also like

Downloadable Citations