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 -