Alternation for sublogarithmic space-bounded alternating pushdown automata

This paper investigates infinite hierarchies on alternation-depth and alter nation-size of alternating pushdown automata (apda's) with sublogarithmic s pace. We first show that there is an infinite hierarchy on alternation-dept h for apda's with sublogarithmic space. We next investigate a relationship between alternation-depth and alternation-size, and show that for sublogari thmic space-bounded apda's, alternation-depth k is better than alternation- size k for each k greater than or equal to3. We finally show that there is an infinite hierarchy on alternation-size for apda's with sublogarithmic sp ace. (C) 2001 Elsevier Science B.V. All rights reserved.