Abstract/Details

Computational complexity of automatic structures


2011 2011

Other formats: Order a copy

Abstract (summary)

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 relations on these structures which appear at arbitrarily high finite levels of the arithmetical hierarchy. The third section creates an automatic equivalence structure, 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.

Indexing (details)


Subject
Applied Mathematics;
Philosophy;
Computer science
Classification
0364: Applied Mathematics
0422: Philosophy
0984: Computer science
Identifier / keyword
Philosophy, religion and theology; Applied sciences; Automatic structures; Computibility; Equivalence relation; Finite automation; Linear ordering; Logic
Title
Computational complexity of automatic structures
Author
Carson, Jacob
Number of pages
63
Publication year
2011
Degree date
2011
School code
0165
Source
DAI-B 73/01, Dissertation Abstracts International
Place of publication
Ann Arbor
Country of publication
United States
ISBN
9781124933368
Advisor
Knight, Julia
University/institution
University of Notre Dame
University location
United States -- Indiana
Degree
Ph.D.
Source type
Dissertations & Theses
Language
English
Document type
Dissertation/Thesis
Dissertation/thesis number
3480078
ProQuest document ID
898608394
Copyright
Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works.
Document URL
http://search.proquest.com/docview/898608394
Access the complete full text

You can get the full text of this document if it is part of your institution's ProQuest subscription.

Try one of the following:

  • Connect to ProQuest through your library network and search for the document from there.
  • Request the document from your library.
  • Go to the ProQuest login page and enter a ProQuest or My Research username / password.