Technical reports
Decoding choice encodings
Uwe Nestmann, Benjamin C. Pierce
April 1996, 54 pages
DOI: 10.48456/tr-392
Abstract
We study two encodings of the asynchronous π-calculus with input-guarded choice into its choice-free fragment. One encoding is divergence-free, but refines the atomic commitment of choice into gradual commitment. The other preserves atomicity, but introduces divergence. The divergent encoding is fully abstract with respect to weak bisumulation, but the more natural divergence-free encoding is not. Instead we shot that it is fully abstract with respect to coupled simulation, a slightly coarser -- but still coinductively defined -- equivalence that does not require bisimilarity of internal branching decisions. The correctness proofs for the two choice encodings exploit the properties of decodings from translations to source terms.
Full text
PDF (3.7 MB)
BibTeX record
@TechReport{UCAM-CL-TR-392, author = {Nestmann, Uwe and Pierce, Benjamin C.}, title = {{Decoding choice encodings}}, year = 1996, month = apr, url = {https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-392.pdf}, institution = {University of Cambridge, Computer Laboratory}, doi = {10.48456/tr-392}, number = {UCAM-CL-TR-392} }