Parys, Pawel
Variants of Collapsible Pushdown Systems
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 wordaccepting 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 n1 times exponentially the size of the leveln CPS. The same results stay true if we restrict ourselves to higherorder 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 epsilonclosures 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 = {500515},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897422},
ISSN = {18688969},
year = {2012},
volume = {16},
editor = {Patrick C{\'e}gielski and Arnaud Durand},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2012/3693},
URN = {urn:nbn:de:0030drops36937},
doi = {http://dx.doi.org/10.4230/LIPIcs.CSL.2012.500},
annote = {Keywords: collapsible pushdown systems, determinization, infinite hierarchy, shrink ing lemma, reachability}
}
2012
Keywords: 

collapsible pushdown systems, determinization, infinite hierarchy, shrink ing lemma, reachability 
Seminar: 

Computer Science Logic (CSL'12)  26th International Workshop/21st Annual Conference of the EACSL

Related Scholarly Article: 


Issue date: 

2012 
Date of publication: 

2012 