Flip-pushdown automata: nondeterminism is better than determinism

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.