Probability and Nondeterminism

• Aim: The goal of this project is to build a theory of processes that faithfully integrates probabilities and nondeterminism.
• Context: A satisfactory semantic theory for processes which encompass both nondeterministic and probabilistic behaviour has been a long-standing research problem. Such a theory is indispensable for the successful modelling, analysis and verification of systems where the interplay of probability and nondeterminism plays an essential role.
         In 1992 Wang & Larsen posed the problems of finding complete axiomatisations and alternative characterisations for a natural generalisation of the standard testing preorders to such processes. Recently, we solved both for finite processes, by providing a detailed account of both may- and must testing preorders for a finite version of the process calculus CSP extended with probabilistic choice. Further work deals with infinite processes, and generalisations to other testing disciplines, such as reward testing.
• Approach: We bring together techniques from process algebra, Markov decision processes and Euclidean geometry (e.g. separating hyperplane lemmas).
• Collaboration: CSIRO's Data61, Shanghai Jiao Tong University, Trinity College Dublin.

People

Publications

2019

		Rob van Glabbeek, Jan Friso Groote and Erik de Vink A complete axiomatization of branching bisimilarity for a simple process language with probabilistic choice The Art of Modelling Computational Systems: A Journey from Logic and Concurrency to Security and Privacy — Essays Dedicated to Catuscia Palamidessi on the Occasion of Her 60th Birthday, pp. 139-162, Paris, November, 2019
		Carroll Morgan, Annabelle McIver and Tahiry Rabehaja Abstract hidden markov models: A monadic account of quantitative information flow Mathematical Structures in Computer Science, Volume 15, Issue 1, pp. 36:1-36:50, March, 2019
		Nick Fischer and Rob van Glabbeek Axiomatising infinitary probabilistic weak bisimilarity of finite-state behaviours Journal of Logical and Algebraic Methods in Programming, Volume 102, pp. 64-102, January, 2019

2018

Annabelle McIver, Carroll Morgan, Benjamin Kaminski and Joost-Pieter Katoen A new proof rule for almost-sure termination ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Los Angeles, January, 2018

2014

Yuxin Deng, Rob van Glabbeek, Matthew Hennessy and Carroll Morgan Real reward testing for probabilistic processes Theoretical Computer Science, Volume 538, pp. 16–36, July, 2014

2011

Yuxin Deng, Rob van Glabbeek, Matthew Hennessy and Carroll Morgan Real reward testing for probabilistic processes (extended abstract) Ninth Workshop on Quantitative Aspects of Programming Languages (QAPL 2011), pp. 61–73, Saarbrücken, Germany, July, 2011

2010

Yuxin Deng and Rob van Glabbeek Characterising probabilistic processes logically (extended abstract) Proceedings of the 17th International Conference on Logic for Programming, Artificial Intelligence and Reasoning, pp. 278–293, Yogyakarta, Indonesia, October, 2010

2009

Yuxin Deng, Rob van Glabbeek, Matthew Hennessy and Carroll Morgan Testing finitary probabilistic processes (extended abstract) Proceedings of the 20th International Conference on Concurrency Theory (CONCUR), pp. 274–288, Bologna, Italy, August, 2009

2008

Yuxin Deng, Rob van Glabbeek, Matthew Hennessy and Carroll Morgan Characterising testing preorders for finite probabilistic processes Logical Methods in Computer Science, Volume 4, Number 4, pp. 1–33, October, 2008

2007

		Yuxin Deng, Rob van Glabbeek, Matthew Hennessy, Carroll Morgan and Cuicui Zhang Characterising testing preorders for finite probabilistic processes Proceedings of the 22nd Annual IEEE Symposium on Logic in Computer Science, pp. 313–322, Wroclaw, Poland, July, 2007
		Yuxin Deng, Rob van Glabbeek, Matthew Hennessy, Carroll Morgan and Cuicui Zhang Remarks on testing probabilistic processes Electronic Notes in Theoretical Computer Science, Volume 172, Number , pp. 359–397, April, 2007
		Yuxin Deng, Rob van Glabbeek, Carroll Morgan and Chenyi Zhang Scalar outcomes suffice for finitary probabilistic testing Proceedings of the 16thEuropean Symposium on Programming, pp. 363–378, Braga, Portugal, March, 2007