A polynomial-time algorithm for deciding bisimulation equivalence of normed Basic Parallel Processes
From MaRDI portal
Publication:4715674
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)
68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
Related Items
Complexity of Weak Bisimilarity and Regularity for BPA and BPP, 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, Decidability of branching bisimulation on normed commutative context-free processes, 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
