TY - JOUR
T1 - Block invariance in elementary cellular automata
AU - Goles, Eric
AU - Montalva-Medel, Marco
AU - Mortveit, Henning
AU - Ramirez-Flandes, Salvador
N1 - Publisher Copyright:
© 2015 Old City Publishing, Inc.
PY - 2015
Y1 - 2015
N2 - Consider an elementary cellular automaton (ECA) under periodic boundary conditions. Given an arbitrary partition of the set of vertices we consider the block updating, i.e. the automaton’s local function is applied from the first to the last set of the partition such that vertices belonging to the same set are updated synchronously. The automaton is said block-invariant if the set of periodic configurations is independent of the choice of the block updating. When the sets of the partition are singletons we have the sequential updating: vertices are updated one by one following a permutation π. In [5] the authors analyzed the π- invariance of the 28 = 256 possible ECA rules (or the 88 non-redundant rules subset). Their main result was that for all n > 3, exactly 41 of these non-redundant rules are π-invariant. In this paper we determine the subset of these 41 rules that are block invariant. More precisely, for all n > 3, exactly 15 of these rules are block invariant. Moreover, we deduce that block invariance also implies that the attractor structure itself is independent of the choice of the block update.
AB - Consider an elementary cellular automaton (ECA) under periodic boundary conditions. Given an arbitrary partition of the set of vertices we consider the block updating, i.e. the automaton’s local function is applied from the first to the last set of the partition such that vertices belonging to the same set are updated synchronously. The automaton is said block-invariant if the set of periodic configurations is independent of the choice of the block updating. When the sets of the partition are singletons we have the sequential updating: vertices are updated one by one following a permutation π. In [5] the authors analyzed the π- invariance of the 28 = 256 possible ECA rules (or the 88 non-redundant rules subset). Their main result was that for all n > 3, exactly 41 of these non-redundant rules are π-invariant. In this paper we determine the subset of these 41 rules that are block invariant. More precisely, for all n > 3, exactly 15 of these rules are block invariant. Moreover, we deduce that block invariance also implies that the attractor structure itself is independent of the choice of the block update.
KW - Block invariance
KW - Block updates
KW - Elementary cellular automata
KW - Periodic points
UR - http://www.scopus.com/inward/record.url?scp=84923247753&partnerID=8YFLogxK
M3 - Article
AN - SCOPUS:84923247753
SN - 1557-5969
VL - 10
SP - 119
EP - 135
JO - Journal of Cellular Automata
JF - Journal of Cellular Automata
IS - 1-2
ER -