Elementary, finite and linear vN-regular cellular automata

DOI10.1016/J.IC.2020.104533zbMATH Open1465.68188arXiv1804.00511OpenAlexW2795531320MaRDI QIDQ2201792FDOQ2201792

Alonso Castillo-Ramirez, Maximilien Gadouleau

Publication date: 17 September 2020

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Theory of cellular automata: a survey
• Applications of a New K-Theoretic Theorem to Soluble Group Rings
• Pseudo-Inverses in Associative Rings and Semigroups
• Cellular Automata and Groups
• The rank of the endomorphism monoid of a uniform partition.
• Ranks of finite semigroups of one-dimensional cellular automata
• On the Group Ring
• On Regular Group Rings
• A note on regular group rings
• Von Neumann regular cellular automata
• Classification of Elementary Cellular Automata Up to Topological Conjugacy
• Generalized reversibility of topological dynamical systems and cellular automata
• On Finite Monoids of Cellular Automata

Cited In (3)

• A generalization of cellular automata over groups
• Complete sets of initial vectors for pattern growth with elementary cellular automata
• On von Neumann regularity of cellular automata

   Recommendations

• Von Neumann regular cellular automata 👍 👎
• Title not available (Why is that?) 👍 👎
• 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 👍 👎
• Title not available (Why is that?) 👍 👎

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)