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

摘要

This paper shows how to calculate preimages in cellular automata using the De Bruijn diagram. The method proposed 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 applied to these matrices. In this manner 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.