@article { ,
title = {Elementary, finite and linear vN-regular cellular automata},
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 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.},
doi = {10.1016/j.ic.2020.104533},
issn = {0890-5401},
journal = {Information and Computation},
note = {EPrint Processing Status: Full text deposited in DRO},
publicationstatus = {Published},
publisher = {Elsevier},
url = {https://durham-repository.worktribe.com/output/1269183},
volume = {274},
year = {2020},
author = {Castillo-Ramirez, Alonso and Gadouleau, Maximilien}
}