Date of Award
Graphs are a popular model in mathematics, and automata, or abstract models of machines, are a useful tool in computer science. Our research looks at combining these two powerful fields. We will begin by looking at some pre liminaries of graph theory and automata theory. We also discuss other meth ods for recognizing graph properties such as algebras, grammars, and monadic second-order logic. We will then explore the concept of “intelligent graphs,” or networks of finite automata operating at each vertex of a graph, and we will show implementations for using such networks to solve labryinth problems and to compute block decompositions of graphs. We end by taking a look at extending this method to the problem of finding linkages in a graph.
Byrum, Cameron Taylor, "Graph Theoretical Problems Computable by Networks of Finite Automata." (2009). Honors Theses. 1963.