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

DOI10.1007/3-540-56939-1_73MaRDI QIDQ4630261zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• A note on some simultaneous relations among time, space, and reversal for single work tape nondeterministic turing machines
• A tradeoff theorem for space and reversal
• The difference between one tape and two tapes: With respect to reversal complexity
• Reversal complexity revisited
• Time/Space Trade-Offs for Reversible Computation

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• A note on some simultaneous relations among time, space, and reversal for single work tape nondeterministic turing machines
• Comparison of the power between reversal-bounded ATMs and reversal- bounded NTMs
• Reversal-bounded multipushdown machines
• Separating Nondeterministic Time Complexity Classes
• The reduction of tape reversals for off-line one-tape Turing machines
• Towards a complexity theory of synchronous parallel computation
• Visits, crosses, and reversals for nondeterministic off-line machines

Cited in

(8)

• Reversal Complexity
• A note on some simultaneous relations among time, space, and reversal for single work tape nondeterministic turing machines
• On the power of alternation on reversal-bounded alternating Turing machines with a restriction
• scientific article; zbMATH DE number 4070311 (Why is no real title available?)
• Reversal complexity revisited
• The difference between one tape and two tapes: With respect to reversal complexity
• An improved simulation of space and reversal bounded deterministic Turing machines by width and depth bounded uniform circuits
• A tradeoff theorem for space and reversal

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4630261)