Effective Projections on Group Shifts to Decide Properties of Group Cellular Automata
From MaRDI portal
Publication:6154975
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 4086592 (Why is no real title available?)
- scientific article; zbMATH DE number 2042127 (Why is no real title available?)
- scientific article; zbMATH DE number 2046045 (Why is no real title available?)
- scientific article; zbMATH DE number 2158945 (Why is no real title available?)
- scientific article; zbMATH DE number 3205673 (Why is no real title available?)
- An Introduction to Symbolic Dynamics and Coding
- Automorphisms of compact groups
- Cellular automata and groups
- Cellular automata and strongly irreducible shifts of finite type.
- Decidability in Group Shifts and Group Cellular Automata
- Dynamical behavior of additive cellular automata over finite abelian groups
- Dynamical systems of algebraic origin
- Endomorphisms and automorphisms of the shift dynamical system
- Linear sampling and the ∀∃∀ case of the decision problem
- Multidimensional cellular automata and generalization of Fekete's Lemma
- On the dynamical behaviour of linear higher-order cellular automata and its decidability
- On the dynamics and recursive properties of multidimensional symbolic systems
- Periodic points for onto cellular automata
- Periodicity and Immortality in Reversible Computing
- Reversibility and surjectivity problems of cellular automata
- Sensitivity and topological mixing are undecidable for reversible one-dimensional cellular automata
- Shorter Note: The Converse of Moore's Garden-of-Eden Theorem
- Solution of some conjectures about topological properties of linear cellular automata
- Some properties of cellular automata with equicontinuity points
- The Nilpotency Problem of One-Dimensional Cellular Automata
- Theory of cellular automata: a survey
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)
