Reversal complexity

Jian Er Chen, Chee Keng Yap

Research output: Contribution to journalArticle

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 languageEnglish (US)
Pages (from-to)622-638
Number of pages17
JournalSIAM Journal on Computing
Volume20
Issue number4
DOIs
StatePublished - 1991

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Reversal complexity'. Together they form a unique fingerprint.

  • Cite this