On the power of alternation on reversal-bounded alternating Turing machines with a restriction
From MaRDI portal
Publication:1390864
DOI10.1016/S0304-3975(96)00143-0zbMath0901.68053MaRDI QIDQ1390864
Publication date: 22 July 1998
Published in: Theoretical Computer Science (Search for Journal in Brave)
Cites Work
- Unnamed Item
- Comparison of the power between reversal-bounded ATMs and reversal- bounded NTMs
- On reversal bounded alternating Turing machines
- \(\Sigma_ 2SPACE(n)\) is closed under complement
- Reversal-bounded multipushdown machines
- The polynomial-time hierarchy
- Complete sets and the polynomial-time hierarchy
- Reversal Complexity Classes for Alternating Turing Machines
- Nondeterministic Space is Closed under Complementation
- Alternation
- Visits, crosses, and reversals for nondeterministic off-line machines
- Reversal-space trade-offs for simultaneous resource-bounded nondeterministic Turing machines