Geodesic
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

Voir la notice de l'article provenant de la source Numdam

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
Keywords: 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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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

Cité par Sources :