Undecidability of bisimilarity by defender's forcing

DOI10.1145/1326554.1326559zbMATH Open1326.68199OpenAlexW1998608869MaRDI QIDQ3546360FDOQ3546360

Authors Petr Jančar, Jiří Srba 

Publication date 21 December 2008

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1326554.1326559

zbMATH Keywords

process algebrapushdown automataundecidabilitybisimilarity

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42) Decidability of theories and sets of sentences (03B25) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• Foundations of Software Science and Computation Structures
• Completeness results for undecidable bisimilarity problems
• scientific article; zbMATH DE number 1927587
• Selected Ideas Used for Decidability and Undecidability of Bisimilarity
• On Bisimilarity of Higher-Order Pushdown Automata: Undecidability at Order Two

Cited In (11)

• Equivalence of pushdown automata via first-order grammars
• Deciding semantic finiteness of pushdown processes and first-order grammars w.r.t. bisimulation equivalence
• On the complexity of checking semantic equivalences between pushdown processes and finite-state processes
• Countdown games, and simulation on (succinct) one-counter nets
• Selected Ideas Used for Decidability and Undecidability of Bisimilarity
• Two lower bounds for BPA
• Foundations of Software Science and Computation Structures
• Simulation relations and applications in formal methods
• Hardness of equivalence checking for composed finite-state systems
• Definable inapproximability: new challenges for duplicator
• Theory of interaction

This page was built for publication: Undecidability of bisimilarity by defender's forcing

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