Comparison of the power between reversal-bounded ATMs and reversal- bounded NTMs (Q1094877)

Alternating Turing machines (ATMs) are a generalization of non- deterministic Turing machines (NTMs). It is said that an ATM runs in reversal \(R(n)\) (resp. leaf \(B(n))\) if for every accepted input of length n there is a computation tree such that for each path from the root to a leaf the number of times a head changes the direction is at most \(R(n)\) (resp. the number of leaves is at most \(B(n)\)). In the paper, the power of reversal-bounded ATMs is considered and the results are as follows: 1. Every recursively enumerable set can be accepted by a 1-type 1-counter ATM with runs in constant reversals but not by a 1-type 1-counter NTM which runs in constant reversals. 2. For \(B(n)\) and \(R(n)\) satisfying \(B(n)\leq 2^{O(R(n))}\) and \(B(n)R(n)\geq n\), a class of languages accepted by 1-type ATMs which run in \(O(R(n))\) reversal and \(O(B(n))\) leaf is equivalent to a class of languages accepted by NTMs which run in \(O(B(n)R(n))\) space.