文章基本信息

标题：What is a ‘Good’ Encoding of Guarded Choice?
本地全文：下载
作者：Uwe Nestmann
期刊名称：BRICS Report Series
印刷版ISSN：0909-0878
出版年度：1999
卷号：6
期号：43
出版社：Aarhus University
摘要：The pi-calculus with synchronous output and mixed-guarded choices is strictly more expressive than the pi-calculus with asynchronous output and no choice. This result was recently proved by Palamidessi and, as a corollary, she showed that there is no fully compositional encoding from the former into the latter that preserves divergence-freedom and symmetries. This paper argues that there are nevertheless `good' encodings between these calculi. In detail, we present a series of encodings for languages with (1) input-guarded choice, (2) both input- and output-guarded choice, and (3) mixed-guarded choice, and investigate them with respect to compositionality and divergence-freedom. The first and second encoding satisfy all of the above criteria, but various `good' candidates for the third encoding - inspired by an existing distributed implementation - invalidate one or the other criterion. While essentially confirming Palamidessi's result, our study suggests that the combination of strong compositionality and divergence-freedom is too strong for more practical purposes.