Algorithmic analysis of qualitative and quantitative termination problems for affine probabilistic programs

DOI10.1145/2837614.2837639zbMath1347.68075arXiv1510.08517OpenAlexW2233431969MaRDI QIDQ2828275

Petr Novotný, Krishnendu Chatterjee, Rouzbeh Hasheminezhad, Hongfei Fu

Publication date: 24 October 2016

Published in: Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1510.08517

zbMATH Keywords

terminationconcentrationprobabilistic programsranking supermartingale

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (10)

Learning probabilistic termination proofs ⋮ A denotational semantics for low-level probabilistic programs with nondeterminism ⋮ Unnamed Item ⋮ Probabilistic Termination by Monadic Affine Sized Typing ⋮ On the hardness of analyzing probabilistic programs ⋮ Toward automatic verification of quantum programs ⋮ Automated termination analysis of polynomial probabilistic programs ⋮ Inferring expected runtimes of probabilistic integer programs using expected sizes ⋮ Computing expected runtimes for constant probability programs ⋮ Generating functions for probabilistic programs

This page was built for publication: Algorithmic analysis of qualitative and quantitative termination problems for affine probabilistic programs