TY - JOUR
T1 - Invertible behavior in elementary cellular automata with memory
AU - Seck-Tuoh-Mora, Juan C.
AU - Martínez, Genaro J.
AU - Alonso-Sanz, Ramon
AU - Hernández-Romero, Norberto
N1 - Funding Information:
This work has been partially supported by CONACYT project No. CB2007-83554 and by PROMEP Collaboration Network “Modelado y análisis de sistemas complejos”.
PY - 2012/9/15
Y1 - 2012/9/15
N2 - Elementary cellular automata (ECAs) have been studied for their ability to generate complex global behavior, despite their simplicity. One variation of ECAs is obtained by adding memory to each cell in a neighborhood. This process generates a provisional configuration in which the application of an evolution rule establishes the dynamics of the system. This version is known as an ECA with memory (ECAM). Most previous work on ECAMs analyzed the complex behavior taking chaotic ECAs. However, the present paper investigates reversible ECAMs as obtained from reversible and permutative ECAs. These ECAs have at least one ancestor for every configuration; thus, the correct permutation of states may specify the memory function to obtain reversible ECAMs. For permutative ECAs, which are often irreversible, we demonstrate that the use of a quiescent state and the correct manipulation of de Bruijn blocks produce reversible ECAMs.
AB - Elementary cellular automata (ECAs) have been studied for their ability to generate complex global behavior, despite their simplicity. One variation of ECAs is obtained by adding memory to each cell in a neighborhood. This process generates a provisional configuration in which the application of an evolution rule establishes the dynamics of the system. This version is known as an ECA with memory (ECAM). Most previous work on ECAMs analyzed the complex behavior taking chaotic ECAs. However, the present paper investigates reversible ECAMs as obtained from reversible and permutative ECAs. These ECAs have at least one ancestor for every configuration; thus, the correct permutation of states may specify the memory function to obtain reversible ECAMs. For permutative ECAs, which are often irreversible, we demonstrate that the use of a quiescent state and the correct manipulation of de Bruijn blocks produce reversible ECAMs.
KW - De Bruijn block
KW - Elementary cellular automata
KW - Memory
KW - Reversibility
UR - http://www.scopus.com/inward/record.url?scp=84860228099&partnerID=8YFLogxK
U2 - 10.1016/j.ins.2012.02.063
DO - 10.1016/j.ins.2012.02.063
M3 - Artículo
AN - SCOPUS:84860228099
SN - 0020-0255
VL - 199
SP - 125
EP - 132
JO - Information Sciences
JF - Information Sciences
ER -