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.