Frankfurter InformatikBerichte
1 search hit
 04, 2

On nonrecursive tradeoffs between finiteturn pushdown automata
(2004)

Andreas Malcher
 It is shown that between oneturn pushdown automata (1turn PDAs) and deterministic finite automata (DFAs) there will be savings concerning the size of description not bounded by any recursive function, socalled nonrecursive tradeoffs. Considering the number of turns of the stack height as a consumable resource of PDAs, we can show the existence of nonrecursive tradeoffs between PDAs performing k+ 1 turns and k turns for k >= 1. Furthermore, nonrecursive tradeoffs are shown between arbitrary PDAs and PDAs which perform only a finite number of turns. Finally, several decidability questions are shown to be undecidable and not semidecidable.