Attractors of Linear Cellular Automata

✍ Scribed by Giovanni Manzini; Luciano Margara

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 147 KB
• Volume: 58
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1006/jcss.1998.1609

✦ Synopsis

In this paper we study the asymptotic behavior of D-dimensional linear cellular automata over the ring Z m (D 1, m 2). In the first part of the paper we consider nonsurjective cellular automata (CA). We prove that, after a transient phase of length at most wlog 2 mx, the evolution of a linear nonsurjective 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 Z m . In the second part of the paper, we study the attractor sets of linear cellular automata. Recently, Kurka 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.