Abstract

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.

@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 )