New time hierarchy results for deterministic TMS

DOI10.1007/3-540-55210-3_194zbMath1494.68083OpenAlexW2144068068MaRDI QIDQ5096792

Krzysztof Loryś

Publication date: 18 August 2022

Published in: STACS 92 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-55210-3_194

zbMATH Keywords

deterministic Turing machines

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Classical models of computation (Turing machines, etc.) (68Q04)

Cites Work

• Unnamed Item
• Data structures for distributed counting
• On alternation
• Two-Tape Simulation of Multitape Turing Machines
• Computational Complexity of One-Tape Turing Machine Computations
• One-tape, off-line Turing machine computations