On the Relative Expressive Power of Ambient-based Calculi

Daniele Gorla

Paper to appear in the 4th International Symposium on Trustworthy Global Computing (TGC'08), Barcelona (Spain), November 3rd-4th, 2008.
Full version available as Tech. Rep. 09/2006, Dip Informatica, Univ. di Roma "La Sapienza".

Abstract:

Nowadays, some of the most successful models for global computers are defined as ambient-based calculi; among them, the mainstream models are Mobile, Safe and Boxed Ambients. In this paper, we comparatively analyse most of their variants by comparing every variant against the language it comes from. In particular, we discuss and compare: objective moves in Mobile Ambients; passwords and a different semantics for the 'out' primitive in Safe Ambients; different communication and mobility primitives in Boxed Ambients. By establishing the possibility/impossibility of encoding one language in another one, we discover which variants enhance the original language and which ones actually yield different formalisms.

@InProceedings{G:TGC08,
  author    =   {D. Gorla},
  title     =   {On the Relative Expressive Power of Ambient-based Calculi},
  editor    =   {C. Kaklamanis and F. Nielson},
  booktitle =   {Proc. of 4th International Symposium on Trustworthy Global Computing (TGC'08)},
  series    =   {LNCS},
  number    =  	{5474},
  pages     =  	{141--156},
  year      =  	{2009},
  publisher =   {Springer},
}