Introduction

An automaton has states and mappings between its states. The concept arose from electrical switching theory, but thanks to the pioneering work of Claude Shannon [1], boolean algebra and probability theory were seen to have an important role in the theory of switching networks. Speculation concerning the relationship between logical processes and the physiology of the nervous system, modelled by networks of cells, had early origins in the work of Warren McCulloch and Walter Pitts [2]. Numerous subsequent investigators have contributed to the subject, in forms ranging all the way from abstract mathematical logic and formal language theory to concrete engineering and biological simulations and experiments.

A cellular automaton lends itself to rigorous analysis because of the symmetry inherent in a crystallographic lattice of individual automata---the cells---and the assumption that individual changes of state depend solely on the states of a limited number of neighbors. At first sight the extensive overlapping between neighborhoods of different cells seemed to confuse the issue, but then it was found that certain ideas used in shift register theory and various techniques from information theory took care of the overlapping in a very natural and elegant way.

Without going into the details of automata theory, our objective is to present graph theory from a point of view useful for automata theory, while also exhibiting some important theorems for this application.

---

Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx