Computation of Predecessor States for Composite Elementary Cellular Automata
Burton Voorhees
Faculty of Science, Athabasca University,
Box 10,000, Athabasca, AB
CANADA T0G 2R0
Abstract
We consider 3-site binary valued one-dimensional cellular automata rules which are the composition of two 2-site rules. For such rules an algorithmic procedure that is simpler than backward reconstruction is given allowing the computation of all predecessors of any given state. Results obtained are compared to results in [1] on the enumeration of preimages of finite strings. A question relating to Garden-of-Eden states is clarified, and an example is given to illustrate a theorem from [2] to the effect that for nonsurjective rules there exist periodic sequences having an uncountable number of predecessors.
