On Higher-Order Probabilistic Subrecursion

Flavien Breuvart 1 Ugo Dal Lago 1, 2 Agathe Herrou 3
1 FOCUS - Foundations of Component-based Ubiquitous Systems
CRISAM - Inria Sophia Antipolis - Méditerranée , DISI - Dipartimento di Informatica - Scienza e Ingegneria [Bologna]
Abstract : We study the expressive power of subrecursive probabilistic higher-order calculi. More specifically, we show that endowing a very expressive deterministic calculus like Gödel's T with various forms of probabilistic choice operators may result in calculi which are not equivalent as for the class of distributions they give rise to, although they all guarantee almost-sure termination. Along the way, we introduce a probabilistic variation of the classic reducibility technique, and we prove that the simplest form of probabilistic choice leaves the expressive power of T essentially unaltered. The paper ends with some observations about functional expressivity: expectedly, all the considered calculi represent precisely the functions which T itself represents.
Type de document :
Communication dans un congrès
FoSSaCS 2017 - 20th International Conference on Foundations of Software Science and Computation Structures, Apr 2017, Uppsala, Sweden. 10203, pp.370-386, LNCS. 〈10.1007/978-3-662-54458-7_22〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01639379
Contributeur : Ugo Dal Lago <>
Soumis le : lundi 20 novembre 2017 - 13:18:36
Dernière modification le : samedi 29 septembre 2018 - 01:15:34
Document(s) archivé(s) le : mercredi 21 février 2018 - 14:41:14

Fichier

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

Identifiants

Citation

Flavien Breuvart, Ugo Dal Lago, Agathe Herrou. On Higher-Order Probabilistic Subrecursion. FoSSaCS 2017 - 20th International Conference on Foundations of Software Science and Computation Structures, Apr 2017, Uppsala, Sweden. 10203, pp.370-386, LNCS. 〈10.1007/978-3-662-54458-7_22〉. 〈hal-01639379〉

Partager

Métriques

Consultations de la notice

535

Téléchargements de fichiers

53