Complexity of Nondeterministic Multitape Computations Based on Crossing Sequences
From MaRDI portal
Publication:5200101
DOI10.1007/978-3-642-22600-7_25zbMath1341.68114MaRDI QIDQ5200101
Publication date: 29 July 2011
Published in: Descriptional Complexity of Formal Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-22600-7_25
68Q45: Formal languages and automata
68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Time- and tape-bounded Turing acceptors and AFLs
- Tape bounds for time-bounded Turing machines
- Fast Simulations of Time-Bounded One-Tape Turing Machines by Space-Bounded Ones
- Some Time-Space Tradeoff Results Concerning Single-Tape and Offline TM’<scp>s</scp>
- On Time Versus Space
- Computational Complexity of One-Tape Turing Machine Computations
- One-tape, off-line Turing machine computations