A Pumping Lemma for Collapsible Pushdown Graphs of Level 2

Kartzow, Alexander

doi:10.4230/LIPIcs.CSL.2011.322

Document

A Pumping Lemma for Collapsible Pushdown Graphs of Level 2

Author Alexander Kartzow

Part of: Volume: Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL (CSL 2011)
Part of: Series: Leibniz International Proceedings in Informatics (LIPIcs)
Part of: Conference: Computer Science Logic (CSL)
License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
Publication Date: 2011-08-31

PDF

File

PDF

LIPIcs.CSL.2011.322.pdf

Filesize: 478 kB
15 pages

Document Identifiers

DOI: 10.4230/LIPIcs.CSL.2011.322
URN: urn:nbn:de:0030-drops-32406

Subject Classification

Keywords

collapsible pushdown graph
epsilon-contraction
pumping lemma

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

Abstract

We present a pumping lemma for the class of collapsible pushdown graphs of level 2. This pumping lemma even applies to epsilon-contractions of level 2 collapsible pushdown graphs. Our pumping lemma also improves the bounds of Hayashi's pumping lemma for indexed languages.

Cite As Get BibTex

Alexander Kartzow. A Pumping Lemma for Collapsible Pushdown Graphs of Level 2. In Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL. Leibniz International Proceedings in Informatics (LIPIcs), Volume 12, pp. 322-336, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011) https://doi.org/10.4230/LIPIcs.CSL.2011.322

Author Details

Alexander Kartzow

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail