文章基本信息

标题：A Pumping Lemma for Collapsible Pushdown Graphs of Level 2
本地全文：下载
作者：Alexander Kartzow
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2011
卷号：12
页码：322-336
DOI：10.4230/LIPIcs.CSL.2011.322
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：collapsible pushdown graph; epsilon-contraction; pumping lemma