A pumping lemma for flip-pushdown languages
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.

Reçu le :
Accepté le :
DOI : 10.1051/ita/2016003
Classification : 68Q45
Mots clés : Pumping lemma, flip-pushdown automaton, flip-pushdown language, reversal-generating context-free grammar
@article{ITA_2016__50_4_295_0,
     author = {Kostol\'anyi, Peter},
     title = {A pumping lemma for flip-pushdown languages},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {295--311},
     publisher = {EDP-Sciences},
     volume = {50},
     number = {4},
     year = {2016},
     doi = {10.1051/ita/2016003},
     mrnumber = {3614547},
     zbl = {1362.68147},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ita/2016003/}
}
TY  - JOUR
AU  - Kostolányi, Peter
TI  - A pumping lemma for flip-pushdown languages
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2016
SP  - 295
EP  - 311
VL  - 50
IS  - 4
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ita/2016003/
DO  - 10.1051/ita/2016003
LA  - en
ID  - ITA_2016__50_4_295_0
ER  - 
%0 Journal Article
%A Kostolányi, Peter
%T A pumping lemma for flip-pushdown languages
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2016
%P 295-311
%V 50
%N 4
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ita/2016003/
%R 10.1051/ita/2016003
%G en
%F ITA_2016__50_4_295_0
Kostolányi, Peter. A pumping lemma for flip-pushdown languages. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 50 (2016) no. 4, pp. 295-311. doi : 10.1051/ita/2016003. http://archive.numdam.org/articles/10.1051/ita/2016003/

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 ε-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).

Cité par Sources :