2017/01/10 by Castillo-Ramirez, Alonso, Gadouleau, Maximilien
#05E18 #20M20 #68Q80 #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Group Theory (math.GR)
paper · doi:10.48550/arxiv.1701.02692
For any group G and any set A, a cellular automaton (CA) is a transformation of the configuration space AG defined via a finite memory set and a local function. Let CA(G;A) be the monoid of all CA over AG. In this paper, we investigate a generalisation of the inverse of a CA from the semigroup-theoretic perspective. An element τ∈ CA(G;A) is von Neumann regular (or simply regular) if there exists σ∈ CA(G;A) such that τ∘ σ∘ τ= τ and σ∘ τ∘ σ= σ, where ∘ is the composition of functions. Such an element σ is called a generalised inverse of τ. The monoid CA(G;A) itself is regular if all its elements are regular. We establish that 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 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 \mathbbF; in particular, we show that every regular linear CA is invertible when G is torsion-free elementary amenable (e.g. when G=ℤd, d ∈ ℕ) and V=\mathbbF, and that every linear CA is regular when V is finite-dimensional and G is locally finite with Char(\mathbbF) \nmid o(g) for all g ∈ G.