Conference paper

Editor list: Esik, Z; Fulop, Z

Publication year: 2003

Pages: 361-372

Journal: Lecture notes in computer science

Volume number: 2710

ISSN: 0302-9743

ISBN: 3-540-40434-1

Conference: 7th International Conference on Developments in Language Theory

Publisher: Springer

Title of series: LECTURE NOTES IN COMPUTER SCIENCE

Abstract: 
Flip-pushdown automata are pushdown automata with the additional ability to flip or reverse its pushdown. We investigate deterministic and nondeterministic flip-pushdown automata accepting by final state or empty pushdown. In particular, for nondeterministic flip-pushdown automata both acceptance criterion are equally powerful, while for determinism, acceptance by empty pushdown is strictly weaker. This nicely fits into the well-known results on ordinary pushdown automata. Moreover, we consider hierarchies of flip-pushdown automata w.r.t. the number of pushdown reversals. There we show that nondeterminism is better than determinism. Moreover, since 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) as shown in [9] we are able to complete our investigations with incomparability results on different levels of the hierarchies under consideration.

Harvard Citation style: Holzer, M. and Kutrib, M. (2003) Flip-pushdown automata: Nondeterminism is better than determinism, Lecture notes in computer science (Schriftenreihe), 2710, pp. 361-372

APA Citation style: Holzer, M., & Kutrib, M. (2003). Flip-pushdown automata: Nondeterminism is better than determinism. Lecture notes in computer science (Schriftenreihe). 2710, 361-372.