On Higher-Order Probabilistic Subrecursion - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2017

On Higher-Order Probabilistic Subrecursion

Résumé

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.
Fichier principal
Vignette du fichier
main.pdf (456.04 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01639379 , version 1 (20-11-2017)

Identifiants

Citer

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. pp.370-386, ⟨10.1007/978-3-662-54458-7_22⟩. ⟨hal-01639379⟩
526 Consultations
122 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More