REVERSAL COMPLEXITY.

Jian er Chen, Chee Keng Yap

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

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 languageEnglish (US)
Title of host publicationUnknown Host Publication Title
PublisherIEEE
Pages14-19
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