Honors Theses

Date of Award


Document Type

Undergraduate Thesis



First Advisor

Laura Sheppardson

Relational Format



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.

Accessibility Status

Searchable text



To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.