Environmental Bisimulations for Probabilistic Higher-Order Languages

Davide Sangiorgi 1, 2 Valeria Vignudelli 1, 2
2 FOCUS - Foundations of Component-based Ubiquitous Systems
CRISAM - Inria Sophia Antipolis - Méditerranée , DISI - Dipartimento di Informatica - Scienza e Ingegneria [Bologna]
Abstract : Environmental bisimulations for probabilistic higher-order languages are studied. In contrast with applicative bisimulations, environmental bisimulations are known to be more robust and do not require sophisticated techniques such as Howe's in the proofs of congruence. As representative calculi, call-by-name and call-by-value λ-calculus, and a (call-by-value) λ-calculus extended with references (i.e., a store) are considered. In each case full abstraction results are derived for probabilistic environmental similarity and bisimilarity with respect to contextual preorder and contextual equivalence, respectively. Some possible enhancements of the (bi)simulations, as 'up-to techniques', are also presented. Probabilities force a number of modifications to the definition of environmental bisimulations in non-probabilistic languages. Some of these modifications are specific to probabilities, others may be seen as general refinements of environmental bisimulations, applicable also to non-probabilistic languages. Several examples are presented, to illustrate the modifications and the differences.
Type de document :
Communication dans un congrès
POPL '16, Jan 2016, St. Petersburg, United States. Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. 〈http://conf.researchr.org/home/POPL-2016〉. 〈10.1145/2837614.2837651〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01337665
Contributeur : Vignudelli Valeria <>
Soumis le : lundi 27 juin 2016 - 14:00:18
Dernière modification le : mercredi 10 octobre 2018 - 10:09:58
Document(s) archivé(s) le : mercredi 28 septembre 2016 - 11:26:38

Fichier

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

Identifiants

Collections

Citation

Davide Sangiorgi, Valeria Vignudelli. Environmental Bisimulations for Probabilistic Higher-Order Languages. POPL '16, Jan 2016, St. Petersburg, United States. Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. 〈http://conf.researchr.org/home/POPL-2016〉. 〈10.1145/2837614.2837651〉. 〈hal-01337665〉

Partager

Métriques

Consultations de la notice

228

Téléchargements de fichiers

158