Consider a one-dimensional cellular automaton operating on periodic lattices of cells each having two states. If the size of the periodic lattice is s , then there are possible configurations of cell states on the lattice. Each configuration maps to a new configuration under the action of the cellular automaton rule. Thus, we think of the configuration as a node in a graph, with an out-going arc leading to its successor configuration. As the number of possible configurations is finite, any initial configuration must map eventually to a temporally periodic cycle.
Most cellular automata are irreversible.
That is, some configurations have more than one possible ancestor, so the evolution cannot be run deterministically backward in time. The leaves of the trees are the configurations which have no preimages, the so-called Gardens of Eden. In the opposite extreme, configurations on cycles have preimages infinitely far back in time. Configurations on the branches of the trees have intermediate length histories. One way to characterize cellular automata, then, is by the shape of their transient trees.