Expressiveness of probabilistic \pi-calculi

Sylvain Pradalier 1 Catuscia Palamidessi 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 : In this work we propose a probabilistic extension of the -calculus. The main novelty is a probabilistic mixed choice operator, that is, a choice construct with a probability distribution on the branches, and where input and output actions can both occur as guards. We develop the operational semantics of this calculus, and then we investigate its expressiveness. In particular, we compare it with the sublanguage with the two separate choices, where input and output guards are not allowed together in the same choice construct. Our main result is that the separate choices can encode the mixed one. Further, we show that input-guarded choice can encode output-guarded choice and viceversa. In contrast, we conjecture that neither of them can encode the pair of the two separate choices.
Type de document :
Communication dans un congrès
Alessandra Di Pierro and Herbert Wiklicky. 4th International Workshop on Quantitative Aspects of Programming Languages (QAPL), Apr 2006, Vienna, Austria. Elsevier, 164 (3), 2006, Electronic Notes in Theoretical Computer Science. 〈10.1016/j.entcs.2006.07.015〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00201088
Contributeur : Catuscia Palamidessi <>
Soumis le : dimanche 23 décembre 2007 - 12:43:17
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : jeudi 27 septembre 2012 - 13:21:38

Fichier

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

Identifiants

Collections

Citation

Sylvain Pradalier, Catuscia Palamidessi. Expressiveness of probabilistic \pi-calculi. Alessandra Di Pierro and Herbert Wiklicky. 4th International Workshop on Quantitative Aspects of Programming Languages (QAPL), Apr 2006, Vienna, Austria. Elsevier, 164 (3), 2006, Electronic Notes in Theoretical Computer Science. 〈10.1016/j.entcs.2006.07.015〉. 〈inria-00201088〉

Partager

Métriques

Consultations de la notice

219

Téléchargements de fichiers

74