On the complexity of 1–tape ATMs and off-line 1-tape ATMs running in constant reversals

AbstractYamamoto and Noguchi raised the question of whether every recursively enumerable set can be accepted by a 1-tape or off-line 1-tape alternating Turing machine (ATM) whose (work)tape head makes only a constant number of reversals. In this paper, we answer the open question in the negative. We show that (1) constant-reversal 1-tape ATMs accept only regular languages and (2) there exists a recursive function h(k, r, n) such that for every k-state off-line 1-tape ATM, M, running in r reversals, the language accepted by M is in ASPACE(h(k, r, n))