TY - JOUR
T1 - Block invariance and reversibility of one dimensional linear cellular automata
AU - MacLean, Stephanie
AU - Montalva-Medel, Marco
AU - Goles, Eric
N1 - Publisher Copyright:
© 2019 Elsevier Inc.
PY - 2019/4
Y1 - 2019/4
N2 - Consider a one-dimensional, binary cellular automaton f (the CA rule), where its n nodes are updated according to a deterministic block update (blocks that group all the nodes and such that its order is given by the order of the blocks from left to right and nodes inside a block are updated synchronously). A CA rule is block invariant over a family F of block updates if its set of periodic points does not change, whatever the block update of F is considered. In this work, we study the block invariance of linear CA rules by means of the property of reversibility of the automaton because such a property implies that every configuration has a unique predecessor, so, it is periodic. Specifically, we extend the study of reversibility done for the Wolfram elementary CA rules 90 and 150 as well as, we analyze the reversibility of linear rules with neighbourhood radius 2 by using matrix algebra techniques.
AB - Consider a one-dimensional, binary cellular automaton f (the CA rule), where its n nodes are updated according to a deterministic block update (blocks that group all the nodes and such that its order is given by the order of the blocks from left to right and nodes inside a block are updated synchronously). A CA rule is block invariant over a family F of block updates if its set of periodic points does not change, whatever the block update of F is considered. In this work, we study the block invariance of linear CA rules by means of the property of reversibility of the automaton because such a property implies that every configuration has a unique predecessor, so, it is periodic. Specifically, we extend the study of reversibility done for the Wolfram elementary CA rules 90 and 150 as well as, we analyze the reversibility of linear rules with neighbourhood radius 2 by using matrix algebra techniques.
KW - Block invariance
KW - Cellular automata
KW - Linear cellular automata
KW - Reversibility
UR - http://www.scopus.com/inward/record.url?scp=85060351335&partnerID=8YFLogxK
U2 - 10.1016/j.aam.2019.01.003
DO - 10.1016/j.aam.2019.01.003
M3 - Article
AN - SCOPUS:85060351335
SN - 0196-8858
VL - 105
SP - 83
EP - 101
JO - Advances in Applied Mathematics
JF - Advances in Applied Mathematics
ER -