Abstract
In this paper we study the asymptotic behavior of D-dimensional linear cellular automata over the ring Zm (D ≥ 1, m ≥ 2). In the first part of the paper we consider non-surjective cellular automata. We prove that, after a transient phase of length at most [log2, m], the evolution of a linear non-surjective cellular automata F takes place completely within a subspace Y F. This result suggests that we can get valuable information on the long term behavior of F by studying its properties when restricted to Y F. We prove that such study is possible by showing that the system (Y F , F) is topologically conjugated to a linear cellular automata F * defined over a different ring Zm. In the second part of the paper, we study the attractor sets of linear cellular automata. Recently, Kurka [8] has shown that CA can be partitioned into five disjoint classes according to the structure of their attractors. We present a procedure for deciding the membership in Kurka's classes for any linear cellular automata. Our procedure requires only gcd computations involving the coefficients of the local rule associated to the cellular automata.
Preview
Unable to display preview. Download preview PDF.
References
F. Blanchard, P. Kurka, and A. Maass. Topological and measure-theoretic properties of one-dimensional cellular automata. Physica D, 103:86–99, 1997.
G. Cattaneo, E. Formenti, G. Manzini, and L. Margara. Ergodicity and regularity for linear cellular automata over Z m. Theoretical Computer Science. To appear.
G. Cattaneo, E. Formenti, G. Manzini, and L. Margara. On ergodic linear cellular automata over Z m. In 14th Annual Symposium on Theoretical Aspects of Computer Science (STACS '97), pages 427–438. LNCS n. 1200, Springer Verlag, 1997.
R. L. Devaney. An Introduction to Chaotic Dynamical Systems. Addison-Wesley, Reading, MA, USA, second edition, 1989.
M. Garzon. Models of Massive Parallelism. EATCS Texts in Theoretical Computer Science. Springer Verlag, 1995.
M. Hurley. Attractors in cellular automata. Ergodic Theory and Dynamical Systems, 10:131–140, 1990.
M. Ito, N. Osato, and M. Nasu. Linear cellular automata over Z m. Journal of Computer and System Sciences, 27:125–140, 1983.
P. Kurka. Languages, equicontinuity and attractors in cellular automata. Ergodic theory and dynamical systems, 17:417–433, 1997.
G. Manzini and L. Margara. Invertible linear cellular automata over Z m: Algorithmic and dynamical aspects. Journal of Computer and System Sciences. To appear.
G. Manzini and L. Margara. A complete and efficiently computable topological classification of D-dimensional linear cellular automata over Zm. In 24th International Colloquium on Automata Languages and Programming (ICALP '97). LNCS n. 1256, Springer Verlag, 1997.
T. Sato. Ergodicity of linear cellular automata over Zm. Information Processing Letters, 61(3):169–172, 1997.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag
About this paper
Cite this paper
Manzini, G., Margara, L. (1998). Attractors of D-dimensional Linear Cellular Automata. In: Morvan, M., Meinel, C., Krob, D. (eds) STACS 98. STACS 1998. Lecture Notes in Computer Science, vol 1373. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0028555
Download citation
DOI: https://doi.org/10.1007/BFb0028555
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64230-5
Online ISBN: 978-3-540-69705-3
eBook Packages: Springer Book Archive