On the Discriminating Power of Passivation and Higher-Order Interaction

Marco Bernardo 1 Davide Sangiorgi 2, 3 Valeria Vignudelli 2, 3
2 FOCUS - Foundations of Component-based Ubiquitous Systems
CRISAM - Inria Sophia Antipolis - Méditerranée , DISI - Dipartimento di Informatica - Scienza e Ingegneria [Bologna]
Abstract : This paper studies the discriminating power offered by higher-order concurrent languages, and contrasts this power with those offered by higher-order sequential languages (a la lambda-calculus) and by first-order concurrent languages (a la CCS). The concurrent higher-order languages that we focus on are Higher-Order pi-calculus (HOpi), which supports higher-order communication, and an extension of HOpi with passivation, a simple higher-order construct that allows one to obtain location-dependent process behaviours. The comparison is carried out by providing embeddings of first-order processes into the various languages, and then examining the resulting contextual equivalences induced on such processes. As first-order processes we consider both ordinary Labeled Transition Systems (LTSs) and Reactive Probabilistic Labeled Transition Systems (RPLTSs). The hierarchy of discriminating powers so obtained for RPLTSs is finer than that for LTSs. For instance, in the LTS case, the additional discriminating power offered by passivation in concurrency is captured, in sequential languages, by the difference between the call-by-name and call-by-value evaluation strategies of an extended typed lambda-calculus.
Liste complète des métadonnées

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

Contributeur : Vignudelli Valeria <>
Soumis le : mercredi 3 décembre 2014 - 17:00:58
Dernière modification le : samedi 27 janvier 2018 - 01:31:34
Document(s) archivé(s) le : lundi 9 mars 2015 - 05:51:32


Fichiers produits par l'(les) auteur(s)




Marco Bernardo, Davide Sangiorgi, Valeria Vignudelli. On the Discriminating Power of Passivation and Higher-Order Interaction. CSL-LICS '14, Jul 2014, Vienna, Austria. 〈http://lics.rwth-aachen.de/csl-lics14/〉. 〈10.1145/2603088.2603113〉. 〈hal-01089467〉



Consultations de la notice


Téléchargements de fichiers