Discrete Baker Transformations for Linear Cellular Automata Analysis
Valeriy Bulitko, Burton Voorhees and Vadim Bulitko
We consider p-valued linear cellular automata (LCA) defined on d-dimensional discrete tori where p is prime.Iteration of an LCA rule increases its computational complexity in general, but minima appear at the iterations pk, k > 0.W e define a transparent, rule-independent procedure that yields the form of these iterates. This is called the discrete Baker transformation (DBT).Use of this transformation provides a means of addressing a number of questions about the behavior of LCA, including rule decomposition, properties of state transition diagrams (STD’s), reduction of STDs, and formalization of global features of STDs in terms of solvable systems of equations and inequalities.