A pumping lemma for flip-pushdown languages

Kostolányi, Peter

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 50 (2016) no. 4, pp. 295-311.

Flip-pushdown automata are pushdown automata with an extra ability to reverse the contents of the pushdown store. A generalisation of the pumping lemma for context-free languages is presented, which applies to the families of languages accepted by flip-pushdown automata with $k$ pushdown flips, for an arbitrary constant $k$. The presented result gives rise to a new technique for disproving existence of flip-pushdown automata with a constant number of flips, which is significantly simpler compared to methods used for this purpose so far.

Classification : 68Q45
Mots clés : Pumping lemma, flip-pushdown automaton, flip-pushdown language, reversal-generating context-free grammar

C. Bader and A. Moura, A generalization of Ogden’s lemma. J. ACM 29 (1982) 404–407. | DOI | MR | Zbl

Y. Bar-Hillel, M. Perles and E. Shamir, On formal properties of simple phrase structure grammars. Z. Phonetik. Sprachwiss. Kommunikationsforsch. 14 (1961) 143–172. | MR | Zbl

H. Bordihn, M. Holzer and M. Kutrib, Input Reversals and Iterated Pushdown Automata: A New Characterization of Khabbaz Geometric Hierarchy of Languages. DLT 2004, edited by C.C. Calude, E. Calude and M.J. Dinneen. In vol. 3340 of Lect. Notes Comput. Sci. Springer (2004) 102–113. | MR | Zbl

H. Bordihn, M. Holzer and M. Kutrib, Hairpin finite automata. J. Autom. Lang. Comb. 16 (2011) 71–74. | MR | Zbl

N. Chomsky, On certain formal properties of grammars. Inf. Control 2 (1959) 167–167. | DOI | MR | Zbl

P. Ďuriš and M. Košta, Flip-Pushdown Automata: Nondeterministic $\epsilon$-Moves Can Be Removed, edited by M. Lopatková. In ITAT 2011 (2011) 15–22.

P. Ďuriš and M. Košta, Flip-pushdown automata with $k$ pushdown reversals and $E0L$ systems are incomparable. Inf. Process. Lett. 114 (2014) 417–420. | DOI | MR | Zbl

J. Duske and R. Parchmann, Linear indexed languages. Theoret. Comput. Sci. 32 (1984) 47–60. | DOI | MR | Zbl

J. Engelfriet, An elementary proof of Double Greibach normal form. Inf. Process. Lett. 44 (1992) 291–293. | DOI | MR | Zbl

S.A. Greibach, A new normal-form theorem for context-free phrase structure grammars. J. ACM 12 (1965) 42–52. | DOI | MR | Zbl

M. Holzer and M. Kutrib, Flip-Pushdown Automata: $k+1$ Pushdown Reversals are Better Than $k$. ICALP 2003, edited by J.C.M. Baeten et al. In vol. 2719 of Lect. Notes Comput. Sci. Springer (2003) 490–501. | MR | Zbl

M. Holzer and M. Kutrib, Flip-Pushdown automata: Nondeterminism is better than determinism. DLT 2003, edited by Z. Ésik and Z. Fülöp. In vol. 2710 of Lect. Notes Comput. Sci. Springer (2003) 361–372. | MR | Zbl

J.E. Hopcroft, R. Motwani and J.D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd edition. Pearson (2006). | Zbl

P. Kostolányi, Two grammatical equivalents of flip-pushdown automata. SOFSEM 2015, edited by G.F. Italiano et al. In vol. 8939 of Lect. Notes Comput. Sci. Springer (2015) 302–313. | MR

D.J. Rosenkrantz, Matrix equations and normal forms for context-free grammars. J. ACM 14 (1967) 501–507. | DOI | MR | Zbl

P. Sarkar, Pushdown Automaton With the Ability to Flip its Stack. Electronic Colloquium on Computational Complexity (ECCC) 8 (2001).