文章基本信息

标题：Variants of Collapsible Pushdown Systems
本地全文：下载
作者：Pawel Parys
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2012
卷号：16
页码：500-515
DOI：10.4230/LIPIcs.CSL.2012.500
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We analyze the relationship between three ways of generating trees using collapsible pushdown systems (CPS's): using deterministic CPS's, nondeterministic CPS's, and deterministic word-accepting CPS's. We prove that (for each level of the CPS and each input alphabet) the three classes of trees are equal. The nontrivial translations increase n-1 times exponentially the size of the level-n CPS. The same results stay true if we restrict ourselves to higher-order pushdown systems without collapse. As a second contribution we prove that the hierarchy of word languages recognized by nondeterministic CPS's is infinite. This is a consequence of a lemma which bounds the length of the shortest accepting run. It also implies that the hierarchy of epsilon-closures of configuration graphs is infinite (which was already known). As a side effect we obtain a new algorithm for the reachability problem for CPS's; it has the same complexity as previously known algorithms.
关键词：collapsible pushdown systems; determinization; infinite hierarchy; shrink- ing lemma; reachability