Abstract. Recent studies reveal that branching bisimilarity is decidable for both nBPP (normed Basic Parallel Processes) and nBPA (normed Basic Process Algebras). These results lead to the question if there are any other models in the hierarchy of PRS (Process Rewrite Systems) whose branching bisimilarity is decidable. It is shown in this paper that the branching bisimilarity for both nOCN (normed One Counter Nets) and nPA (normed Process Algebras) is undecidable. These results essentially imply that the question has a negative answer.
In REF , it is shown that branching bisimilarity is undecidable on two classes of infinite-state systems: normed OCN (one-counter nets) and normed PA (process algebra).
Branching Bisimilarity Checking for PRS
ArXiv
ArXiv
Computer Science Mathematics