LIPIcs.STACS.2012.54.pdf
- Filesize: 0.56 MB
- 12 pages
Document
A Pumping Lemma for Pushdown Graphs of Any Level
Author
-
Part of:
Volume:
29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
- Publication Date: 2012-02-24
Cite As Get BibTex
Pawel Parys. A Pumping Lemma for Pushdown Graphs of Any Level. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 54-65, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)
https://doi.org/10.4230/LIPIcs.STACS.2012.54
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.
Subject Classification
Keywords
- pushdown graph
- epsilon-contraction
- pumping lemma
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads