Jian er Chen, Chee Keng Yap

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 languageEnglish (US)
Title of host publicationUnknown Host Publication Title
Number of pages6
ISBN (Print)0818607947
StatePublished - 1987

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'REVERSAL COMPLEXITY.'. Together they form a unique fingerprint.

Cite this