Modular Runtime Complexity Analysis of Probabilistic While Programs

2019/08/23 by Avanzini, Martin, Schaper, Michael, Moser, Georg
#FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Programming Languages (cs.PL)

paper · doi:10.48550/arxiv.1908.11343

Abstract

We are concerned with the average case runtime complexity analysis of a prototypical imperative language endowed with primitives for sampling and probabilistic choice. Taking inspiration from known approaches from to the modular resource analysis of non-probabilistic programs, we investigate how a modular runtime analysis is obtained for probabilistic programs.

Related

• Inferring Expected Runtimes of Probabilistic Integer Programs Using Expected Sizes
• Program Analysis of Probabilistic Programs
• Probabilistic Programming Concepts
• Asymptotic Complexity Estimates for Probabilistic Programs and their VASS Abstractions
• Bounded Expectations: Resource Analysis for Probabilistic Programs