文章基本信息

标题：A Pumping Lemma for Pushdown Graphs of Any Level
本地全文：下载
作者：Pawel Parys
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2012
卷号：14
页码：54-65
DOI：10.4230/LIPIcs.STACS.2012.54
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：pushdown graph; epsilon-contraction; pumping lemma