CALCULATING ANCESTORS IN ONE-DIMENSIONAL CELLULAR AUTOMATA
Juan Carlos Seck-Tuoh-Mora, Genaro J. Martínez, Harold V. McIntosh · International Journal of Modern Physics C · 2004
One-dimensional cellular automata are dynamical systems characterized by discreteness (in space and time), determinism and local interaction. We present a procedure to calculate the ancestors for a given sequence of states, which is based on a special kind of graph called subset diagram. We use this diagram to specify subset tables for calculating ancestors which are not Garden-of-Eden sequences, hence the process is able to yield ancestors in several generations. Some examples are illustrated using the cellular automaton Rule 110 which is the most interesting automaton of two states and three neighbors.