  We show that deterministic collapsible pushdown automata of second order can
recognize a language that is not recognizable by any deterministic higher-order
pushdown automaton (without collapse) of any order. This implies that there
exists a tree generated by a second order collapsible pushdown system
(equivalently, by a recursion scheme of second order) that is not generated by
any deterministic higher-order pushdown system (without collapse) of any order
(equivalently, by any safe recursion scheme of any order). As a side effect, we
present a pumping lemma for deterministic higher-order pushdown automata, which
potentially can be useful for other applications.
