Algebraic Methods for Finite Linear Cellular Automata

Abstract

Cellular automata are a simple class of extended dynamical systems which have been much studied in recent years. Linear cellular automata are the class of cellular automata most amenable to algebraic analytic treatments, algebraic techniques are used to study finite linear cellular automata and also finite linear cellular automata with external inputs. General results are developed for state alphabet a finite commutative ring and a notion of qualitative dynamical similarity is introduced for those systems consisting of a fixed linear cellular automata rule but with distinct time independent inputs. Sufficient conditions for qualitative dynamical similarity are obtained in the general case. Exact results are obtained for the case of state alphabet a finite field, including new results for finite linear cellular automata without inputs and a complete description of the behaviour of the corresponding system with time independent inputs. Necessary and sufficient conditions for qualitative dynamical similarity in this case are given. Results for the hitherto untreated case of state alphabet the integers modulo pk, p prime and k>1, are obtained from those for the finite field case by the technique of idempotent lifting. These two cases suffice for the treatment of the general case of st, ),t e alphabet the integers modulo any positive integer m>1, in particular a necessary and sufficient condition for qualitatively similar dynamics in the presence of time independent inputs is given for this case. The extension of the results for time independent inputs to the case of periodic and eventually periodic inputs is treated and the generalisation of the techniques developed to higher dimensional linear cellular automata is discussed.