2026-07-23T19:43:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3858 2024-03-06T10:34:32Z ddc:004 open_access

On Bisimilarity of Higher-Order Pushdown Automata: Undecidability at Order Two Broadbent, Christopher Göller, Stefan Bisimulation equivalence Higher-order pushdown automata We show that bisimulation equivalence of order-two pushdown automata is undecidable. Moreover, we study the lower order problem of higher-order pushdown automata, which asks, given an order-k pushdown automaton and some k'<k, to determine if there exists a reachable configuration that is bisimilar to some order-k' pushdown automaton. We show that the lower order problem is undecidable for each k >= 2 even when the input k-PDA is deterministic and real-time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Christopher Broadbent and Stefan Göller 2012 Is Part Of LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2012.160 urn:nbn:de:0030-drops-38583 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.160 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode