Fall 2016

Quantitative Algebraic Reasoning

Tuesday, Oct. 4, 2016 2:00 pm2:40 pm

Add to Calendar


Calvin Lab Auditorium

We develop a quantitative analogue of equational reasoning which we call quantitative algebraic reasoning. We define an indexed equality relation of type a =_e b which we think of as saying that “a is approximately equal to b up to an error of e”. The models are universal algebras defined on metric spaces.
We have interesting examples where we have a quantitative equational theory whose free algebras correspond to well known structures. In each case we have finitary and continuous versions. The cases are: Hausdorff metrics from quantitive semilattices; p-Wasserstein metrics (hence also the Kantorovich metric) from barycentric algebras; and the total variation distance from a particular type of barycentric algebras.

This is a joint work with Gordon Plotkin and Prakash Panangaden; preliminary results have been presented at LICS2016.

File Quantitative Algebraic Reasoning24.91 MB