On the Expressiveness of Pure Safe Ambients

Pascal Zimmer 1
1 MIMOSA - Migration and mobility : semantics and applications
CRISAM - Inria Sophia Antipolis - Méditerranée , Université de Provence - Aix-Marseille 1, MINES ParisTech - École nationale supérieure des mines de Paris
Abstract : We consider the Pure Safe Ambient Calculus, which is Levi and Sangiorgi's Safe Ambient Calculus (a variant of Cardelli and Gordon's Mobile Ambient Calculus) restricted to its mobility primitives, and we focus on its expressiv- e power. Since it has no form of communication or substitution, we show how these notions can be simulated by mobility and modifications in the hierarchical structure of ambients. As a main result, we use these techniques to design an encoding of the synchronous pi-calculus into pure ambients, and we study its correctness, thus showing that pure ambients are as expressive as the pi-calculus. In order to simplify the proof and give an intuitive understanding of the encoding, we design an intermediate language: the pi-calculus with Explicit Substitutions and Channels, which is an extension of the pi-calculus in which communication and substitution are broken into simpler steps, and we show that is has the same expressive power as the pi-calculus.
Document type :
Reports
Complete list of metadatas

Cited literature [1 references]  Display  Hide  Download

https://hal.inria.fr/inria-00072238
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 8:11:37 PM
Last modification on : Wednesday, December 18, 2019 - 5:20:30 PM
Long-term archiving on: Sunday, April 4, 2010 - 10:59:53 PM

Identifiers

  • HAL Id : inria-00072238, version 1

Citation

Pascal Zimmer. On the Expressiveness of Pure Safe Ambients. RR-4350, INRIA. 2002. ⟨inria-00072238⟩

Share

Metrics

Record views

210

Files downloads

390