Deciding bisimulation and trace equivalences for systems with many identical processes

DOI10.1016/S0304-3975(96)80714-6zbMath0874.68119OpenAlexW1981799619MaRDI QIDQ672063

Shi-Tsuen Jian, Hsu-Chun Yen, Ta-Pang Lao

Publication date: 27 February 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(96)80714-6

zbMATH Keywords

process semanticsbisimulation equivalencecalculus communicating systemsinterprocess communicationtrace equivalence

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Semantics in the theory of computing (68Q55)

Cites Work

• Undecidability of bisimilarity for Petri nets and some related problems
• Priority systems with many identical processes
• CCS expressions, finite state processes, and three problems of equivalence
• Reasoning about networks with many identical finite state processes
• On the analysis of cooperation and antagonism in networks of communicating processes
• Deciding bisimilarity is P-complete
• Deciding bisimilarity of normed context-free processes is in \(\Sigma_ 2^ p\)
• Undecidable equivalences for basic process algebra
• Bisimulation equivalence is decidable for all context-free processes
• Reasoning about systems with many processes
• On deciding some equivalences for concurrent processes
• A polynomial-time algorithm for deciding bisimulation equivalence of normed Basic Parallel Processes
• Unnamed Item
• Unnamed Item
• Unnamed Item