LIPIcs.CSL.2011.322.pdf
- Filesize: 478 kB
- 15 pages
Document
A Pumping Lemma for Collapsible Pushdown Graphs of Level 2
Author
-
Part of:
Volume:
Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL (CSL 2011)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Computer Science Logic (CSL) - License:
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
- Publication Date: 2011-08-31
Cite AsGet 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
https://doi.org/10.4230/LIPIcs.CSL.2011.322
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.
Keywords
- collapsible pushdown graph
- epsilon-contraction
- pumping lemma
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads