  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.

Formal Languages and Automata Theory