Runtime analysis of probabilistic programs with unbounded recursion

DOI10.1016/j.jcss.2014.06.005zbMath1410.68083OpenAlexW1922177649MaRDI QIDQ743128

Tomáš Brázdil, Ivana Hutařová Vařeková, Stefan Kiefer, Antonín Kučera

Publication date: 22 September 2014

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2014.06.005

zbMATH Keywords

termination timeprobabilistic pushdown automatarecursive Markov chains

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Other programming paradigms (object-oriented, sequential, concurrent, automatic, etc.) (68N19) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Automata and formal grammars in connection with logical questions (03D05) 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 (5)

A denotational semantics for low-level probabilistic programs with nondeterminism ⋮ Recursive stochastic games with positive rewards ⋮ Probabilistic total store ordering ⋮ Weakest Precondition Reasoning for Expected Run–Times of Probabilistic Programs ⋮ Moment-based analysis of Bayesian network properties

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Generalisations of the Bienaymé-Galton-Watson branching process via its representations as an embedded random walk
• One-Counter Stochastic Games
• Computing the Least Fixed Point of Positive Polynomial Systems
• Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations
• Probability with Martingales
• Introduction to Matrix Analytic Methods in Stochastic Modeling
• Convergence Thresholds of Newton's Method for Monotone Polynomial Equations
• Numerical Methods for Structured Markov Chains
• Discounted Properties of Probabilistic Pushdown Automata
• Some limit theorems for the total progeny of a branching process
• Tools and Algorithms for the Construction and Analysis of Systems
• Concentration of Measure for the Analysis of Randomized Algorithms

This page was built for publication: Runtime analysis of probabilistic programs with unbounded recursion