next up previous
Next: Garden of Eden Up: Linear Cellular Automata via Previous: Structural observations

Use of the subset diagrams

An excellent application of the subset construction to linear cellular automata is to the search for the Garden of Eden---configurations which cannot evolve from any predecessor. The problem has two settings---for finite or periodically closed automata in which it is trivial due to finiteness, and for infinite automata. Later, the problem can be generalized to counting the counterimages, calculating the frequency distribution of the multiplicity of counterimages, and establishing the relationship between singlevaluedness and invertibility.





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