On Recursive and Non-Recursive Trade-Offs Between Finite-Turn Pushdown Automata
Andreas Malcher · Journal of automata, languages and combinatorics · 2007
It is shown that between one-turn pushdown automata (1-turn PDAs) and deterministic finite automata (DFAs) there will be savings concerning the size of description not bounded by any recursive function, so-called non-recursive trade-offs. Considering the number of turns of the stack height as a consumable resource of PDAs, the existence of non-recursive trade-offs between PDAs performing $k+1$ turns and $k$ turns for $k\geq 1$ is proven. Furthermore, non-recursive trade-offs are shown between arbitrary PDAs and PDAs which perform only a finite number of turns. In the second part, $k$-turn deterministic PDAs ($k$-turn DPDAs) are considered. The trade-offs between nondeterministic and deterministic $k$-turn PDAs are still non-recursive whereas it is an open question whether the trade-offs between DPDAs performing $k+1$ turns and $k$ turns for $k\geq 1$ is recursive. If the trade-offs are recursive, then a doubly exponential function serves as a lower bound.