Undecidability of bisimilarity by defender's forcing
From MaRDI portal
Publication:3546360
DOI10.1145/1326554.1326559zbMath1326.68199OpenAlexW1998608869MaRDI QIDQ3546360
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
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