Combinatorial Structure of Pre-Image Trees in Cellular Automata

Henryk Fuks

Brock University

Abstract

Starting with a given string of symbols, one can easily construct a set of its pre-images under a given cellular automata rule. For each of these pre-images, one can compute a set of further pre-images, and one can repeat this procedure iteratively, producing a graph that we call a pre-image tree. For some elementary cellular automata rules, such as rules possessing additive invariants, pre-image trees exhibit striking regularities. We will show how to explain these regularities using combinatorial arguments involving generating functions.