pi-calculus, internal mobility, and agent-passing calculi

Davide Sangiorgi 1
1 MEIJE - Concurrency, Synchronization and Real-time Programming
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : The $\pi$-calculus is a process algebra which originates from CCS and permits a natural modelling of mobility (i.e., dynamic reconfigurations of the process linkage) using communication of names. Previous research has shown that the $\pi$-calculus has much greater expressiveness than CCS, but also a much more complex mathematical theory. The primary goal of this work is to understand the reasons of this gap. Another goal is to compare the expressiveness of {\em \no} calculi, i.e., calculi like $\pi$-calculus where mobility is achieved via exchange of names, and that of {\em agent-passing calculi}, i.e., calculi where mobility is achieved via exchange of agents. We separate the mobility mechanisms of the \pic into two, respectively called {\em internal mobility} and {\em external mobility}. The study of the subcalculus which only uses internal mobility, called \pii, suggests that internal mobility is responsible for {much} of the expressiveness of the $\pi$-calculus, whereas external mobility is responsible for {much} of the semantic complications. A pleasant property of \pii  is the full symmetry between input and output constructs. Internal mobility is strongly related to agent-passing mobility. By imposing bounds on the order of the types of \pii and of the Higher-Order $\pi$-calculus \cite{San923} we define a hierarchy of name-passing calculi based on internal mobility and one of agent-passing calculi. We show that there is an exact correspondence, in terms of expressiveness, between the two hierarchies.
Type de document :
RR-2539, INRIA. 1995
Liste complète des métadonnées

Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 14:36:18
Dernière modification le : samedi 27 janvier 2018 - 01:31:30
Document(s) archivé(s) le : lundi 5 avril 2010 - 00:05:53



  • HAL Id : inria-00074139, version 1



Davide Sangiorgi. pi-calculus, internal mobility, and agent-passing calculi. RR-2539, INRIA. 1995. 〈inria-00074139〉



Consultations de la notice


Téléchargements de fichiers