Spectral properties of reversible one-dimensional cellular automata

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