Memory bounds for recognition of context-free and context-sensitive languages
Philip Lewis, Richard Edwin Stearns, Juris Hartmanis · 1965
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