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.
| Author: | Andreas Malcher |
|---|---|
| URN: | urn:nbn:de:hebis:30-71719 |
| ISSN: | 1616-9107 |
| 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 |
| Language: | English |
| 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. |
| HeBIS-PPN: | 219732019 |
| Institutes: | Informatik und Mathematik / Informatik |
| Dewey Decimal Classification: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik |
| Licence (German): |  Deutsches Urheberrecht |
