Files in this item

FilesDescriptionFormat

application/pdf

application/pdf3044154.pdf (3MB)Restricted to U of Illinois
(no description provided)PDF

Description

Title:Decision Problems in the Lattice of P01 Classes
Author(s):Lawton, Linda Barker
Doctoral Committee Chair(s):Jockusch, Carl G., Jr.
Department / Program:Mathematics
Discipline:Mathematics
Degree Granting Institution:University of Illinois at Urbana-Champaign
Degree:Ph.D.
Genre:Dissertation
Subject(s):Mathematics
Abstract:Given 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).
Issue Date:2002
Type:Text
Language:English
Description:85 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 2002.
URI:http://hdl.handle.net/2142/86790
Other Identifier(s):(MiAaPQ)AAI3044154
Date Available in IDEALS:2015-09-28
Date Deposited:2002


This item appears in the following Collection(s)

Item Statistics