2026-07-22T11:17:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3693 2024-03-06T10:34:23Z ddc:004 open_access

Variants of Collapsible Pushdown Systems Parys, Pawel collapsible pushdown systems determinization infinite hierarchy shrink- ing lemma reachability 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pawel Parys 2012 Is Part Of LIPIcs, Volume 16, Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL (2012) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2012.500 urn:nbn:de:0030-drops-36937 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2012.500 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode