On time hierarchies

DOI10.1016/0022-0000(79)90028-XzbMath0428.68055OpenAlexW2041195445MaRDI QIDQ1137384

Wolfgang J. Paul

Publication date: 1979

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(79)90028-x

zbMATH Keywords

k-tape Turing machinestime hierarchy theorem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)

Related Items

On the structure of one-tape nondeterministic Turing machine time hierarchy ⋮ Tradeoffs for language recognition on alternating machines ⋮ Translational lemmas for DLOGTIME-uniform circuits, alternating TMs, and PRAMs ⋮ A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes ⋮ Data structures for distributed counting ⋮ Deterministic Turing machines in the range between real-time and linear-time.

Cites Work

• Unnamed Item
• Unnamed Item
• Komplexität von Entscheidungsproblemen. Ein Seminar
• Time bounded random access machines
• On Time Versus Space
• Space bounds for a game on graphs
• Two-Tape Simulation of Multitape Turing Machines