Konferenzpaper

Herausgeberliste: Esik, Z; Fulop, Z

Jahr der Veröffentlichung: 2003

Seiten: 361-372

Zeitschrift: Lecture notes in computer science

Bandnummer: 2710

ISSN: 0302-9743

ISBN: 3-540-40434-1

Konferenz: 7th International Conference on Developments in Language Theory

Verlag: Springer

Serientitel: 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-Zitierstil: 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-Zitierstil: Holzer, M., & Kutrib, M. (2003). Flip-pushdown automata: Nondeterminism is better than determinism. Lecture notes in computer science (Schriftenreihe). 2710, 361-372.