IMDEA Software

IMDEA initiative

Home > Events > Invited Talks > 2023 > Probabilistic Language Inclusion Problems

Tobias Winkler

Tuesday, September 19, 2023

11:00am 302-Mountain View and Zoom3 (, password: @s3)

Tobias Winkler, PhD Candidate, RWTH Aachen University

Probabilistic Language Inclusion Problems


In this talk, I will introduce and motivate a well-studied probabilistic variant of the classic inclusion problem between formal languages. Also known as probabilistic model checking, the problem asks to determine the probability that a word drawn randomly from some known probability measure L (often modelling the behaviour of a system to be verified) is contained in a target language M (modelling the desired system specification). As in the traditional setting, probabilistic language inclusion is typically studied through the lens of automata theory. A generative variant of probabilistic automata (which is closely related to Markov chains) is employed to model probability measures on infinite words. A variety of problems arise by considering automata models with different expressive power, acceptance conditions, etc. The standard approach for solving such problems relies on determinizing the automaton for the target language M, an automata-theoretic product construction, and a numerical analysis of the resulting Markov chain-like stochastic process. I will demonstrate this solution approach with the example of probabilistic pushdown automata and omega-visibly pushdown languages.