Open for all UnRAVeL Members: Talk at QuantLA by Tobias Winkler: Model Checking Temporal Properties of Recursive Probabilistic Programs

Tuesday, December 07, 2021

Location: Online Session

Speaker: Tobias Winkler



Probabilistic pushdown automata (pPDA) are a standard operational model for programming languages involving discrete random choices, procedures, and returns. Temporal properties are useful for gaining insight into the chronological order of events during program execution. Existing approaches in the literature have focused mostly on omega-regular and LTL properties. In this talk, I consider the model checking problem of pPDA against omega-visibly pushdown languages that can be described by specification logics such as CaRet. The latter captures a strict superset of the omega-regular languages. With CaRet formulae, it is possible to specify properties that explicitly take the structured computations arising from procedural programs into account. For example, CaRet is able to match procedure calls with their corresponding future returns, and thus allows to express fundamental program properties like total and partial correctness.