Neighborhood matrix

To form complex symbolic expressions, the language of regular expressions is convenient, whose operations are union, concatenation, and iteration. Another operation which is sometimes useful is the overlapping (whose symbol could be ) of two strings; if the words ax and yb each consist of letters a and b, joined to the shorter words x and y, then:

( is the empty word).

With such notation a symbolic de Bruijn matrix


could be defined; the symbolic form of the matrix shown above would be 0.30em

dots now represent the empty word. Such matrices would be multiplied by using to multiply individual matrix elements. Subsequently the advantage of substituting images --- such as the evolved cell --- for the symbolic neighborhoods will be seen. The full neighborhood matrix is rarely used, but it serves to illustrate very explicitly the involvement of the row indices and the column indices with the individual matrix elements.

Harold V. McIntosh