Back to Search
Start Over
Curry and Howard Meet Borel
- 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.
- Subjects :
- FOS: Computer and information sciences
Computer Science - Logic in Computer Science
D.3.1
Proof theory
Counting Logic
Mathematics - Logic
[INFO] Computer Science [cs]
Curry-Howard Correspondence, Probabilistic Computation, Counting Logic, Termination, Intersection Types
Logic in Computer Science (cs.LO)
TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES
TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS
Computer Science::Logic in Computer Science
Intersection Types
Probabilistic computation Curry-Howard Correspondence
FOS: Mathematics
F.4.1
F.3.2
Probabilistic Computation
[INFO]Computer Science [cs]
Logic (math.LO)
Termination
Subjects
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