Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2012.54
URN: urn:nbn:de:0030-drops-33940
URL: https://drops.dagstuhl.de/opus/volltexte/2012/3394/
Parys, Pawel
A Pumping Lemma for Pushdown Graphs of Any Level
| pdf-format: |
|
Abstract
We present a pumping lemma for the class of epsilon-contractions of pushdown graphs of level n, for each n. A pumping lemma was proposed by Blumensath, but there is an irrecoverable error in his proof; we present a new proof. Our pumping lemma also improves the bounds given in the invalid paper of Blumensath.
BibTeX - Entry
@InProceedings{parys:LIPIcs:2012:3394,
author = {Pawel Parys},
title = {{A Pumping Lemma for Pushdown Graphs of Any Level}},
booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
pages = {54--65},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-35-4},
ISSN = {1868-8969},
year = {2012},
volume = {14},
editor = {Christoph D{\"u}rr and Thomas Wilke},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2012/3394},
URN = {urn:nbn:de:0030-drops-33940},
doi = {10.4230/LIPIcs.STACS.2012.54},
annote = {Keywords: pushdown graph, epsilon-contraction, pumping lemma}
}
| Keywords: | pushdown graph, epsilon-contraction, pumping lemma | |
| Seminar: | 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012) | |
| Issue date: | 2012 | |
| Date of publication: | 24.02.2012 |
