There are (directed) graphs, usually called de Bruijn diagrams (for k
symbols and n stages), whose nodes correspond to all the 
possible sequences of length n-1 composed of the given symbols. Their
links are sequences of length n, joining any pair of nodes where the
tail comprises the first n-1 symbols, the head the last n-1
symbols.
In other words, 1101 would link node 110 to node 101 in a four stage binary diagram.
For two-dimensional binary automata with Moore neighborhoods, it is convenient to split the 3x3 neighborhood into two 3x2 rectangles, overlapping in a central column containing three cells. Accordingly its three stage, eight symbol de Bruin diagram would have sixty four nodes, each with eight links. Taking a full column as one single eight state cell makes the structure one dimensional.
Graphs are conveniently represented by matrices, whose rows and columns are labelled by the nodes. The elements of the matrix are to be ones and zeroes, according to whether the node indexing the row is linked to the node indexing the column; in symbolic form:
Written with the link predicate, the rule of matrix multiplication,
implies that powers of such a matrix describe paths through the graph;
the 
power yields paths of length k, the sum of the first k
powers paths of length k or less. Such matrix elements will be
integers; those greater than 1 indicate a multiple path.
To make the general de Bruijn diagram correspond to a particular type of evolution, retain only those links whose neighborhoods behave properly. In the connection matrix, zeroes replace the missing links.
Powers of the de Bruijn matrix, the connectivity matrix of the diagram,
reveal sequences of neighborhoods - rectangular regions - whose
evolution proceeds correctly. In order to close the sequence into a
ring of length k, the 
power of the de Bruijn matrix should
be calculated, from which paths corresponding to the diagonal should be
culled.