Graph Theoretical Problems Computable by Networks of Finite Automata.

Author

Cameron Taylor Byrum

Date of Award

2009

Document Type

Undergraduate Thesis

Department

Mathematics

First Advisor

Laura Sheppardson

Relational Format

Dissertation/Thesis

Abstract

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.

Recommended Citation

Byrum, Cameron Taylor, "Graph Theoretical Problems Computable by Networks of Finite Automata." (2009). Honors Theses. 1963.
https://egrove.olemiss.edu/hon_thesis/1963

Accessibility Status

Searchable text