DocumentCode
3263829
Title
Memory bounds for recognition of context-free and context-sensitive languages
Author
Lewis, P.M., II ; Stearns, R.E. ; Hartmanis, J.
fYear
1965
fDate
6-8 Oct. 1965
Firstpage
191
Lastpage
202
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
Keywords
Binary sequences; Computational complexity; Turing machines;
fLanguage
English
Publisher
ieee
Conference_Titel
Switching Circuit Theory and Logical Design, 1965. SWCT 1965. Sixth Annual Symposium on
Conference_Location
Ann Arbor, MI, USA
Type
conf
DOI
10.1109/FOCS.1965.14
Filename
5397245
Link To Document