Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. On Time Versus Space

On Time Versus Space

File(s)
75-264.pdf (1.03 MB)
75-264.ps (306.52 KB)
Permanent Link(s)
https://hdl.handle.net/1813/6755
Collections
Computer Science Technical Reports
Author
Hopcroft, John E.
Paul, Wolfgang J.
Valiant, Leslie
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.

Date Issued
1975-12
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR75-264
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance