TY - JOUR

T1 - Block invariance and reversibility of one dimensional linear cellular automata

AU - MacLean, Stephanie

AU - Montalva-Medel, Marco

AU - Goles, Eric

N1 - Funding Information:
This work was partially supported by FONDECYT Iniciación 11150827 (M.M-M.), CONICYT 21160688 (S.M.), Basal CMM, ECOS C16E01 (S.M., M.M-M., E.G.) and UAI Project 2018.
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

VL - 105

SP - 83

EP - 101

JO - Advances in Applied Mathematics

JF - Advances in Applied Mathematics

SN - 0196-8858

ER -