License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2012.500
URN: urn:nbn:de:0030-drops-36937
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2012/3693/
Go to the corresponding LIPIcs Volume Portal

Parys, Pawel

Variants of Collapsible Pushdown Systems

pdf-format:
39.pdf (0.5 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{parys:LIPIcs:2012:3693,
  author =	{Pawel Parys},
  title =	{{Variants of Collapsible Pushdown Systems}},
  booktitle =	{Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL},
  pages =	{500--515},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-42-2},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{16},
  editor =	{Patrick C{\'e}gielski and Arnaud Durand},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2012/3693},
  URN =		{urn:nbn:de:0030-drops-36937},
  doi =		{10.4230/LIPIcs.CSL.2012.500},
  annote =	{Keywords: collapsible pushdown systems, determinization, infinite hierarchy, shrink- ing lemma, reachability}
}

Keywords: collapsible pushdown systems, determinization, infinite hierarchy, shrink- ing lemma, reachability
Collection: Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL
Issue Date: 2012
Date of publication: 03.09.2012

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI