The tight deterministic time hierarchy

Martin Fürer

doi:10.1145/800070.802172

The tight deterministic time hierarchy

Martin Fürer

Eberly College of Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

24 Scopus citations

Abstract

Let k be a. constant ≥ 2, and let us consider only deterministic k-tape Turing machines. We assume t₂(n) > n and t₂ is computable in time t₂. Then there is a language which is accepted in time t₂, but not accepted in any time t₁ with t₁(n) = o(t₂(n)). Furthermore, we obtain a strong hierarchy (isomorphic to the rationals Q) for languages accepted in fixed space and variable time.

Original language	English (US)
Title of host publication	Proceedings of the 14th Annual ACM Symposium on Theory of Computing, STOC 1982
Publisher	Association for Computing Machinery
Pages	8-16
Number of pages	9
ISBN (Print)	0897910702
DOIs	https://doi.org/10.1145/800070.802172
State	Published - May 5 1982
Event	14th Annual ACM Symposium on Theory of Computing, STOC 1982 - San Francisco, United States Duration: May 5 1982 → May 7 1982

Publication series

Name	Proceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)	0737-8017

Other

Other	14th Annual ACM Symposium on Theory of Computing, STOC 1982
Country/Territory	United States
City	San Francisco
Period	5/5/82 → 5/7/82

All Science Journal Classification (ASJC) codes

Software

Access to Document

10.1145/800070.802172

Cite this

@inproceedings{90ca9c667a3541b1979473a4c8dd74f1,

title = "The tight deterministic time hierarchy",

abstract = "Let k be a. constant ≥ 2, and let us consider only deterministic k-tape Turing machines. We assume t2(n) > n and t2 is computable in time t2. Then there is a language which is accepted in time t2, but not accepted in any time t1 with t1(n) = o(t2(n)). Furthermore, we obtain a strong hierarchy (isomorphic to the rationals Q) for languages accepted in fixed space and variable time.",

author = "Martin F{\"u}rer",

note = "Publisher Copyright: {\textcopyright} 1982 ACM.; 14th Annual ACM Symposium on Theory of Computing, STOC 1982 ; Conference date: 05-05-1982 Through 07-05-1982",

year = "1982",

month = may,

day = "5",

doi = "10.1145/800070.802172",

language = "English (US)",

isbn = "0897910702",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

pages = "8--16",

booktitle = "Proceedings of the 14th Annual ACM Symposium on Theory of Computing, STOC 1982",

}

Fürer, M 1982, The tight deterministic time hierarchy. in Proceedings of the 14th Annual ACM Symposium on Theory of Computing, STOC 1982. Proceedings of the Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, pp. 8-16, 14th Annual ACM Symposium on Theory of Computing, STOC 1982, San Francisco, United States, 5/5/82. https://doi.org/10.1145/800070.802172

TY - GEN

T1 - The tight deterministic time hierarchy

AU - Fürer, Martin

PY - 1982/5/5

Y1 - 1982/5/5

N2 - Let k be a. constant ≥ 2, and let us consider only deterministic k-tape Turing machines. We assume t2(n) > n and t2 is computable in time t2. Then there is a language which is accepted in time t2, but not accepted in any time t1 with t1(n) = o(t2(n)). Furthermore, we obtain a strong hierarchy (isomorphic to the rationals Q) for languages accepted in fixed space and variable time.

AB - Let k be a. constant ≥ 2, and let us consider only deterministic k-tape Turing machines. We assume t2(n) > n and t2 is computable in time t2. Then there is a language which is accepted in time t2, but not accepted in any time t1 with t1(n) = o(t2(n)). Furthermore, we obtain a strong hierarchy (isomorphic to the rationals Q) for languages accepted in fixed space and variable time.

UR - http://www.scopus.com/inward/record.url?scp=0002601160&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0002601160&partnerID=8YFLogxK

U2 - 10.1145/800070.802172

DO - 10.1145/800070.802172

M3 - Conference contribution

AN - SCOPUS:0002601160

SN - 0897910702

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 8

EP - 16

BT - Proceedings of the 14th Annual ACM Symposium on Theory of Computing, STOC 1982

PB - Association for Computing Machinery

T2 - 14th Annual ACM Symposium on Theory of Computing, STOC 1982

Y2 - 5 May 1982 through 7 May 1982

ER -

The tight deterministic time hierarchy

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this