Skip to Main content Skip to Navigation
New interface
Conference papers

Asynchronous pi-calculus at Work: The Call-by-Need Strategy

Davide Sangiorgi 1, 2 
2 FOCUS - Foundations of Component-based Ubiquitous Systems
CRISAM - Inria Sophia Antipolis - Méditerranée , DISI - Dipartimento di Informatica - Scienza e Ingegneria [Bologna]
Abstract : In a well-known and influential paper [17] Palamidessi has shown that the expressive power of the Asynchronous π-calculus is strictly less than that of the full (synchronous) $π$-calculus. This gap in expres-siveness has a correspondence, however, in sharper semantic properties for the former calculus, notably concerning algebraic laws. This paper substantiates this, taking, as a case study, the encoding of call-by-need λ-calculus into the $π$-calculus. We actually adopt the Local Asynchronous π-calculus, that has even sharper semantic properties. We exploit such properties to prove some instances of validity of $β$-reduction (meaning that the source and target terms of a $β$-reduction are mapped onto be-haviourally equivalent processes). Nearly all results would fail in the ordinary synchronous $π$-calculus. We show that however the full $β$-reduction is not valid. We also consider a refined encoding in which some further instances of $β$-validity hold. We conclude with a few questions for future work.
Complete list of metadata

Cited literature [35 references]  Display  Hide  Download
Contributor : Davide Sangiorgi Connect in order to contact the contributor
Submitted on : Monday, December 9, 2019 - 11:12:33 AM
Last modification on : Wednesday, February 2, 2022 - 3:56:17 PM
Long-term archiving on: : Tuesday, March 10, 2020 - 3:39:50 PM


Files produced by the author(s)




Davide Sangiorgi. Asynchronous pi-calculus at Work: The Call-by-Need Strategy. The Art of Modelling Computational Systems: A Journey from Logic and Concurrency to Security and Privacy, Nov 2019, Paris, France. pp.33-49, ⟨10.1007/978-3-030-31175-9_3⟩. ⟨hal-02399695⟩



Record views


Files downloads