Abstract
Some basic techniques necessary for establishing analogs of well-known theorems on space and time complexity are developed. The main results are that for reversal-constructible functions s(n) greater than equivalent to log n, DSPACE(s(n)) 25 DREVERSAL(s(n)) and the first 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) |
|---|---|
| Title of host publication | Unknown Host Publication Title |
| Publisher | IEEE |
| Pages | 14-19 |
| Number of pages | 6 |
| ISBN (Print) | 0818607947 |
| State | Published - 1987 |
ASJC Scopus subject areas
- General Engineering