Back to Search Start Over

Curry and Howard Meet Borel

Authors :
Melissa Antonelli
Ugo Dal Lago
Paolo Pistone
Department of Computer Science and Engineering [Bologna] (DISI)
Alma Mater Studiorum Università di Bologna [Bologna] (UNIBO)
Foundations of Component-based Ubiquitous Systems (FOCUS)
Inria Sophia Antipolis - Méditerranée (CRISAM)
Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Dipartimento di Informatica - Scienza e Ingegneria [Bologna] (DISI)
Alma Mater Studiorum Università di Bologna [Bologna] (UNIBO)-Alma Mater Studiorum Università di Bologna [Bologna] (UNIBO)
University of Bologna/Università di Bologna
Antonelli, Melissa
Dipartimento di Informatica - Scienza e Ingegneria [Bologna] (DISI)
Dipartimento di Scienze dell'Informazione [Bologna] (DISI)
Melissa Antonelli
Ugo Dal Lago
Paolo Pistone
Source :
LICS 2022-37th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2022-37th Annual ACM/IEEE Symposium on Logic in Computer Science, Aug 2022, Haifa, Israel. ⟨10.1145/3531130.3533361⟩
Publication Year :
2022
Publisher :
HAL CCSD, 2022.

Abstract

International audience; We show that an intuitionistic version of counting propositional logic corresponds, in the sense of Curry and Howard, to an expressive type system for the probabilistic event λ-calculus, a vehicle calculus in which both call-by-name and call-by-value evaluation of discrete randomized functional programs can be simulated. In this context, proofs (respectively, types) do not guarantee that validity (respectively, termination) holds, but reveal the underlying probability. We finally show how to obtain a system precisely capturing the probabilistic behavior of λ-terms, by endowing the type system with an intersection operator.

Details

Language :
English
Database :
OpenAIRE
Journal :
LICS 2022-37th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2022-37th Annual ACM/IEEE Symposium on Logic in Computer Science, Aug 2022, Haifa, Israel. ⟨10.1145/3531130.3533361⟩
Accession number :
edsair.doi.dedup.....1efc979e003ba98a956408ecce80c241