SPECTRAL PROPERTIES OF REVERSIBLE ONE-DIMENSIONAL CELLULAR AUTOMATA

Juan Carlos Seck Tuoh Mora (), Sergio V. Chapa Vergara (), Genaro Juárez Martínez () and V. McINTOSH Harold
Additional contact information
Juan Carlos Seck Tuoh Mora: Centro de Investigación Avanzada en Ingeniería Industrial, Universidad Autónoma del Estado de Hidalgo, Ciudad Universitaria, Carr. Pachuca-Tulancingo Km 4.5 Pachuca, Hidalgo, México
Sergio V. Chapa Vergara: Departamento de Ingeniería Eléctrica, Sección Computación, CINVESTAV-IPN., Av IPN 2508, Col San Pedro Zacatenco, México 07360 D.F., México
Genaro Juárez Martínez: Departamento de Ingeniería Eléctrica, Sección Computación, CINVESTAV-IPN., Av IPN 2508, Col San Pedro Zacatenco, México 07360 D.F., México
V. McINTOSH Harold: Departamento de Aplicación de Microcomputadoras, Instituto de Ciencias, UAP, México

International Journal of Modern Physics C (IJMPC), 2003, vol. 14, issue 03, 379-395

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.

Keywords: Cellular automata; spectrum of graphs; idempotent behavior (search for similar items in EconPapers)
Date: 2003
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0129183103004541
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:ijmpcx:v:14:y:2003:i:03:n:s0129183103004541

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0129183103004541

Access Statistics for this article

International Journal of Modern Physics C (IJMPC) is currently edited by H. J. Herrmann

More articles in International Journal of Modern Physics C (IJMPC) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().