Alternating and empty alternating auxiliary stack automata

✍ Scribed by Markus Holzer; Pierre McKenzie

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 496 KB
• Volume: 299
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(02)00326-2

✦ Synopsis

We consider variants of alternating auxiliary stack automata and characterize their computational power when the number of alternations is bounded by a constant or unlimited. In this way we get new characterizations of NP, the polynomial hierarchy, PSpace, and bounded query classes like co-DP =NL NP[1] and 2P =P NP[O(log n)] , in a uniform framework.