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