Flip-pushdown automata: nondeterministic $\epsilon$-moves can be removed.
Pavol Ďuriš, Marek Košta · ITAT · 2011
Flip-pushdown automaton is pushdown automaton which has ability to flip its pushdown throughout the computation. This model was introduced in [3] by Sarkar. Here we solve in the affirmative the following open problem posed by Holzer and Kutrib in [1]: What is the power of e-moves for nondeterministic flip-pushdown automata – can they be removed without affecting the computational capacity? (e denotes the empty word.) Moreover, we prove here that the family of languages recognized by the deterministic variant of the flip-pushdown automata (with k-pushdown reversals) is closed under intersection with regular sets, complement and inverse homomorphism, but it is not closed under union, intersection, (non-erasing) homomorphism, reverse, concatenation and (positive) iteration. Finally, we formulate some new questions and pose new