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 and Theta(2)P=P-NP[O(log n)], in a uniform framework. (C) 2002 Elsevier Science B.V. All rights reserved. [References: 24]
展开▼
