Elementary, finite and linear vN-regular cellular automata

DOI10.1016/J.IC.2020.104533MaRDI QIDQ2201792zbMATHOpenAlexFDO

Authors Alonso Castillo-Ramirez, Maximilien Gadouleau

Publication date 17 September 2020

Published in Information and Computation (Search for Journal in Brave)

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

zbMATH Keywords

cellular automataelementary cellular automatamonoidslinear cellular automatageneralised inversevon Neumann regularity

Mathematics Subject Classification ID

Dynamical aspects of cellular automata (37B15) Cellular automata (computational aspects) (68Q80) Semigroups in automata theory, linguistics, etc. (20M35)

Abstract: Let $G$ be a group and $A$ a set. A cellular automaton (CA) $au$ over $A^G$ is von Neumann regular (vN-regular) if there exists a CA $sigma$ over $A^G$ such that $ausigmaau=au$, and in such case, $sigma$ is called a generalised inverse of $au$. In this paper, we investigate vN-regularity of various kinds of CA. First, we establish that, over any nontrivial configuration space, there always exist CA that are not vN-regular. Then, we obtain a partial classification of elementary vN-regular CA over ${0,1}^{mathbbZ}$; 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 finite, we obtain a full characterisation of vN-regular CA over $A^G$. Finally, we study vN-regular linear CA when $A=V$ is a vector space over a field $mathbbF$; we show that every vN-regular linear CA is invertible when $V=mathbbF$ and $G$ is torsion-free elementary amenable (e.g. when $G=mathbb{Z}^d,dinmathbbN$), and that every linear CA is vN-regular when $V$ is finite-dimensional and $G$ is locally finite with $Char(mathbbF)mido(g)$ for all $ginG$.

Recommendations

• Von Neumann regular cellular automata
• scientific article; zbMATH DE number 1665453
• Linearizable cellular automata
• Linear cellular automata, finite automata and Pascal's triangle
• Linear cellular automata and decidability
• Linear cellular automata and recurring sequences in finite fields
• Linear cellular automata and recurring sequences in finite fields
• The algebraic properties of finite cellular automata
• scientific article; zbMATH DE number 4195206

Cites work

• scientific article; zbMATH DE number 3179521 (Why is no real title available?)
• scientific article; zbMATH DE number 3638054 (Why is no real title available?)
• scientific article; zbMATH DE number 6255719 (Why is no real title available?)
• A note on regular group rings
• Applications of a New K-Theoretic Theorem to Soluble Group Rings
• Cellular automata and groups
• Classification of elementary cellular automata up to topological conjugacy
• Generalized reversibility of topological dynamical systems and cellular automata
• On Finite Monoids of Cellular Automata
• On Regular Group Rings
• On the Group Ring
• Pseudo-Inverses in Associative Rings and Semigroups
• Ranks of finite semigroups of one-dimensional cellular automata
• The rank of the endomorphism monoid of a uniform partition.
• Theory of cellular automata: a survey
• Von Neumann regular cellular automata

Cited in

(5)

• A generalization of cellular automata over groups
• On von Neumann regularity of cellular automata
• Complete sets of initial vectors for pattern growth with elementary cellular automata
• Von Neumann regularity, split epicness and elementary cellular automata
• Von Neumann regular cellular automata

This page was built for publication: Elementary, finite and linear vN-regular cellular automata

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