Since 2014
What Is a ‘Good’ Encoding of Guarded Choice?
BRICS Report Series
View Archive Info| Field | Value | |
| Title |
What Is a ‘Good’ Encoding of Guarded Choice?
|
|
| Creator |
Nestmann, Uwe
|
|
| Description |
The pi-calculus with synchronous output and mixed-guarded choices is strictly more expressive than the pi-calculus with asynchronous output and no choice. As a corollary, Palamidessi recently proved that there is no fully compositional encodingfrom the former into the latter that preserves divergence-freedom and symmetries. This paper shows 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 firstand 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 studysuggests that the combination of strong compositionality and divergence-freedom is too strong for more practical purposes.
|
|
| Publisher |
Aarhus University
|
|
| Date |
1997-06-15
|
|
| Type |
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion |
|
| Format |
application/pdf
|
|
| Identifier |
https://tidsskrift.dk/brics/article/view/19266
10.7146/brics.v4i45.19266 |
|
| Source |
BRICS Report Series; No 45 (1997): RS-45 What Is a ‘Good’ Encoding of Guarded Choice?
BRICS Report Series; Nr. 45 (1997): RS-45 What Is a ‘Good’ Encoding of Guarded Choice? 1601-5355 0909-0878 |
|
| Language |
eng
|
|
| Relation |
https://tidsskrift.dk/brics/article/view/19266/16893
|
|
| Rights |
Copyright (c) 2014 BRICS Report Series
|
|