Summary
In conclusion, there are two aspects of graph theory which are important for automata theory. One, typified by the use of classical de Bruijn diagrams and their subdiagrams, portrays the relationships between components of the automaton, such as the individual neighborhoods or partial neighborhoods, and the evolution of the automaton. This application emphasizes several aspects of graph theory, motivating the introduction of operations on graphs which adequately describe properties of the automaton.
Among these are the ordering of graphs, homomorphisms between graphs, and such operations as the formation of cartesian products and dual graphs. The characterization of homomorphism in terms of matrices embodied in Equations 3 and 16 has long been known to mathematicians with varying degrees of formality, but deserves to be emphasized anew. The definition of duals via the RC factorization is more original, probably because it relates better to ``digraphs'' than to the structure traditionally called a graph.
Consequently, it is a step away from the classical treatments of graph theory, such as Ore's American Mathematical Society monograph [27]; treatments which were more content with simply describing and classifying graphs.
Not only that, but the requirements of the application to automata theory oblige us to consider several alternative approaches to graphs not ordinarily considered part of graph theory, such as the description of graphs by symbolic equations, and their representation by regular expressions. Likewise the topological matrix, or connectivity matrix, is intimately related to properties considered essential to the understanding of automata, requiring a working knowledge of the class of positive matrices.
The second aspect of graph theory concerns its relation to probability theory, via the topological matrix, probabilistic evolution, and probabilistic de Bruijn diagrams. Strictly, interest lies in the application of detailed properties of positive matrices and the Frobenius-Perron theory to all the structures which have been constructed with the aid of graph theory in the earlier sections of the article.
Probabilistic de Bruijn matrices describe correlations between overlapping cell blocks in an automaton. Yet another class of diagram, evolution diagrams, has its probabilistic version; thus either type of diagram has a probabilistic version which could be of concern. Some interesting recently published papers have dealt with establishing and then solving equations for self-consistent probabilities for clusters of cells [28,29].
So, although it is not part of graph theory, automata theory brings about an interesting application of the classical Perron-Frobenius theory to certain classes of graphs --- the de Bruijn diagrams and evolutionary diagrams --- which might otherwise have escaped such attention; and in the process some interesting new characteristics of graphs are revealed.
Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx