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, Polytechnique - X, CNRS - Centre National de la Recherche Scientifique : UMR7161
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.
Type de document :
Communication dans un congrès
Gabriel Ciobanu and Dominique Méry. ICTAC 2014 - 11th International Colloquium on Theoretical Aspects of Computing, Sep 2014, Bucharest, Romania. Springer, 8687, pp.206-223, 2014, Lecture Notes in Computer Science. 〈10.1007/978-3-319-10882-7_13〉
Liste complète des métadonnées

Littérature citée [30 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00999082
Contributeur : Catuscia Palamidessi <>
Soumis le : mardi 3 juin 2014 - 11:20:21
Dernière modification le : jeudi 9 février 2017 - 15:17:31
Document(s) archivé(s) le : mercredi 3 septembre 2014 - 11:07:41

Fichier

compute.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Thomas Given-Wilson. Expressiveness via Intensionality and Concurrency. Gabriel Ciobanu and Dominique Méry. ICTAC 2014 - 11th International Colloquium on Theoretical Aspects of Computing, Sep 2014, Bucharest, Romania. Springer, 8687, pp.206-223, 2014, Lecture Notes in Computer Science. 〈10.1007/978-3-319-10882-7_13〉. 〈hal-00999082〉

Partager

Métriques

Consultations de
la notice

463

Téléchargements du document

106