Collapse Operation Increases Expressive Power of Deterministic Higher Order Pushdown Automata

Pawel Parys
We show that collapsible deterministic second level pushdown automata can recognize more languages than deterministic second level pushdown automata (without collapse). This implies that there exists a tree generated by a second level recursion scheme which is not generated by any second level safe recursion scheme.