Von Neumann regular cellular automata

DOI10.1007/978-3-319-58631-1_4MaRDI QIDQ1704101zbMATH OpenOpenAlexFDO

Authors Alonso Castillo-Ramirez, Maximilien Gadouleau

Publication date 8 March 2018

Full work available at URL https://arxiv.org/abs/1701.02692

zbMATH Keywords

cellular automatamonoidsvon Neumann regular elementslinear cellular automatageneralised inverses

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80) Semigroups (20M99)

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 $extCA(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 $auinextCA(G;A)$ is von Neumann regular (or simply regular) if there exists $sigmainextCA(G;A)$ such that $aucircsigmacircau=au$ and $sigmacircaucircsigma=sigma$, where $circ$ is the composition of functions. Such an element $sigma$ is called a generalised inverse of $au$. The monoid $extCA(G;A)$ itself is regular if all its elements are regular. We establish that $extCA(G;A)$ is regular if and only if $vertGvert=1$ or $vertAvert=1$, and we characterise all regular elements in $extCA(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 $mathbbF$; in particular, we show that every regular linear CA is invertible when $G$ is torsion-free elementary amenable (e.g. when $G=mathbb{Z}^d,dinmathbbN$) and $V=mathbbF$, and that every linear CA is regular when $V$ is finite-dimensional and $G$ is locally finite with $extChar(mathbbF)mido(g)$ for all $ginG$.

Recommendations

• Elementary, finite and linear vN-regular cellular automata
• Cellular automata over algebraic structures
• On Finite Monoids of Cellular Automata
• Structure of the invertible CA transformations group
• Group structured linear cellular automata over \(Z_ m\)

Cited in

(9)

• Strongly regular matrices revisited
• On the minimal number of generators of endomorphism monoids of full shifts
• Bounding the minimal number of generators of groups and monoids of cellular automata
• Matrices having nonzero outer inverses
• Von Neumann regular matrices revisited
• Elementary, finite and linear vN-regular cellular automata
• Von Neumann regularity, split epicness and elementary cellular automata
• On von Neumann regularity of cellular automata
• CELLULAR AUTOMATA OVER SEMI-DIRECT PRODUCT GROUPS: REDUCTION AND INVERTIBILITY RESULTS

This page was built for publication: Von Neumann regular cellular automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1704101)