Computational Complexity of Automatic Structures

This dissertation creates automatic structures with complex recursion-theoretic properties. A structure is said to be automatic if its universe and relations can be recognized by a deterministic finite automaton. Although arbitrary computable structures isomorphic to an automatic structure can be surprisingly complicated, automatic copies require only a few extra conditions to be computably isomorphic to each other. The first section provides definitions and theorems necessary for creating the structures and proving their properties. The second section presents a family of automatic linear orderings, then defines a corresponding family of automatic re- lations on these structures which appear at arbitrarily high finite levels of the arithmetical hierarchy. The third section creates an automatic equivalence struc- ture, and proves that the set of isomorphic equivalence structures is as complicated as any set of isomorphic equivalence structures can be. The fourth section defines a generalization of equivalence structures, called nested equivalence structures. It goes on to produce an automatic nested equivalence structure for which the set of isomorphic structures is more complicated than any set of isomorphic equivalence structures. The fifth provides brief descriptions of other projects the author assisted during his time at Notre Dame, as well as suggestions for future work on related problems.