Advertisement
Published in:
2012 | OriginalPaper | Chapter
Strictness of the Collapsible Pushdown Hierarchy
Authors : Alexander Kartzow, Paweł Parys
Published in: Mathematical Foundations of Computer Science 2012
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We present a pumping lemma for each level of the collapsible pushdown graph hierarchy in analogy to the second author’s pumping lemma for higher-order pushdown graphs (without collapse). Using this lemma, we give the first known examples that separate the levels of the collapsible pushdown graph hierarchy and of the collapsible pushdown tree hierarchy, i.e., the hierarchy of trees generated by higher-order recursion schemes. This confirms the open conjecture that higher orders allow one to generate more graphs and more trees.
Full proofs can be found in the arXiv version[10] of this paper.