Decidability and Characterization of Expansivity for Group Cellular Automata
By: Niccolo' Castronuovo, Alberto Dennunzio, Luciano Margara
Potential Business Impact:
Makes computer rules predictable and understandable.
Group cellular automata are continuous, shift-commuting endomorphisms of $G^\mathbb{Z}$, where $G$ is a finite group. We provide an easy-to-check characterization of expansivity for group cellular automata on abelian groups and we prove that expansivity is a decidable property for general (non-abelian) groups. Moreover, we show that the class of expansive group cellular automata is strictly contained in that of topologically transitive injective group cellular automata.
Similar Papers
A Divide and Conquer Algorithm for Deciding Group Cellular Automata Dynamics
Formal Languages and Automata Theory
Simplifies complex computer programs for easier study.
Word problems and embedding-obstructions in cellular automata groups on groups
Group Theory
Makes computers solve harder puzzles faster.
On the order of lazy cellular automata
Formal Languages and Automata Theory
Makes simple computer rules behave in predictable ways.