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 p...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Book |
| Language: | English |
| Published: |
College Station, Tex. :
Texas A & M University, Computer Science Dept.,
[1993]
|
| Series: | Technical report (Texas A & M University. Computer Science Department) ;
93-046. |
| Subjects: |
| Summary: | 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." |
|---|---|
| Item Description: | "September 29, 1993." |
| Physical Description: | 27 leaves : illustrations ; 28 cm. |
| Bibliography: | Includes bibliographical references. |