Type-Based Complexity Analysis of Probabilistic Functional Programs

Martin Avanzini (1) , Ugo Dal Lago (1) , Alexis Ghyselen (2)

1 FOCUS - Foundations of Component-based Ubiquitous Systems
2 ENS de Lyon - École normale supérieure de Lyon

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.

Domaines: Complexité [cs.CC]

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⟩