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 pushdown flips, for an arbitrary constant . 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.
Accepté le :
DOI : 10.1051/ita/2016003
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, 7th Non-Classical Models of Automata and Applications (NCMA-2015) , Tome 50 (2016) no. 4, pp. 295-311. doi : 10.1051/ita/2016003. http://archive.numdam.org/articles/10.1051/ita/2016003/
A generalization of Ogden’s lemma. J. ACM 29 (1982) 404–407. | DOI | MR | Zbl
and ,On formal properties of simple phrase structure grammars. Z. Phonetik. Sprachwiss. Kommunikationsforsch. 14 (1961) 143–172. | MR | Zbl
, and ,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
Hairpin finite automata. J. Autom. Lang. Comb. 16 (2011) 71–74. | MR | Zbl
, and ,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.
Flip-pushdown automata with pushdown reversals and systems are incomparable. Inf. Process. Lett. 114 (2014) 417–420. | DOI | MR | Zbl
and ,Linear indexed languages. Theoret. Comput. Sci. 32 (1984) 47–60. | DOI | MR | Zbl
and ,An elementary proof of Double Greibach normal form. Inf. Process. Lett. 44 (1992) 291–293. | DOI | MR | Zbl
,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: Pushdown Reversals are Better Than . 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
Matrix equations and normal forms for context-free grammars. J. ACM 14 (1967) 501–507. | DOI | MR | Zbl
,Pushdown Automaton With the Ability to Flip its Stack. Electronic Colloquium on Computational Complexity (ECCC) 8 (2001).
,Cité par Sources :