Memory bounds for recognition of context-free and context-sensitive languages

Abstract

This paper investigates the computational complexity of binary sequences as measured by the rapidity of their generation by multitape Turing machines. A "translational" method which escapes some of the limitations of earlier approaches leads to a refinement of the established hierarchy. The previous complexity classes are shown to possess certain translational properties. An related hierarchy of complexity classes of monotonic functions is examined