On input read-modes of alternating Turing machines
Academic Article
Overview
Identity
Additional Document Info
Other
View All
Overview
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 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. 1995.