The difference between one tape and two tapes: With respect to reversal complexity
From MaRDI portal
Publication:920983
DOI10.1016/0304-3975(90)90178-KzbMath0709.03033MaRDI QIDQ920983
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
time complexity; space complexity; number of alternations; reversal complexity; simulation of k-tape Turing machines
03D15: Complexity of computation (including implicit computational complexity)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
03D10: Turing machines and related notions
Related Items
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