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

lmcs:6692 - Logical Methods in Computer Science, August 20, 2020, Volume 16, Issue 3 - https://doi.org/10.23638/LMCS-16(3:11)2020
On the Expressive Power of Higher-Order Pushdown SystemsArticle

Authors: Paweł Parys ORCID

    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
    Accepted on: August 13, 2020
    Submitted on: August 5, 2020
    Keywords: Computer Science - Formal Languages and Automata Theory,F.1.1

    Consultation statistics

    This page has been seen 1033 times.
    This article's PDF has been downloaded 225 times.