| Issue |
RAIRO-Theor. Inf. Appl.
Volume 50, Number 4, October-December 2016
7th Non-Classical Models of Automata and Applications (NCMA-2015)
|
|
|---|---|---|
| Page(s) | 295 - 311 | |
| DOI | https://doi.org/10.1051/ita/2016003 | |
| Published online | 02 June 2016 | |
A pumping lemma for flip-pushdown languages∗
Department of Computer Science, Faculty of Mathematics, Physics
and Informatics, Comenius University in Bratislava, Mlynská dolina, 842 48
Bratislava,
Slovakia
kostolanyi@fmph.uniba.sk
Received: 16 December 2015
Accepted: 24 March 2016
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.
Mathematics Subject Classification: 68Q45
Key words: Pumping lemma / flip-pushdown automaton / flip-pushdown language / reversal-generating context-free grammar
© EDP Sciences 2016
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.