Complex probabilistic/stochastic processes are of central importance in modern computing, representing new challenges in Engineering and Technology, both from theoretical and practical perspectives. They involve real-valued parameters (probabilities of transitions, distributions characterizing the residence-time in a state, etc.) to abstract missing information, model ignorance, uncertainty or inherent randomness. Advances in verification of probabilistic and real-time systems as well as the tremendous growth of applications in cyber-physical systems, machine learning, and planning under uncertainty testify to their importance. To develop dedicated probabilistic/stochastic programming languages or theories of systems, one needs to reconsider the foundations of computational theory, since the classic logical principles supporting it must be replaced with non-classical (e.g., measure-theoretic) probabilistic principles. More concretely, identifying probabilistic processes with identical probabilistic behaviours, as the classic computability theory does, is too `exact' for most purposes. In applications, one instead needs to know whether two processes that may differ by a small amount in their real-valued parameters have sufficiently similar behaviours, or to study the behavioural divergence-convergence of inequivalent probabilistic programs.

In this talk I will discuss two such non-standard semantics: the metric semantics and the Boolean-valued semantics, with their advantages and limitations. And I will present some technical details and challenges emerging form the metric semantics.

Bibliography:

[1] R. Mardare, P. Panangaden, G. Plotkin. Quantitative Algebraic Reasoning, LICS 2016.

[2] R. Mardare, P. Panangaden, G. Plotkin. On the Axiomatizability of Quantitative Algebras, LICS 2017.

[3] G. Bacci, R. Mardare, P. Panangaden, G. Plotkin. An Algebraic Theory of Markov Processes, LICS 2018.

[4] G. Bacci, R. Furber, D. Kozen, R. Mardare, P. Panangaden, Dana Scott. Boolean-Valued Semantics for Stochastic Lambda-Calculus, LICS 2018.