Computation of Explicit Preimages in One-Dimensional Cellular Automata Applying the De Bruijn Diagram

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.