Combinatorial Structure of PreImage Trees in Cellular Automata
Henryk Fuks
Brock University
Abstract
Starting with a given string of symbols, one can easily construct a set
of its preimages under a given cellular automata rule. For each of these preimages, one can compute a set of further preimages, and one can repeat this procedure iteratively, producing a graph that we call a preimage tree. For some elementary cellular automata rules, such as rules possessing additive invariants, preimage trees exhibit striking regularities. We will show how to explain these regularities using combinatorial arguments involving generating functions.


