Affordable Access

Publisher Website

A relation between space, return and dual return complexities

Authors
Journal
Theoretical Computer Science
0304-3975
Publisher
Elsevier
Publication Date
Volume
9
Issue
1
Identifiers
DOI: 10.1016/0304-3975(79)90010-0

Abstract

Abstract We introduce the dual return complexity and prove that the return complexity classes and the dual return complexity classes of nondeterministic Turing machines coincide with the tape complexity classes of Turing machines with auxiliary pushdown tape for resource functions ƒ⩾ id, id being the identity function.

There are no comments yet on this publication. Be the first to share your thoughts.