Connections between the minimal neighborhood and the activity value of cellular automata
Preprint
Abstract
For a group $G$ and a finite set $A$, a cellular automaton is a transformation of the configuration space $A^G$ defined via a finite neighborhood and a local map. Although neighborhoods are not unique, every CA admits a unique minimal neighborhood, which consists on all the essential cells in $G$ that affect the behavior of the local map. An active transition of a cellular automaton is a pattern that produces a change on the current state of a cell when the local map is applied. In this paper, we study the links between the minimal neighborhood and the number of active transitions, known as the activity value, of cellular automata. Our main results state that the activity value usually imposes several restrictions on the size of the minimal neighborhood of local maps.
Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- On the Minimal Memory Set of Cellular Automata2024
- A generalization of cellular automata over groupsCommunications in Algebra, 2023
- From Multiple to Single Updates Per Cell in Elementary Cellular Automata with Neighbourhood Based Priority2022
- Introducing the activity parameter for elementary cellular automataInternational Journal of Modern Physics C, 2022
- Characterisation of the elementary cellular automata with neighbourhood priority based deterministic updatesCommunications in Nonlinear Science and Numerical Simulation, 2022
- Elementary, finite and linear vN-regular cellular automataInformation and Computation, 2020
- A tutorial on elementary cellular automata with fully asynchronous updatingNatural Computing, 2020
- Tables of Cellular Automaton Properties2018
- Asynchronous Cellular Automata2018
- Theory of cellular automata: A surveyTheoretical Computer Science, 2005