Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Elementary, finite and linear vN-regular cellular automata.

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

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.

Item Type:Article
Full text:Publisher-imposed embargo
(AM) Accepted Manuscript
Available under License - Creative Commons Attribution Non-commercial No Derivatives.
File format - PDF
(573Kb)
Status:Peer-reviewed
Publisher Web site:https://doi.org/10.1016/j.ic.2020.104533
Publisher statement:© 2020 This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/
Date accepted:No date available
Date deposited:03 March 2020
Date of first online publication:2020
Date first made open access:No date available

Save or Share this output

Export:
Export
Look up in GoogleScholar