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

DOI10.1017/S0960129500000992zbMath0857.68042OpenAlexW2137502532WikidataQ59556998 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 algorithmbisimulationbasic parallel processes

Mathematics Subject Classification ID

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

Related Items

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

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