On input read-modes of alternating Turing machines Academic Article uri icon

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.

published proceedings

  • Theoretical Computer Science

author list (cited authors)

  • Cai, L., & Chen, J.

citation count

  • 10

complete list of authors

  • Cai, Liming||Chen, Jianer

publication date

  • August 1995