Model Checking Recursive Probabilistic Programs with Conditioning

We address the problem of model checking temporal logic specifications for discrete probabilistic programs with recursive procedures, nested queries, and hard conditioning expressed with observe statements. We give them an operational semantics in terms of \emph{probabilistic Operator Precedence Automata} (pOPA), a novel class of probabilistic pushdown automata suitable to model constructs and behaviors of probabilistic programs. We develop a model checking algorithm that can verify requirements expressed in a fragment of Precedence Oriented Temporal Logic (POTLf$\chi$) on a pOPA in single \textsc{exptime}. POTLf$\chi$ is a temporal logic based on Operator Precedence Languages, which features modalities that interact with the context-free structure of program traces, matching procedure calls with returns or observe statements. We provide the \emph{first} probabilistic model checking implementation of context-free language properties for probabilistic pushdown systems.
Comment: 43 pages, 16 figures