Note on Undecidability of Bisimilarity for Second-Order Pushdown Processes

2013/03/04 by Petr Jančar, Jančar, Petr, Jǐŕı Srba +1
Engineering · #Process Optimization and Integration #Field-Flow Fractionation Techniques #Advanced Control Systems Optimization

paper · pdf · doi:10.48550/arxiv.1303.0780

Abstract

Broadbent and Göller (FSTTCS 2012) proved the undecidability of bisimulation equivalence for processes generated by epsilon-free second-order pushdown automata. We add a few remarks concerning the used proof technique, called Defender's forcing, and the related undecidability proof for first-order pushdown automata with epsilon-transitions (Jančar and Srba, JACM 2008).

Related

• Deciding semantic finiteness of pushdown processes and first-order grammars w.r.t. bisimulation equivalence
• Bisimilarity of Pushdown Systems is Nonelementary
• Bisimulation equivalence of first-order grammars is Ackermann-hard
• Bisimilarity of Probabilistic Pushdown Automata
• On Bisimulation in Absence of Restriction