Department of Information Engineering, Faculty of Engineering, Shinshu University, 500 Wakasato, Nagano-shi, 380, Japan
Abstract:
Whether or not there is a difference of the power among alternating Turing machines with a bounded number of alternations is one of the most important problems in the field of computer science. This paper presents the following result: Let R(n) be a space and reversal constructible function. Then, for any k 1, we obtain that the class of languages accepted by off-line 1-tape rσk machines running in reversal O(R(n)) is equal to the class of languages accepted by off-line 1-tape σ1 machines running in reversal O(R(n)). An off-line 1-tape σk machine M is called an off-line 1-tape rσk machine if M always limits the non-blank part of the work-tape to at most O(R(n) logn) when making an alternation between universal and existential states during the computation.