Undecidability of bisimilarity by defender's forcing

DOI10.1145/1326554.1326559zbMath1326.68199OpenAlexW1998608869MaRDI QIDQ3546360

Jiří Srba, Petr Jančar

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

undecidabilityprocess algebrapushdown automatabisimilarity

Mathematics Subject Classification ID

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

Related Items

Countdown games, and simulation on (succinct) one-counter nets ⋮ Theory of interaction ⋮ Simulation relations and applications in formal methods ⋮ Equivalence of pushdown automata via first-order grammars ⋮ Selected Ideas Used for Decidability and Undecidability of Bisimilarity ⋮ On the complexity of checking semantic equivalences between pushdown processes and finite-state processes ⋮ Unnamed Item ⋮ Deciding semantic finiteness of pushdown processes and first-order grammars w.r.t. bisimulation equivalence ⋮ Hardness of equivalence checking for composed finite-state systems