On the complexity of 1-tape ATMs and off-line 1-tape ATMs running in constant reversals
From MaRDI portal
Publication:917283
DOI10.1016/0304-3975(90)90024-CzbMath0704.68036MaRDI QIDQ917283
Publication date: 1990
Published in: Theoretical Computer Science (Search for Journal in Brave)
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (1)
Cites Work
- Unnamed Item
- Alternating multicounter machines with constant number of reversals
- Comparison of the power between reversal-bounded ATMs and reversal- bounded NTMs
- Tradeoffs for language recognition on alternating machines
- The complexity of decision problems for finite-turn multicounter machines
- Reversal-bounded multipushdown machines
- The reduction of tape reversals for off-line one-tape Turing machines
- Tape-reversal bounded Turing machine computations
- Alternation
- Reversal-Bounded Multicounter Machines and Their Decision Problems
- Visits, crosses, and reversals for nondeterministic off-line machines
- Note on tape reversal complexity of languages
This page was built for publication: On the complexity of 1-tape ATMs and off-line 1-tape ATMs running in constant reversals
