On the Relative Expressive Power of Asynchronous Communication Primitives

Daniele Gorla

Short version in 9th International Conference on Foundations of Software Science and Computation Structures (FoSSaCS '06), Wien (Austria), March 29-31, 2006.
Full version available as Tech. Rep. 06/2005, Dip Informatica, Univ. di Roma "La Sapienza".

Abstract:

In this paper, we study eight asynchronous communication primitives, arising from the combination of three features: arity (monadic vs polyadic data), communication medium (message passing vs shared dataspaces) and pattern-matching. Each primitive has been already used in at least one language appeared in literature; however, to uniformly reason on such primitives, we plugged them in a common framework inspired by the asynchronous pi-calculus. By means of possibility/impossibility of `reasonable' encodings, we compare every pair of primitives to obtain a hierarchy of languages based on their relative expressive power.

@InProceedings{G:FoSSaCS06,
  author    =   {D. Gorla},
  title     =   {On the Relative Expressive Power of Asynchronous Communication Primitives},
  editor    =   {L. Aceto and A. Ingolfsdottir},
  booktitle =   {Proc. of 9th Intern. Conf. on Foundations of Software Science and Computation Structures (FoSSaCS'06)},
  series    =   {LNCS},
  volume    =  	{3921},
  pages     =  	{47--62},
  year      =  	{2006},
  publisher =   {Springer},
}

Home page / Publications