Back to results
University of Illinois at Urbana-Champaign
Decision Problems in the Lattice of P01 Classes
Abstract
dc:descriptionGiven an (undecidable) elementary theory of a computability-theoretic structure, it is natural to ask how much of the theory is decidable. An AE-sentence is a sentence in prenex normal form with all universal quantifiers preceding all existential quantifiers, and the AE-theory of a structure is the set of all AE-sentences true in the structure. In Chapter 3 we show that the AE-theory of ( LP01 , ∩, ∪, 0, 1) is decidable. In Chapter 4 we show that the AE-theories of ( LP01 , ∩, ∪, 0, 1) and ( LP01 * , ∩, ∪, 0, 1) are different and provide a decision procedure for the AE-theory of ( LP01 * , ∩, ∪, 0, 1).
Degree
thesis:*- Name thesis:degree_name
- Ph.D.
- Level thesis:degree_level
- Dissertation
- Discipline thesis:degree_discipline
- Mathematics
- Grantor
- University of Illinois at Urbana-Champaign
- Year dc:date
- 2015
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Lawton, Linda Barker
- Contributors dc:contributor
-
- Jockusch, Carl G., Jr.
Subjects
dc:subject × 1Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- (MiAaPQ)AAI3044154
- OAI identifier oai:identifier
- oai:www.ideals.illinois.edu:2142/86790