Parys, Paweł - On the Expressive Power of Higher-Order Pushdown Systems

lmcs:6692 - Logical Methods in Computer Science, August 20, 2020, Volume 16, Issue 3
On the Expressive Power of Higher-Order Pushdown Systems

Authors: Parys, Paweł

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.


Volume: Volume 16, Issue 3
Published on: August 20, 2020
Submitted on: August 5, 2020
Keywords: Computer Science - Formal Languages and Automata Theory,F.1.1


Share

Consultation statistics

This page has been seen 65 times.
This article's PDF has been downloaded 41 times.