2026-09-21T20:15:03Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/71229 2023-07-11 col_2142_5131 col_2142_16340 com_2142_5130 com_2142_16339 com_2142_8903

Lindsay, Peter Alexander 2014-12-16T06:18:12Z 2014-12-16T06:18:12Z 10000-01-01 1984 1984 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.) It is seen that under certain acceptance conditions alternating (omega)-TA's are no more powerful than their nondeterministic counterparts, while under other conditions they are far more powerful. In fact, each of the following cases occurs: D < N < A; D = N < A; D < N = A. We characterize the classes in terms of the arithmetical and analytical hierarchies of (omega)-languages (c.f. Rogers, Theory of Recursive Functions and Effective Computability, chapter 14) and give examples of (omega)-languages which are in some sense the most complicated in each class. Made available in DSpace on 2014-12-16T06:18:12Z (GMT). No. of bitstreams: 1 8502221.pdf: 2391355 bytes, checksum: 7380815aaef9ebc6edef4db6c9243fa0 (MD5) Previous issue date: 1984 Embargo set by: Seth Robbins for item 71395 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs U of I Only 103 p. Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1984. http://hdl.handle.net/2142/71229 (UMI)AAI8502221 Mathematics Alternation and Omega-Type Turing Acceptors text Mathematics Mathematics University of Illinois at Urbana-Champaign Dissertation Ph.D.