http://www.loc.gov/mods/v3 http://www.loc.gov/standards/mods/v3/mods-3-2.xsd
On input read-modes of alternating Turing machines
Abstract: "A number of input read-modes of Turing machines have appeared in the literature. To investigate the differences among these input read-modes, we study log-time alternating Turing machines of constant alternations. For each fixed integer k [> or =] 1 and for each read-mode, a precise circuit characterization is established for log-time alternating Turing machines of k alternations, which is a nontrivial refinement of Ruzzo's circuit characterization of alternating Turing machines. These circuit characterizations indicate clearly the differences among the input read-modes. Complete languages in strong sense for each level of the log- time hierarchy are presented, refining a result by Buss. An application of these results to computational optimization problems is described."
Supported in part by an Engineering Excellence Award from Texas A&M University
Supported in part by the National Science Foundation. CCR- 9110824
Technical report (Texas A & M University. Computer Science Department) ; 93-046