Reversal-space trade-offs for simultaneous resource-bounded nondeterministic Turing machines

DOI10.1007/3-540-56939-1_73zbMath1420.68089OpenAlexW1926211062MaRDI QIDQ4630261

Hiroaki Yamamoto

Publication date: 29 March 2019

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-56939-1_73

zbMATH Keywords

Turing machinespace complexitybinary counterinput tapeinput symbol

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Related Items (1)

On the power of alternation on reversal-bounded alternating Turing machines with a restriction

Cites Work

• Unnamed Item
• Comparison of the power between reversal-bounded ATMs and reversal- bounded NTMs
• Towards a complexity theory of synchronous parallel computation
• Reversal-bounded multipushdown machines
• The reduction of tape reversals for off-line one-tape Turing machines
• A note on some simultaneous relations among time, space, and reversal for single work tape nondeterministic turing machines
• Separating Nondeterministic Time Complexity Classes
• Visits, crosses, and reversals for nondeterministic off-line machines

This page was built for publication: Reversal-space trade-offs for simultaneous resource-bounded nondeterministic Turing machines