Linear Cellular Automata

Linear Cellular Automata
Harold V. McIntosh

This paper is available in Acrobat PDF (lcau.pdf).

Reversible Cellular Automata
Harold V. McIntosh

         Abstract
A reversible cellular automaton is one whose evolution, and therefore the entire past history of any configuration, can be uniquely deciphered. There are degrees of reversibility, depending upon whether the configurations considered are arbitrary, periodic, or quiescent at infinity; which are subsidiary to more general questions of injectivity and surjectivity, within a general perspective of the ancestry of configurations. Reversibility is examined within this general context, expanded to include the frequency distribution of ancestors and its moments. It is argued that the coupling of zero variance (judged from the maximum eigenvalue of the second moment matrix) with zero frequency for zero ancestors (surjectivity) is the fundamental concept. An ideal theoretic property inherent in decompositions of the de Bruijn matrix suffices to prove the coupling for automata. Surjectivity in different contexts, injectivity, and degrees of multiple valuedness all follow from this central result. Although the article is intended as a review, it is far from a complete historical survey; the presentation is uniformized through the use of graphs, de Bruijn diagrams and matrices wherever possible.     This paper is available in Acrobat PDF (rca.pdf).

Linear Cellular Automata Via de Bruijn Diagrams
Harold V. McIntosh

   Abstract
Graph theory plays several important roles in the theory of cellular automata, one of which consists in describing the evolution of the automaton, and another of which consists in relating local properties to global properties. Evolution is described by local rules mapping cell neighborhoods into its subsequent state; because successive neighborhoods overlap it is important to be able to take the overlap into account when relating the behavior of successive cells to one another. In illustration, the de Bruijn diagram and its subdiagrams are applied to the study of cellular automata in one dimension.      This paper is available in Acrobat PDF (debruijn.pdf).

What Has and What Hasn't Been Done with Cellular Automata
Harold V. McIntosh

   Abstract
Research on the subject of cellular automata is surveyed, with the intention of distinguishing between what has and what has not been accomplished during the course of its history.     This paper is available in Acrobat PDF (what.pdf).