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|
|Number of pages||6|
|State||Published - 1987|
ASJC Scopus subject areas