Counting Preimages of Homogeneous Configurations in 1-Dimensional Cellular Automata
Edward J. Powley and Susan Stepney
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.
Keywords: Homogeneity, preimages, de Bruijn graphs, de Bruijn matrices, spectral graph theory.