Conservation Functions for 1-D Automata: Efficient Algorithms, New Results, and a Partial Taxonomy
Leemon Baird and Barry Fagin
We present theorems that can be used for improved efficiency in the calculation of conservation functions for cellular automata. We report results obtained from implementations of algorithms based on these theorems that show conservation laws for 1-D cellular automata of higher order than any previously known. We introduce the notion of trivial and core conservation functions to distinguish truly new conservation functions from simple extensions of lower-order ones. We then present the complete list of conservation functions up to order 16 for the 256 elementary 1-d binary cellular automata. These include CAs that were not previously known to have nontrivial conservation functions.