Selected Ideas Used for Decidability and Undecidability of Bisimilarity
From MaRDI portal
Publication:3532999
DOI10.1007/978-3-540-85780-8_4zbMath1161.68621OpenAlexW1753356046MaRDI QIDQ3532999
Publication date: 30 October 2008
Published in: Developments in Language Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-85780-8_4
Formal languages and automata (68Q45) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Grammars and rewriting systems (68Q42)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the regular structure of prefix rewriting
- CCS expressions, finite state processes, and three problems of equivalence
- Decidability of bisimulation equivalence for normed pushdown processes
- Comparing expressibility of normed BPA and normed BPP processes
- A polynomial algorithm for deciding bisimilarity of normed context-free processes
- Strong bisimilarity of simple process algebras: Complexity lower bounds
- \(L(A)=L(B)\)? decidability results from complete formal systems
- \(L(A)=L(B)\)? A simplified decidability proof.
- Bisimulation equivalence is decidable for all context-free processes
- Decidability of bisimulation equivalence for process generating context-free languages
- Normed BPA vs. Normed BPP Revisited
- Undecidability of bisimilarity by defender's forcing
- An elementary bisimulation decision procedure for arbitrary context-free processes
- Three Partition Refinement Algorithms
- A polynomial-time algorithm for deciding bisimulation equivalence of normed Basic Parallel Processes
- The Bisimulation Problem for Equational Graphs of Finite Out-Degree
- Equivalence-checking on infinite-state systems: Techniques and results
- Faster Algorithm for Bisimulation Equivalence of Normed Context-Free Processes
- CONCUR 2003 - Concurrency Theory
- Decidability of DPDA equivalence