Title:
Computation of Explicit Preimages in One-Dimensional Cellular Automata Applying the De Bruijn Diagram
Author(s):
José Soto
Paper #:
06-02-005
Date:
Feb. 1, 2006
Abstract:
In this paper it is shown how to simplify the calculation of preimages in cellular automata. The method is based on the so-called De Bruijn diagrams and works for any k-states and r-radius in one-dimensional space. In order to calculate preimages, we construct preimage matrices from the De Bruijn diagram and an operator defined on these matrices. In this way the problem of calculating preimages is reduced to solving the classic "Path Finding Problem" in graph theory, where all possible paths are the preimages of the cellular automaton.
Facebook
Twitter
Email Newsletter
SFI News Feed
Google+
YouTube
iTunes U