TY  - UNPD
A1  - Malcher, Andreas
T1  - On non-recursive trade-offs between finite-turn pushdown automata
T2  - Frankfurter Informatik-Berichte ; Nr. 04,2
N2  - 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 tradeoffs. Considering the number of turns of the stack height as a consumable resource of PDAs, we can show the existence of non-recursive trade-offs between PDAs performing k+ 1 turns and k turns for k >= 1. Furthermore, non-recursive trade-offs 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.
T3  - Frankfurter Informatik-Berichte - 04, 2 
Y1  - 2004
UR  - http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/7188
UR  - https://nbn-resolving.org/urn:nbn:de:hebis:30-71719
SN  - 1616-9107
PB  - Johann Wolfgang Goethe-Univ., Fachbereich Biologie und Informatik, Inst. für Informatik
CY  - Frankfurt am Main
ER  -