On the Expressiveness of Polyadic and Synchronous Communication in Higher-Order Process Calculi

Ivan Lanese 1, 2 Jorge Peréz 1 Davide Sangiorgi 2, 1 Alan Schmitt 3
2 FOCUS - Foundations of Component-based Ubiquitous Systems
CRISAM - Inria Sophia Antipolis - Méditerranée , DISI - Dipartimento di Informatica - Scienza e Ingegneria [Bologna]
3 SARDES - System architecture for reflective distributed computing environments
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : Higher-order process calculi are calculi in which processes can be communicated. We study the expressiveness of strictly higher-order process calculi, and focus on two issues well-understood for first-order calculi but not in the higher-order setting: synchronous vs. asynchronous communication and polyadic vs. monadic communication. First, and similarly to the first-order setting, synchronous process-passing is shown to be encodable into asynchronous process- passing. Then, the absence of name-passing is shown to induce a hierarchy of higher-order process calculi based on the arity of polyadic communication, thus revealing a striking point of contrast with respect to first-order calculi. Finally, the passing of abstractions (i.e., functions from processes to processes) is shown to be more expressive than process-passing alone.
Type de document :
Communication dans un congrès
Samson Abramsky and Cyril Gavoille and Claude Kirchner and Friedhelm Meyer auf der Heide and Paul G. Spirakis. 37th International Colloquium on Automata, Languages and Programming (ICALP 2010), Jul 2010, Bordeaux, France. Springer, 6199, pp.442--453, 2010, Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP 2010)
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00514912
Contributeur : Alan Schmitt <>
Soumis le : vendredi 3 septembre 2010 - 16:41:27
Dernière modification le : mercredi 11 avril 2018 - 01:56:13
Document(s) archivé(s) le : mardi 23 octobre 2012 - 15:31:22

Fichier

Lanese2010On-the-Expressivenes...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00514912, version 1

Collections

Citation

Ivan Lanese, Jorge Peréz, Davide Sangiorgi, Alan Schmitt. On the Expressiveness of Polyadic and Synchronous Communication in Higher-Order Process Calculi. Samson Abramsky and Cyril Gavoille and Claude Kirchner and Friedhelm Meyer auf der Heide and Paul G. Spirakis. 37th International Colloquium on Automata, Languages and Programming (ICALP 2010), Jul 2010, Bordeaux, France. Springer, 6199, pp.442--453, 2010, Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP 2010). 〈inria-00514912〉

Partager

Métriques

Consultations de la notice

573

Téléchargements de fichiers

112