Alternation and Omega-Type Turing Acceptors

An (omega)-language is a set of infinite ((omega)-type) strings of symbols. We study the classes of (omega)-languages accepted by Turing Acceptors when infinite computations are allowed. There are various possible "natural" acceptance conditions to consider, including those already common in the literature of (omega)-automata. There are also the deterministic (D), nondeterministic (N) and alternating (A) models to consider. Alternating machines were introduced by Chandra, Kozen and Stockmeyer (J. Assoc. Comp. Mach. 28 (1981), 114-133) as a natural extension of nondeterministic machines. (In symbols: D (LESSTHEQ) N (LESSTHEQ) A.)

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

2014

Author dc:creator

• Lindsay, Peter Alexander

• Mathematics

Identifier

(UMI)AAI8502221

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/71229