Probabilistic termination by monadic affine sized typing
From MaRDI portal
Abstract: We introduce a system of monadic affine sized types, which substantially generalise usual sized types, and allows this way to capture probabilistic higher-order programs which terminate almost surely. Going beyond plain, strong normalisation without losing soundness turns out to be a hard task, which cannot be accomplished without a richer, quantitative notion of types, but also without imposing some affinity constraints. The proposed type system is powerful enough to type classic examples of probabilistically terminating programs such as random walks. The way typable programs are proved to be almost surely terminating is based on reducibility, but requires a substantial adaptation of the technique.
Recommendations
- Probabilistic termination: soundness, completeness, and compositionality
- New approaches for almost-sure termination of probabilistic programs
- Algorithmic analysis of qualitative and quantitative termination problems for affine probabilistic programs
- On probabilistic term rewriting
- scientific article; zbMATH DE number 1927425
Cites work
- scientific article; zbMATH DE number 1189292 (Why is no real title available?)
- scientific article; zbMATH DE number 42059 (Why is no real title available?)
- scientific article; zbMATH DE number 48812 (Why is no real title available?)
- scientific article; zbMATH DE number 1223626 (Why is no real title available?)
- scientific article; zbMATH DE number 2090077 (Why is no real title available?)
- scientific article; zbMATH DE number 819814 (Why is no real title available?)
- scientific article; zbMATH DE number 1408945 (Why is no real title available?)
- A Short Introduction to Implicit Computational Complexity
- A Tutorial on Type-Based Termination
- A higher-order characterization of probabilistic polynomial time
- Algorithmic analysis of qualitative and quantitative termination problems for affine probabilistic programs
- Computer-Aided Security Proofs for the Working Cryptographer
- Dependent types for program termination verification
- Formal certification of code-based cryptographic proofs
- Linear dependent types and relative completeness
- On equivalences, metrics, and polynomial time
- One-counter Markov decision processes
- Probabilistic operational semantics for the lambda calculus
- Probabilistic termination by monadic affine sized typing
- Probabilistic termination: soundness, completeness, and compositionality
- Realizability models and implicit complexity
- Term Rewriting and Applications
- Termination analysis of probabilistic programs through Positivstellensatz's
- Termination checking with types
- Type-Based Termination with Sized Products
- Type-based termination of recursive definitions
Cited in
(13)- Probabilistic Analysis of Binary Sessions
- Probabilistic termination by monadic affine sized typing
- On the hardness of analyzing probabilistic programs
- On the termination problem for probabilistic higher-order recursive programs
- Automated termination analysis of polynomial probabilistic programs
- Program equivalence in a typed probabilistic call-by-need functional language
- scientific article; zbMATH DE number 7376040 (Why is no real title available?)
- On lexicographic proof rules for probabilistic termination
- From innermost to full almost-sure termination of probabilistic term rewriting
- Proving Almost-Sure Innermost Termination of Probabilistic Term Rewriting Using Dependency Pairs
- Curry and Howard meet Borel
- Type-based complexity analysis of probabilistic functional programs
- The geometry of Bayesian programming
This page was built for publication: Probabilistic termination by monadic affine sized typing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2988649)
