文章基本信息

标题：Collapse Operation Increases Expressive Power of Deterministic Higher Order Pushdown Automata
本地全文：下载
作者：Pawel Parys
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2011
卷号：9
页码：603-614
DOI：10.4230/LIPIcs.STACS.2011.603
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：pushdown automata