Department of Computer Science and Technology

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}
}