Reversal Complexity
Jianer Chen, Chee-Keng Yap · SIAM Journal on Computing · 1991
The importance of reversal complexity as a basic computational resource has only been recognized in recent years. It is intimately connected to parallel time complexity and circuit depth. In this paper, some basic techniques necessary for establishing analogues of well-known theorems on space and time complexity are developed. The main results are, for reversal-constructible functions $s(n) \geqq \log n$, \[ \textit{DSPACE} (s(n)) \subseteq \textit{DREVERSAL}(s(n)), \] and a tape reduction theorem. As applications of the tape reduction theorem, a hierarchy theorem is proved and the existence of complete languages for reversal complexity is shown.