Technical Reports

The report FIMU-RS-99-05

Approximating Weak Bisimulation on Basic Process Algebra

by Jitka Støíbrná, This work has been presented at MFCS`99. September 1999, 18 pages.

FIMU-RS-99-05. Available as Postscript, PDF.

Abstract:

The maximal strong and weak bisimulations on any class of processes can be obtained as the limits of decreasing chains of binary relations, approximants. In the case of strong bisimulation and Basic Process Algebras this chain has length at most omega which enables semidecidability of strong bisimilarity. We show that it is not so for weak bisimulation where the chain can grow much longer, and discuss the implications this has for the problem of (semi)decidability of weak bisimilarity.