Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Conference papers

Von Neumann Regular Cellular Automata

Abstract : For any group G and any set A, a cellular automaton (CA) is a transformation of the configuration space $$A^G$$ defined via a finite memory set and a local function. Let $$\mathrm {CA}(G;A)$$ be the monoid of all CA over $$A^G$$. In this paper, we investigate a generalisation of the inverse of a CA from the semigroup-theoretic perspective. An element $$\tau \in \mathrm {CA}(G;A)$$ is von Neumann regular (or simply regular) if there exists $$\sigma \in \mathrm {CA}(G;A)$$ such that $$\tau \circ \sigma \circ \tau = \tau $$ and $$\sigma \circ \tau \circ \sigma = \sigma $$, where $$\circ $$ is the composition of functions. Such an element $$\sigma $$ is called a generalised inverse of $$\tau $$. The monoid $$\mathrm {CA}(G;A)$$ itself is regular if all its elements are regular. We establish that $$\mathrm {CA}(G;A)$$ is regular if and only if $$\vert G \vert = 1$$ or $$\vert A \vert = 1$$, and we characterise all regular elements in $$\mathrm {CA}(G;A)$$ when G and A are both finite. Furthermore, we study regular linear CA when $$A= V$$ is a vector space over a field $$\mathbb {F}$$; in particular, we show that every regular linear CA is invertible when G is torsion-free (e.g. when $$G=\mathbb {Z}^d, d \ge 1$$), and that every linear CA is regular when V is finite-dimensional and G is locally finite with $$\mathrm {char}(\mathbb {F}) \not \mid o(g)$$ for all $$g \in G$$.
Document type :
Conference papers
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/hal-01656360
Contributor : Hal Ifip Connect in order to contact the contributor
Submitted on : Tuesday, December 5, 2017 - 3:42:37 PM
Last modification on : Thursday, July 19, 2018 - 4:58:10 PM

File

447449_1_En_4_Chapter.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Alonso Castillo-Ramirez, Maximilien Gadouleau. Von Neumann Regular Cellular Automata. 23th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2017, Milan, Italy. pp.44-55, ⟨10.1007/978-3-319-58631-1_4⟩. ⟨hal-01656360⟩

Share

Metrics

Record views

44

Files downloads

41