On the power of alternation on reversal-bounded alternating Turing machines with a restriction

DOI10.1016/S0304-3975(96)00143-0zbMath0901.68053MaRDI QIDQ1390864

Hiroaki Yamamoto

Publication date: 22 July 1998

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

zbMATH Keywords

alternating Turing machines

Mathematics Subject Classification ID

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

This page was built for publication: On the power of alternation on reversal-bounded alternating Turing machines with a restriction