EXTENSIONS IN REVERSIBLE ONE-DIMENSIONAL CELLULAR AUTOMATA ARE EQUIVALENT WITH THE FULL SHIFT

Juan Carlos Seck Tuoh Mora (), Manuel González Hernáandez (), Genaro Juárez Martínez () and Sergio V. Chapa Vergara ()
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, 42184 Pachuca, México
Manuel González Hernáandez: Centro de Investigación Avanzada en Ingeniería Industrial, Universidad Autónoma del Estado de Hidalgo, Ciudad Universitaria, Carr. Pachuca-Tulancingo Km. 4.5, 42184 Pachuca, México
Genaro Juárez Martínez: Depto. de Ingeniería Eléctrica, Sección Computación, CINVESTAV-IPN, Av. IPN 2508, Col. San Pedro Zacatenco, 07300 DF, México
Sergio V. Chapa Vergara: Depto. de Ingeniería Eléctrica, Sección Computación, CINVESTAV-IPN, Av. IPN 2508, Col. San Pedro Zacatenco, 07300 DF, México

International Journal of Modern Physics C (IJMPC), 2003, vol. 14, issue 08, 1143-1160

Abstract: Cellular automata are discrete dynamical systems based on simple local interactions among its components, but sometimes they are able to yield quite a complex global behavior. A special kind of cellular automaton is the one where the global behavior is invertible, this type of cellular automaton is called reversible. In this paper we expose the graph representation provided by de Bruijn diagrams of reversible one-dimensional cellular automata and we define the distinct types of paths between self-loops in such diagrams. With this, we establish the way in which a reversible one-dimensional cellular automaton generates sequences composed by subsequences produced by the undefined repetition of a single state. Using this graph presentation, we define Welch diagrams which will be useful for proving that all the extensions of the ancestors in reversible one-dimensional cellular automata are equivalent to the full shift. In this way an important result of this paper is that we understand and classify the behavior of a reversible automaton analyzing the extensions of the ancestors of a given sequence by means of symbolic dynamics tools. A final example illustrates the results exposed in the paper.

Keywords: Reversible automata; Welch diagrams; amalgamations (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/S012918310300525X
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:08:n:s012918310300525x

Ordering information: This journal article can be ordered from

DOI: 10.1142/S012918310300525X

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 ().