Comparison and analysis of probabilistic systems

17^th February 2023, 13:00 Ashton Lecture Theatre
Dr. Qiyi Tang
Department of Computer Science, University of Liverpool

Abstract

Given a model of computation (e.g., finite automata), and two instances of it, are they semantically equivalent (e.g., do the automata accept the same language)? Such equivalence problems can be viewed as a fundamental question for almost any model of computation. In this talk, we try to answer the fundamental questions for some probabilistic models (Markov chains and Markov decision processes).

We focus on probabilistic bisimilarity, the most prominent notion of behavioural equivalence. We will then have a look at a more robust notion of probabilistic bisimilarity distance, a quantitative generalisation of probabilistic bisimilarity.

We show the following:

• For labelled Markov chains, the development of algorithms to compute probabilistic bisimilarity distance.

• Policy iteration algorithm can be applied to compute the probabilistic bisimilarity distances for labelled Markov chains. In particular, simple policy iteration algorithm takes exponential time in the worst case.

• Comparison of Markov decision processes in terms of probabilistic bisimilarity.

Biography

From Dr. Tang's website: Qiyi is a lecturer (assistant professor) in the Department of Computer Science at the University of Liverpool.

Prior to that, she worked as a postdoctoral researcher in different places. She was a research associate at the University of Liverpool, supervised by Prof. Xiaowei Huang and Prof. Sven Schewe. She was working on algorithmic comparison of probabilistic systems, with Prof. Stefan Kiefer at the University of Oxford and the compiler bug impact project at Imperial College London. Qiyi was also a lecturer at Balliol College, the University of Oxford for the 2020-2021 academic year.

Her research interests include software verification, probabilistic models, automata theory and compiler testing.

She received her Ph.D. in 2018 from York University, Toronto under the supervision of Prof. Franck van Breugel. She received the Governor General's Academic Gold Medal, Canada's most prestigious academic award for students. She has obtained her Master's degree in Computer Science at Oxford University with Distinction in 2013.