论文标题
关于高阶俯卧系统的表达能力
On the Expressive Power of Higher-Order Pushdown Systems
论文作者
论文摘要
我们表明，确定性的折叠式下阶的二阶自动机可以识别一种无法通过任何确定性的高阶倒计时自动机（无折叠）识别的语言。这意味着存在由二阶折叠下降系统生成的树（等效地，是通过第二阶的递归方案），该树未由任何确定性的高阶倒数系统（不倒塌）生成任何订单（等于任何订单的任何安全递归方案）。作为副作用，我们提出了用于确定性高阶俯卧撑自动机的抽水引理，这可能对其他应用程序有用。
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.
