Skip to main content


eCommons@Cornell

eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/6755
Title: On Time Versus Space
Authors: Hopcroft, John E.
Paul, Wolfgang J.
Valiant, Leslie
Keywords: computer science
technical report
Issue Date: Dec-1975
Publisher: Cornell University
Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR75-264
Abstract: It is shown that every deterministic multitape Turing machine of time complexity t(n)/log t(n). Consequently, for tape constructable t(n), the class of languages recognizable by multitape Turing machines of time complexity t(n) is strictly contained in the class of languages recognized by Turing machines of tape complexity t(n). In particular, the context sensitive languages can not be recognized in linear time by deterministic multitape Turing machines. Keywords and phrases: Turing machines, time complexity, tape complexity.
URI: http://hdl.handle.net/1813/6755
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
75-264.pdf1.05 MBAdobe PDFView/Open
75-264.ps306.52 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.

 

© 2014 Cornell University Library Contact Us