Algorithms for computing preimages of cellular automata configurations

This paper investigates pre-images (ancestors or past configurations) of specified configurations of one-dimensional cellular automata. Both counting and listing of pre-images are discussed. The main graphical tools used are the de Bruijn diagram, and its extension the pre-image network, which is created by concatenating de Bruijn diagrams. The counting of pre-images is performed as the multiplication of topological matrices of de Bruijn diagrams. Listing of pre-images is described using two algorithms. The first algorithm traces paths in the pre-image network and focuses on local knowledge of the network. The second performs a complete analysis of the network before proceeding with listing. (c) 2007 Elsevier B.V. All rights reserved.