Skip to Main content Skip to Navigation
Conference papers

Expressiveness via Intensionality and Concurrency

Thomas Given-Wilson 1 
1 COMETE - Concurrency, Mobility and Transactions
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France
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.
Complete list of metadata

Cited literature [30 references]  Display  Hide  Download
Contributor : Catuscia Palamidessi Connect in order to contact the contributor
Submitted on : Tuesday, June 3, 2014 - 11:20:21 AM
Last modification on : Saturday, June 25, 2022 - 7:46:54 PM
Long-term archiving on: : 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