On Bisimilarity of Higher-Order Pushdown Automata: Undecidability at Order Two

DOI10.4230/LIPICS.FSTTCS.2012.160MaRDI QIDQ2957489zbMATH OpenOpenAlexFDO

Authors Christopher H. Broadbent, Stefan Göller

Publication date 26 January 2017

Full work available at URL https://doi.org/10.4230/LIPIcs.FSTTCS.2012.160

zbMATH Keywords

bisimulation equivalencehigher-order pushdown automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• scientific article; zbMATH DE number 1759489
• Bisimilarity of pushdown automata is nonelementary
• On the determinacy problem for two-way pushdown automata
• On symmetric higher-dimensional automata and bisimilarity
• Bisimilarity of probabilistic pushdown automata
• ON THE EQUIVALENCE OF TWO-WAY PUSHDOWN AUTOMATA AND COUNTER MACHINES OVER BOUNDED LANGUAGES
• scientific article; zbMATH DE number 512842
• Unboundedness and downward closures of higher-order pushdown automata
• scientific article; zbMATH DE number 1927587

Cited in

(7)

• Equivalence of pushdown automata via first-order grammars
• Deciding semantic finiteness of pushdown processes and first-order grammars w.r.t. bisimulation equivalence
• Unboundedness and downward closures of higher-order pushdown automata
• Undecidability of bisimilarity by defender's forcing
• scientific article; zbMATH DE number 1759489 (Why is no real title available?)
• Bisimilarity of pushdown automata is nonelementary
• Second-Order Simple Grammars

This page was built for publication: On Bisimilarity of Higher-Order Pushdown Automata: Undecidability at Order Two

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2957489)