On 
-Automata
Klaus Sutner
Stevens Institute of Technology, Castle Point,
Hoboken, NJ 07030, USA
Abstract
A -automaton is a particularly simple type of cellular automaton on a graph: each cell is either in state 0 or 1 and the next state of a cell is determined by adding the states of its neighbors modulo two. Using algebraic and graph-theoretic techniques, questions such as reversibility and existence of predecessor configurations of these automata will be studied. We derive some general results for product graphs. In particular, we give a simple characterization of the number of predecessors of a configuration in rectangular grids, cylinders, and tori.
