LIPIcs.STACS.2011.603.pdf
- Filesize: 0.55 MB
- 12 pages
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.
Feedback for Dagstuhl Publishing