Cookies

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

Profile

Publication details for Dr Maximilien Gadouleau

Castillo-Ramirez, Alonso & Gadouleau, Maximilien (2020). Elementary, finite and linear vN-regular cellular automata. Information and Computation 104533.

Author(s) from Durham

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
weak generalised inverse of  . In this paper, we investigate vN-regularity of various kinds of
CA. First, we establish that, over any nontrivial con guration space, there always exist CA
that are not vN-regular. Then, we obtain a partial classi cation 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.