A polynomial-time algorithm for deciding bisimulation equivalence of normed Basic Parallel Processes

DOI10.1017/S0960129500000992zbMath0857.68042WikidataQ59556998 ScholiaQ59556998MaRDI QIDQ4715674

Faron Moller, Mark R. Jerrum, Joram Hirschfeld

Publication date: 18 November 1996

Published in: Mathematical Structures in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s0960129500000992

zbMATH Keywords

polynomial-time algorithm; bisimulation; basic parallel processes

Mathematics Subject Classification ID

68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)

Related Items

Complexity of Weak Bisimilarity and Regularity for BPA and BPP, Petri nets, commutative context-free grammars, and basic parallel processes, High undecidability of weak bisimilarity for Petri nets, Normed Processes, Unique Decomposition, and Complexity of Bisimulation Equivalences, Pushdown automata, multiset automata, and Petri nets, Weak bisimilarity between finite-state systems and BPA or normed BPP is decidable in polynomial time, Partially-commutative context-free processes: expressibility and tractability, Deciding bisimulation and trace equivalences for systems with many identical processes, On the computational complexity of bisimulation, redux, Non-interleaving bisimulation equivalences on basic parallel processes, A polynomial algorithm for deciding bisimilarity of normed context-free processes, Undecidable problems in unreliable computations., Effective decomposability of sequential behaviours, An efficient algorithm for computing bisimulation equivalence, Complexity of deciding bisimilarity between normed BPA and normed BPP, Bisimilarity on basic parallel processes, Decidability of branching bisimulation on normed commutative context-free processes, Bisimulation and coinduction enhancements: a historical perspective, A general approach to comparing infinite-state systems with their finite-state specifications, Decidability of Branching Bisimulation on Normed Commutative Context-Free Processes, Partially-Commutative Context-Free Processes, Causality, Behavioural Equivalences, and the Security of Cyberphysical Systems, Selected Ideas Used for Decidability and Undecidability of Bisimilarity, Normed BPA vs. Normed BPP Revisited

Cites Work

• Unnamed Item
• Algebra of communicating processes with abstraction
• A short proof of the decidability of bisimulation for normed BPA- processes
• Unique decomposition of processes
• Deciding bisimilarity of normed context-free processes is in \(\Sigma_ 2^ p\)
• Decidability of bisimulation equivalence for process generating context-free languages