PapersNo Access

UNCONVENTIONAL INVERTIBLE BEHAVIORS IN REVERSIBLE ONE-DIMENSIONAL CELLULAR AUTOMATA

Centro de Investigación Avanzada en Ingeniería Industrial, UAEH, Carr. Pachuca Tulancingo Km. 4.5, Pachuca Hidalgo 42184, Mexico

Author for correspondence.

Search for more papers by this author

MANUEL GONZÁLEZ HERNÁNDEZ

Centro de Investigación Avanzada en Ingeniería Industrial, UAEH, Carr. Pachuca Tulancingo Km. 4.5, Pachuca Hidalgo 42184, Mexico

Search for more papers by this author

GENARO JUÁREZ MARTÍNEZ

Faculty of Computing, Engineering and Mathematical Sciences, University of the West of England, United Kingdom

Search for more papers by this author

SERGIO V. CHAPA VERGARA

Departamento de Computación, CINVESTAV-IPN, Av. IPN No. 2508, Mexico, D.F. 07360, Mexico

Search for more papers by this author

, and

HAROLD V. McINTOSH

Departamento de Aplicación de Microcomputadoras, BUAP, Apartado postal 461, 72000 Puebla, Puebla, Mexico

Search for more papers by this author

https://doi.org/10.1142/S0218127408022597Cited by:0 (Source: Crossref)

Abstract

Reversible cellular automata are discrete invertible dynamical systems determined by local interactions among their components. For the one-dimensional case, there are classical references providing a complete characterization based on combinatorial properties. Using these results and the simulation of every automaton by another with neighborhood size 2, this paper describes other types of invertible behaviors embedded in these systems different from the classical one observed in the temporal evolution. In particular, spatial reversibility and diagonal surjectivity are studied, and the generation of macrocells in the evolution space is analyzed.

Keywords:

References

A. Adamatzky (ed.) , Collision-Based Computing ( Springer , 2003 ) . Google Scholar
S. Amoroso and Y. Patt, J. Comput. Syst. Sci. 6, 448 (1972). Crossref, Google Scholar
Boykett, T. [1997] "Comparism of radius 1/2 and radius 1 paradigms in one-dimensional reversible cellular automata," http://verdi.algebra.uni-linz.ac.at/~tim . Google Scholar
Boykett, T. [2003] "Orderly algorithm to enumerate central grupoids," http://www.algebra.uni-linz.ac.at/~tim/pubs.html . Google Scholar
T. Boykett, Theor. Comput. Sci. 325, 215 (2004), DOI: 10.1016/j.tcs.2004.06.007. Crossref, Web of Science, Google Scholar
Boykett, T. [2006] "Towards a noetherlike conservation law theorem for one-dimensional reversible cellular automata," http://www.algebra.uni-linz.ac.at/~tim/pubs.html . Google Scholar
D. B. Brown, Compl. Syst. 1, 169 (1987). Web of Science, Google Scholar
B. Chopard and M. Droz (eds.) , Cellular Automata Modeling of Physical Systems ( Cambridge University Press , 1998 ) . Crossref, Google Scholar
G. A. Hedlund, Math. Syst. Th. 3, 320 (1969), DOI: 10.1007/BF01691062. Crossref, Google Scholar
D. Hillman, Physica D 52, 277 (1991), DOI: 10.1016/0167-2789(91)90128-V. Crossref, Web of Science, Google Scholar
Hillman, D. [2004] "Combinatorial dynamics," http://www.wolframscience.com/conference/2004/presentations . Google Scholar
Kari, J. [1992a] "Cryptosystems based on rever-sible cellular automata," http://citeseer.ist.psu.edu/kari92cryptosystems.html . Google Scholar
J. Kari, Lindenmayer Systems. Impacts on Theoretical Computer Science, Computer Graphics, and Developmental Biology, eds. G. Rozenberg and A. Salomaa (Springer-Verlag, 1992) pp. 477–495. Crossref, Google Scholar
H. V. McIntosh, Physica D 45, 105 (1990), DOI: 10.1016/0167-2789(90)90177-Q. Crossref, Web of Science, Google Scholar
E. F. Moore , Machine Models of Self-Reproduction ( University of Illinois Press , 1970 ) . Google Scholar
H. Moraal, Physica D 141, 1 (2000), DOI: 10.1016/S0167-2789(00)00020-8. Crossref, Web of Science, Google Scholar
J. Myhill, P. Am. Math. Soc. 14, 685 (1963), DOI: 10.2307/2034301. Web of Science, Google Scholar
M. Nasu, Math. Syst. Th. 11, 327 (1978), DOI: 10.1007/BF01768485. Crossref, Google Scholar
J. C. Seck-Tuoh, J. Phys. A-Math. Gen. 35, 5563 (2002). Google Scholar
J. C. Seck-Tuohet al., Int. J. Mod. Phys. C 14, 1143 (2003). Web of Science, Google Scholar
J. C. Seck-Tuoh, G. Juárez-Martínez and H. V. McIntosh, TUCS Gen. Publ. 32, 54 (2004). Google Scholar
J. C. Seck-Tuohet al., Physica D 202, 134 (2005). Crossref, Web of Science, Google Scholar
J. C. Seck-Tuoh, G. Juárez-Martínez and H. V. McIntosh, J. Cell. Automata 1, 25 (2006). Web of Science, Google Scholar
T. Toffoli and N. Margolus , Cellular Automata Machines ( MIT Press , London , 1987 ) . Crossref, Google Scholar
T. Toffoli and N. Margolus, Cellular Automata: Theory and Experiment, ed. H. A. Gutowitz (MIT/North-Holland, 1991) pp. 229–253. Google Scholar
J. von Neumann , Theory of Self-Reproducing Automata , ed. A. W. Burks ( University of Illinois Press , Urbana and London , 1966 ) . Google Scholar
S. Wolfram (ed.) , Theory and Applications of Cellular Automata ( World Scientific , Singapore , 1986 ) . Google Scholar