Konferenzpaper

Herausgeberliste: Baeten, JCM; Parrow, J; Lenstra, JK; Woeginger, GJ

Jahr der Veröffentlichung: 2003

Seiten: 490-501

Zeitschrift: Lecture notes in computer science

Bandnummer: 2719

ISSN: 0302-9743

ISBN: 3-540-40493-7

Konferenz: 30th International Colloquium on Automata, Languages and Programming (ICALP 2003)

Verlag: Springer

Serientitel: LECTURE NOTES IN COMPUTER SCIENCE

Abstract: 
Flip-pushdown automata are pushdown automata with the additional power to flip or reverse its pushdown, and were recently introduced by Sarkax [13]. We solve most of Sarkar's open problems. In particular, we show that k + 1 pushdown reversals are better than k for both deterministic and nondeterministic flip-pushdown automata, i.e., there are languages which can be recognized by a deterministic flip-pushdown automaton with k + 1 pushdown reversals but which cannot be recognized by a k-flip-pushdown (deterministic or nondeterministic). Furthermore, we investigate closure and non-closure properties as well as computational complexity problems such as fixed and general membership.

Harvard-Zitierstil: Holzer, M. and Kutrib, M. (2003) Flip-pushdown automata:: k+1 pushdown reversals are better than k, Lecture notes in computer science (Schriftenreihe), 2719, pp. 490-501

APA-Zitierstil: Holzer, M., & Kutrib, M. (2003). Flip-pushdown automata:: k+1 pushdown reversals are better than k. Lecture notes in computer science (Schriftenreihe). 2719, 490-501.