zbMATH — the first resource for mathematics

A hierarchy of equivalences for asynchronous calculi. (Extended abstract). (English) Zbl 0909.03030
Larsen, Kim G. (ed.) et al., Automata, languages and programming. 25th international colloquium, ICALP ’98. Aalborg, Denmark, July 13–17, 1998. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1443, 844-855 (1998).
Summary: We generate a natural hierarchy of equivalences for asynchronous name-passing process calculi from simple variations on Milner and Sangiorgi’s definition of weak barbed bisimulation. The \(\pi\)-calculus, used here, and the join-calculus are examples of such calculi.
We prove that barbed congruence coincides with Honda and Yoshida’s reduction equivalence, and with asynchronous labeled bisimulation when the calculus includes name matching, thus closing those two conjectures. We also show that barbed congruence is coarser when only one barb is tested. For the \(\pi\)-calculus it becomes an odd limit bisimulation, but for the join-calculus it coincides with both fair testing equivalence and with the weak barbed version of Sjödin and Parrow’s coupled simulation.
For the entire collection see [Zbl 0893.00039].

03B70 Logic in computer science
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)