Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1898954 | Physica D: Nonlinear Phenomena | 2007 | 17 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Applied Mathematics
Authors
Iztok Jeras, Andrej Dobnikar,