Flip-pushdown automata are pushdown automata with the additional power to flip or reverse its pushdown, and were recently introduced by Sarkar. 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.
展开▼
