Comparison of the power between reversal-bounded ATMs and reversal- bounded NTMs

DOI10.1016/0890-5401(87)90055-1zbMath0631.68051OpenAlexW2087846761MaRDI QIDQ1094877

Shoichi Noguchi, Hiroaki Yamamoto

Publication date: 1987

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(87)90055-1

zbMATH Keywords

recursively enumerable setAlternating Turing machinesnon-deterministic Turing machinesreversal-bounded machine

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Turing machines and related notions (03D10)

Related Items (4)

On the power of 1-tape off-line ATMs running in a bounded number of reversals ⋮ On the power of alternation on reversal-bounded alternating Turing machines with a restriction ⋮ On the complexity of 1-tape ATMs and off-line 1-tape ATMs running in constant reversals ⋮ Reversal-space trade-offs for simultaneous resource-bounded nondeterministic Turing machines

Cites Work

• Unnamed Item
• Alternating multicounter machines with constant number of reversals
• Tree-size bounded alternation
• Reversal-bounded multipushdown machines
• Techniques for separating space complexity classes
• The reduction of tape reversals for off-line one-tape Turing machines
• Tape-reversal bounded Turing machine computations
• Alternation
• Visits, crosses, and reversals for nondeterministic off-line machines
• Relations Between Time and Tape Complexities
• Note on tape reversal complexity of languages

This page was built for publication: Comparison of the power between reversal-bounded ATMs and reversal- bounded NTMs