Collapse Operation Increases Expressive Power of Deterministic Higher Order Pushdown Automata
Paweł Parys · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2011
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.