Abstract of Paper

Alternating and Empty Alternating Auxiliary Stack Automata
by Markus Holzer and Pierre McKenzie


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