Effective Projections on Group Shifts to Decide Properties of Group Cellular Automata
From MaRDI portal
Publication:6154975
DOI10.1142/S0129054123480040arXiv2301.11133MaRDI QIDQ6154975FDOQ6154975
Authors: Pierre Béaur, Jarkko Kari 
Publication date: 16 February 2024
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
Abstract: Many decision problems concerning cellular automata are known to be decidable in the case of algebraic cellular automata, that is, when the state set has an algebraic structure and the automaton acts as a morphism. The most studied cases include finite fields, finite commutative rings and finite commutative groups. In this paper, we provide methods to generalize these results to the broader case of group cellular automata, that is, the case where the state set is a finite (possibly non-commutative) finite group. The configuration space is not even necessarily the full shift but a subshift -- called a group shift -- that is a subgroup of the full shift on Z^d, for any number d of dimensions. We show, in particular, that injectivity, surjectivity, equicontinuity, sensitivity and nilpotency are decidable for group cellular automata, and non-transitivity is semi-decidable. Injectivity always implies surjectivity, and jointly periodic points are dense in the limit set. The Moore direction of the Garden-of-Eden theorem holds for all group cellular automata, while the Myhill direction fails in some cases. The proofs are based on effective projection operations on group shifts that are, in particular, applied on the set of valid space-time diagrams of group cellular automata. This allows one to effectively construct the traces and the limit sets of group cellular automata. A preliminary version of this work was presented at the conference Mathematical Foundations of Computer Science 2020.
Full work available at URL: https://arxiv.org/abs/2301.11133
Recommendations
Cites Work
- Theory of cellular automata: a survey
- Title not available (Why is that?)
- An Introduction to Symbolic Dynamics and Coding
- Endomorphisms and automorphisms of the shift dynamical system
- Dynamical systems of algebraic origin
- Some properties of cellular automata with equicontinuity points
- Automorphisms of compact groups
- Title not available (Why is that?)
- Reversibility and surjectivity problems of cellular automata
- Solution of some conjectures about topological properties of linear cellular automata
- The Nilpotency Problem of One-Dimensional Cellular Automata
- Periodic points for onto cellular automata
- On the dynamics and recursive properties of multidimensional symbolic systems
- Cellular automata and strongly irreducible shifts of finite type.
- Cellular automata and groups
- Title not available (Why is that?)
- Shorter Note: The Converse of Moore's Garden-of-Eden Theorem
- Periodicity and Immortality in Reversible Computing
- Multidimensional cellular automata and generalization of Fekete's Lemma
- Sensitivity and topological mixing are undecidable for reversible one-dimensional cellular automata
- Title not available (Why is that?)
- Linear sampling and the ∀∃∀ case of the decision problem
- Title not available (Why is that?)
- Dynamical behavior of additive cellular automata over finite abelian groups
- On the dynamical behaviour of linear higher-order cellular automata and its decidability
- Decidability in Group Shifts and Group Cellular Automata
Cited In (1)
This page was built for publication: Effective Projections on Group Shifts to Decide Properties of Group Cellular Automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6154975)
