On non-recursive trade-offs between finite-turn pushdown automata

  • 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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Author:Andreas Malcher
Parent Title (German):Frankfurter Informatik-Berichte ; Nr. 04,2
Series (Serial Number):Frankfurter Informatik-Berichte (04, 2)
Publisher:Johann Wolfgang Goethe-Univ., Fachbereich Biologie und Informatik, Inst. für Informatik
Place of publication:Frankfurt am Main
Document Type:Working Paper
Year of Completion:2004
Year of first Publication:2004
Publishing Institution:Universitätsbibliothek Johann Christian Senckenberg
Release Date:2009/10/16
Page Number:9, IV S.
Institutes:Informatik und Mathematik / Informatik
Dewey Decimal Classification:0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik
Licence (German):License LogoDeutsches Urheberrecht