The difference between one tape and two tapes: With respect to reversal complexity

DOI10.1016/0304-3975(90)90178-KzbMath0709.03033OpenAlexW2020818044MaRDI QIDQ920983

Jian'er Chen

Publication date: 1990

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(90)90178-k

zbMATH Keywords

time complexityspace complexitynumber of alternationsreversal complexitysimulation of k-tape Turing machines

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Turing machines and related notions (03D10)

Related Items (1)

On the relationship between deterministic time and deterministic reversal

Cites Work

• Unnamed Item
• Reversal-bounded multipushdown machines
• Relationships between nondeterministic and deterministic tape complexities
• The reduction of tape reversals for off-line one-tape Turing machines
• Tape-reversal bounded Turing machine computations
• Nondeterministic Space is Closed under Complementation
• One-tape, off-line Turing machine computations

This page was built for publication: The difference between one tape and two tapes: With respect to reversal complexity