Next: Reversible automata Up: History Previous: Probability theory

# Graph theory and de Bruijn diagrams

Looking in another direction, the cells of one dimensional automata, by definition, form linear chains. But the neighborhoods themselves form another kind of chain, wherein they necessarily overlap. The result is an arrangement which has a very close connection with shift register theory [44], which is a systematic study of the properties of overlapping strings and how the overlaps happen to come about. In particular, the form of graphical representation known as the de Bruijn diagram [98] enters into many discussions, and can be used to organize a major portion of the theory.

The application to automata theory arises from labelling links in a de Bruijn diagram in two ways -- as a neighborhood N or as the evolutionary image of that neighborhood, . Including or excluding links according to various properties of either the neighborhood or its image results in a considerable variety of subdiagrams, or graphs, to be used for further study.

Graphs provide a finite frame of reference for describing the multitudinous paths corresponding to the actual configurations of an automaton; an economy of presentation which fully justifies linking graph theory with even the theory of general automata. Graphs in turn have such diverse representations as their connectivity matrix or a system of symbolic equations expressing their connectivity, not forgetting simple paper sketches of graphs which are not overly complex.

In turn the collection of paths through a diagram is readily described by such entities as polynomials in the connectivity matrix or even by regular expressions. The former permit the definition of a zeta function; the latter follow from the symbolic connectivity equations, and can be seen as an opportunity to use formal language theory to obtain further results. Both approaches have been discussed in the literature.

Still further aspects of graph theory are available to describe automata and their evolution -- such as dual diagrams, cartesian product diagrams, or mappings between diagrams. For example, product diagrams serve to compare two or more paths through the underlying graph, a comparison which can profitably be used to decide questions of uniqueness or of ambiguity.

So in one way or another it pays to be familiar with the standard results of graph theory. As it is, Masakazu Nasu [86] refers the properties of injective and surjective evolutionary functions to de Bruijn and related diagrams; Wolfram [120] himself used them to express evolutionary properties, and Erica Jen [62] has used them to calculate ancestors.

Other examples can be found in the literature. Moreover, it is always possible for a retrospective knowledge of the appropriate diagrams to facilitate the understanding of those publications whose authors did not avail themselves of graph theory. Or at the very least least, to hope that the resulting insight will lighten the burden of obtaining further results.

Next: Reversible automata Up: History Previous: Probability theory

Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx