A cellular automaton (CA) is in a homogeneous configuration if every cell has the same state. The preimages of a configuration s are those configurations which evolve to s within a single time step.
We present two methods of finding the total number of preimages for a given homogeneous configuration. The first is more intuitive, and gives a clear picture of how the number of preimages varies with the number of cells on which the CA operates, but it is only workable for elementary CAs (1-dimensional binary state CAs with neighbourhood size 3). The second method, based on de Bruijn matrices, is more abstract, but more readily extends to general 1-dimensional CAs.
Full paper : PDF 272K
@article(SS-JCA-11, author = "Edward J. Powley and Susan Stepney", title = "Counting preimages of homogeneous configurations in 1-dimensional cellular automata", journal = "Journal of Cellular Automata", volume = 5, number = "4-5", pages = "353-381", year = 2010 )