Flip-Pushdown Automata with k Pushdown Reversals and E0L Systems are Incomparable

摘要

We prove that any propagating E0L system cannot generate the language containing all words of the form w#w. This result, together with some known ones, enable us to conclude that the flip-pushdown automata with k pushdown reversals (i.e. the pushdown automata with the ability to flip its pushdown) and E0L systems are incomparable. This result solves an open problem stated in [3].