LCA
Linear Cellular Automata.
Abstract A text book about linear cellular automata This paper is available in PDF lcau.pdf).
RCA
Reversible Cellular Automata.
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 PDF (rca.pdf).
DE BRUIJN
Linear Cellular Automata Via de Bruijn Diagrams.
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 PDF (debruijn.pdf).
What Has and What Hasn't...
What Has and What Hasn't Been Done with Cellular Automata.
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 PDF (what.pdf).