On the Hardness of Almost–Sure Termination

DOI10.1007/978-3-662-48057-1_24zbMath1465.68097arXiv1506.01930OpenAlexW1595069411WikidataQ57800726 ScholiaQ57800726MaRDI QIDQ2946345

Benjamin Lucien Kaminski, Joost-Pieter Katoen

Publication date: 16 September 2015

Published in: Mathematical Foundations of Computer Science 2015 (Search for Journal in Brave)

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

zbMATH Keywords

probabilistic programscomputational hardnessalmost-sure terminationpositive almost-sure terminationexpected outcomes

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) 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 (13)

Understanding Probabilistic Programs ⋮ Calibrating generative models: the probabilistic Chomsky-Schützenberger hierarchy ⋮ On the Hardness of Almost–Sure Termination ⋮ The probabilistic termination tool amber ⋮ Unnamed Item ⋮ Time-bounded termination analysis for probabilistic programs with delays ⋮ On Higher-Order Probabilistic Subrecursion ⋮ Unnamed Item ⋮ On the hardness of analyzing probabilistic programs ⋮ Automated termination analysis of polynomial probabilistic programs ⋮ Weakest Precondition Reasoning for Expected Run–Times of Probabilistic Programs ⋮ Computing expected runtimes for constant probability programs ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Semantics of probabilistic programs
• Classical recursion theory. The theory of functions and sets of natural numbers.
• Classical recursion theory. Vol. II
• Probabilistic termination versus fair termination
• Probabilistic Termination
• On the Hardness of Almost–Sure Termination
• Probabilistic Termination of CHRiSM Programs
• Recursive Predicates and Quantifiers
• Recursively enumerable sets of positive integers and their decision problems
• Measure Transformer Semantics for Bayesian Machine Learning

This page was built for publication: On the Hardness of Almost–Sure Termination