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).

# 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$.
Keywords :
Document type :
Conference papers
Domain :

Cited literature [15 references]

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)

### 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⟩

Record views