The structure and behavior of cellular automata

Abstract

A cellular automaton (or CA) is an interconnected set of finite state machines (or cells) such that the inputs of each cell are connected to the outputs of k "neighboring" cells, and the next state of each cell is a function of the present states of its neighboring cells. A CA is uniform if its connection graph is an edge labelled group graph [E.G. WAGNER, IEEE Trans. Elec. Comp., EC-15 (1966), pp 861-873]. A structural homomorphism exists from a CA N1 onto another CA N2 if N2 can effectively be "embedded" in N1. It is proved that neighborhood preserving functions [H. YAMADA and S. AMOROSO, Info. Contr. 18 (1971), pp 1-32] are equivalent to graphical homomorphisms that preserve edge labelling. It is shown that a sufficient condition for the existence of a structural homomorphism from some uniform CA onto another CA N2 is that any cell in N2 be the ith neighbor of exactly one cell in the CA, for all i, Furthermore, when N2 has a finite number of cells, this condition is also necessary. If N2 meets this condition, then a method is shown to construct the smallest CA N1 such