Thumbnail
Access Restriction
Subscribed

Author Hopcroft, John E. ♦ Ullman, Jeffrey D.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1968
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract It is shown that if a language $\textit{L}$ is recognized by a (nondeterministic) single-tape Turing machine of time complexity $\textit{T}(\textit{n}),$ then $\textit{L}$ is recognized by a (nondeterministic) offline Turing machine of tape complexity $\textit{T}1/2(\textit{n}).$ If $\textit{T}(\textit{n})$ ≥ $\textit{n}2;,$ $\textit{L}$ is recognized by a (nondeterministic) single-tape Turing machine of tape complexity $\textit{T}1/2(\textit{n}).$ If a language $\textit{L}$ is recognized by a (nondeterministic) offline Turing machine of time complexity $(\textit{T}(\textit{n}),$ then $\textit{L}$ is recognized by a (nondeterministic) offline Turing machine of tape complexity $(\textit{T}(\textit{n})$ log $\textit{n})1/2$ and by a (nondeterministic) single-tape Turing machine of that tape complexity if $\textit{T}$ $(\textit{n})$ ≥ $\textit{n}2/log$ $\textit{n}.$
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1968-07-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 15
Issue Number 3
Page Count 14
Starting Page 414
Ending Page 427


Open content in new tab

   Open content in new tab
Source: ACM Digital Library