Type-Based Complexity Analysis of Probabilistic Functional Programs - Archive ouverte HAL Access content directly
Conference Papers Year :

Type-Based Complexity Analysis of Probabilistic Functional Programs

Abstract

We show that complexity analysis of probabilistic higher-order functional programs can be carried out composi-tionally by way of a type system. The introduced type system is a significant extension of refinement types. On the one hand, the presence of probabilistic effects requires adopting a form of dynamic distribution type, subject to a coupling-based subtyping discipline. On the other hand, recursive definitions are proved terminating by way of Lyapunov ranking functions. We prove not only that the obtained type system, called RPCF, provides a sound methodology for average case complexity analysis, but also that it is extensionally complete, in the sense that any average case polytime Turing machines can be encoded as a term typable in RPCF.
Fichier principal
Vignette du fichier
main.pdf (412 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-02381829 , version 1 (27-11-2019)

Identifiers

Cite

Martin Avanzini, Ugo Dal Lago, Alexis Ghyselen. Type-Based Complexity Analysis of Probabilistic Functional Programs. LICS 2019 - 34th Annual ACM/IEEE Symposium on Logic in Computer Science, Jun 2019, Vancouver, Canada. pp.1-13, ⟨10.1109/LICS.2019.8785725⟩. ⟨hal-02381829⟩
33 View
118 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More