Undecidability of bisimilarity by defender's forcing

DOI10.1145/1326554.1326559MaRDI QIDQ3546360zbMATH OpenOpenAlexFDO

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

(13)

• 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
• Bisimilarity in fresh-register automata
• Countdown games, and simulation on (succinct) one-counter nets
• Selected Ideas Used for Decidability and Undecidability of Bisimilarity
• Bisimulation equivalence of pushdown automata is Ackermann-complete
• Two lower bounds for BPA
• Foundations of Software Science and Computation Structures
• Hardness of equivalence checking for composed finite-state systems
• Simulation relations and applications in formal methods
• 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)