Abstract of Paper |

*Alternating and Empty Alternating Auxiliary Stack Automata*

by Markus Holzer and Pierre McKenzie

**Abstract:**

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 $NL^{\langle NP[1]\rangle}$ and $\Theta_2P=P^{NP[O(\log n)]}$, in a uniform framework.