Paper Details

On Linear Time and Congruence in Channel-Passing Calculi

Authors: Peschanski, Frederic

Abstract:

Process algebras such as CSP or the Pi-calculus are theories to reason about concurrent software. The Pi-calculus also introduces channel passing to address specific issues in mobility. Despite their similarity, the languages expose salient divergences at the formal level. CSP is built upon trace semantics while labelled transition systems and bisimulation are the privileged tools to discuss the Pi-calculus semantics. In this paper, we try to bring closer both approaches at the theoretical level by showing that proper trace semantics can be built upon the Pi-calculus. Moreover, by introducing locations, we obtain the same discriminative power for both the trace and bisimulation equivalences, in the particular case of early semantics. In a second part, we propose to develop the semantics of a slightly modified language directly in terms of traces. This language retains the full expressive power of the Pi-calculus and most notably supports channel passing. Interestingly, the resulting equivalence, obtained from late semantics, exhibits a nice congruence property over process expressions.

Proceedings:

Communicating Process Architectures 2004, Ian R. East, David Duce, Mark Green, Jeremy M. R. Martin, Peter H. Welch, 2004, pp 39 - 54 published by IOS Press, Amsterdam

Files: PDF

This record in other formats:

Web page: BibTEX, Refer
Plain text: BibTEX, Refer

If you have any comments on this database, including inaccuracies, requests to remove or add information, or suggestions for improvement, the WoTUG web team are happy to hear of them. We will do our best to resolve problems to everyone's satisfaction.

Copyright for the papers presented in this database normally resides with the authors; please contact them directly for more information. Addresses are normally presented in the full paper.