Quantitative Algebraic Reasoning

Add to your list(s) Download to your calendar using vCal

• Radu Mardare, University of Aalborg
• Friday 02 November 2018, 10:30-11:30
• Computer Science, The Sloman Lounge (UG).

If you have a question about this talk, please contact Jamie Vicary.

This talk summarizes a series of results that we got while trying to understand whether the concept of behavioural metric (metric semantics) for stochastic/probabilistic systems can be achieved in a canonical way from the given mathematical structure of a system, and without ad hoc assumptions. Starting from generalizing Stone-like dualities, we eventually proposed a quantitative extension of the concept of universal algebra, called Quantitative Algebra. These are algebras supported by metric spaces and characterized by quantitative equational theories. Similarly to the way a classic equational theory characterizes a congruence, a quantitative equational theory characterizes a metric over the support set of an algebra. In this way, instead of getting a monad on Set, one gets a monad on the category of metric spaces and nonexpansive maps. The development remains sound while restricting the arguments to the category of complete or complete separable metric spaces.

We identified axiomatic systems for metrics such as Kantorovich, p-Wasserstein, Hausdorff and more. Interesting in this settings is to observe how these metrics emerge from well-known, but apparently unrelated, algebraic structures.

This talk is based on a series of papers (LICS’16, LICS ’17, LICS ’18) in collaboration with Gordon Plotkin and Prakash Panangaden.

This talk is part of the Theoretical computer science seminar series.

This talk is included in these lists:

• Computer Science Departmental Series
• Computer Science Distinguished Seminars
• Computer Science, The Sloman Lounge (UG)
• Theoretical computer science seminar
• computer sience

Note that ex-directory lists are not shown.