A Pumping Lemma for Pushdown Graphs of Any Level

Author Pawel Parys



PDF
Thumbnail PDF

File

LIPIcs.STACS.2012.54.pdf
  • Filesize: 0.56 MB
  • 12 pages

Document Identifiers

Author Details

Pawel Parys

Cite AsGet 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.
Keywords
  • pushdown graph
  • epsilon-contraction
  • pumping lemma

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail