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

DOI10.1007/3-540-56939-1_73zbMATH Open1420.68089OpenAlexW1926211062MaRDI QIDQ4630261FDOQ4630261

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

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

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)

Cites Work

• Title not available (Why is that?)
• Reversal-bounded multipushdown machines
• Separating Nondeterministic Time Complexity Classes
• Towards a complexity theory of synchronous parallel computation
• Comparison of the power between reversal-bounded ATMs and reversal- bounded NTMs
• The reduction of tape reversals for off-line one-tape Turing machines
• Visits, crosses, and reversals for nondeterministic off-line machines
• A note on some simultaneous relations among time, space, and reversal for single work tape nondeterministic turing 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
• Title not available (Why is that?)
• 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)