Expressiveness via Intensionality and Concurrency

Thomas Given-Wilson 1
1 COMETE - Concurrency, Mobility and Transactions
Inria Saclay - Ile de France, LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
Abstract : Computation can be considered by taking into account two dimensions: extensional versus intensional, and sequential versus concurrent. Traditionally sequential extensional computation can be captured by the lambda-calculus. However, recent work shows that there are more expressive intensional calculi such as SF-calculus. Traditionally process calculi capture computation by encoding the lambda-calculus, such as in the pi-calculus. Following this increased expressiveness via intensionality, other recent work has shown that concurrent pattern calculus is more expressive than pi-calculus. This paper formalises the relative expressiveness of all four of these calculi by placing them on a square whose edges are irreversible encodings. This square is representative of a more general result: that expressiveness increases with both intensionality and concurrency.
Liste complète des métadonnées

Cited literature [30 references]  Display  Hide  Download
Contributor : Catuscia Palamidessi <>
Submitted on : Tuesday, June 3, 2014 - 11:20:21 AM
Last modification on : Wednesday, March 27, 2019 - 4:41:28 PM
Document(s) archivé(s) le : Wednesday, September 3, 2014 - 11:07:41 AM


Files produced by the author(s)




Thomas Given-Wilson. Expressiveness via Intensionality and Concurrency. ICTAC 2014 - 11th International Colloquium on Theoretical Aspects of Computing, Sep 2014, Bucharest, Romania. pp.206-223, ⟨10.1007/978-3-319-10882-7_13⟩. ⟨hal-00999082⟩



Record views


Files downloads