Abstract
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)≥log n, DSPACE(s(n)) ⊃ DRESERVAL(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.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 622-638 |
| Number of pages | 17 |
| Journal | SIAM Journal on Computing |
| Volume | 20 |
| Issue number | 4 |
| DOIs | |
| State | Published - 1991 |
ASJC Scopus subject areas
- Computer Science(all)
- Mathematics(all)