Laboratoire d'informatique de l'École polytechnique

Talk by Prakash Panangaden: «Quantitative Equational Logic»

Speaker: Prakash Panangaden
Location: Salle Philippe Flajolet, (LIX - Alan Turing building)
Date: Mon, 12 Feb 2018, 14:00-15:00

The next Comète seminar will take place on Monday 12th of February 2017 at 14h00 in Salle Philippe Flajolet (LIX - Alan Turing building, École Polytechnique). Prakash Panangaden, Professor at McGill University School of Computer Science, will talk about his joint work with Radu Mardare and Gordon Plotkin: Quantitative Equational Logic.

Abstract: Equational reasoning is a central part of mathematics. The traditional theory links the equational logic and monads on the category of sets. More precisely, one can define an algebraic theory by giving a set of operations and equations. One can then show that the collection of algebras defined by these equations form the algebras for a monad on the category of sets. One has classical theorems like the completeness and variety theorems of Birkhoff. We consider a modified notion of equation where the equality symbol is annotated with a real number so we can write s =_e t with the interpretation that the terms "s" and "t" are within "e" of each other. We develop the metatheory and obtain some analogues of the classical theorems. Furthermore, we show that this extended notion of equational definition yields algebras of monads on the category of metric spaces. What makes the theory interesting is the fact that well known metric spaces of probability distributions can be defined by such equations.