E-viri
Recenzirano
-
Jeras, Iztok; Dobnikar, Andrej
Physica. D, 09/2007, Letnik: 233, Številka: 2Journal Article
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.
