Conference paper

Editor list: Baeten, JCM; Parrow, J; Lenstra, JK; Woeginger, GJ

Publication year: 2003

Pages: 490-501

Journal: Lecture notes in computer science

Volume number: 2719

ISSN: 0302-9743

ISBN: 3-540-40493-7

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

Publisher: Springer

Title of series: 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 Citation style: 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 Citation style: 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.