Iterated pushdown automata and complexity classes
Joost Engelfriet · 1983
An iterated pushdown is a pushdown of pushdowns of ... of pushdowns. An iterated exponential function is 2 to the 2 to the ... to the 2 to some polynomial. The main result is that nondeterministic 2-way and multi-head iterated pushdown automata characterize deterministic iterated exponential time complexity classes. This is proved by investigating both nondeterministic and alternating auxiliary iterated pushdown automata, for which similar characterization results are given. In particular it is shown that alternation corresponds to one more iteration of pushdowns. These results are applied to the 1-way iterated pushdown automata: (1) they form a proper hierarchy with respect to the number of iterations, (2) their emptiness problem is complete in deterministic iterated exponential time.