Skip to main content

Research Repository

Advanced Search

Spectral properties of reversible one-dimensional cellular automata

Authors

Sergio V.Chapa Vergara

Juan Carlos Seck Tuoh Mora

Harold V. McIntosh



Abstract

Reversible cellular automata are invertible dynamical systems characterized by discreteness, determinism and local interaction. This article studies the local behavior of reversible one-dimensional cellular automata by means of the spectral properties of their connectivity matrices. We use the transformation of every one-dimensional cellular automaton to another of neighborhood size 2 to generalize the results exposed in this paper. In particular we prove that the connectivity matrices have a single positive eigenvalue equal to 1; based on this result we also prove the idempotent behavior of these matrices. The significance of this property lies in the implementation of a matrix technique for detecting whether a one-dimensional cellular automaton is reversible or not. In particular, we present a procedure using the eigenvectors of these matrices to find the inverse rule of a given reversible one-dimensional cellular automaton. Finally illustrative examples are provided.

Citation

Martínez, G. J., Vergara, S. V., Mora, J. C. S. T., & McIntosh, H. V. (2003). Spectral properties of reversible one-dimensional cellular automata. International Journal of Modern Physics C, 14(3), 379-395. https://doi.org/10.1142/S0129183103004541

Journal Article Type Article
Publication Date Mar 1, 2003
Journal International Journal of Modern Physics C
Print ISSN 0129-1831
Publisher World Scientific Publishing
Peer Reviewed Peer Reviewed
Volume 14
Issue 3
Pages 379-395
DOI https://doi.org/10.1142/S0129183103004541
Keywords cellular automata, spectrum of graphs, idempotent behavior
Public URL https://uwe-repository.worktribe.com/output/1074037
Publisher URL http://dx.doi.org/10.1142/S0129183103004541
Additional Information Additional Information : Electronic version of an article published as International Journal of Bifurcation and Chaos, Vol. 14, issue 3, 2003, pp. 379-395 DOI: 10.1142/S0129183103004541 © World Scientific Publishing Company http://www.worldscinet.com/ijmpc/14/1403/S0129183103004541.html

Files







Downloadable Citations