Quantitative algebraic reasoning

Radu Mardare, Prakash Panangaden, Gordon Plotkin

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

23 Citations (Scopus)
9 Downloads (Pure)

Abstract

We develop a quantitative analogue of equational reasoning which we call quantitative algebra. We define an equality relation indexed by rationals: a = ϵ b which we think of as saying that "a is approximately equal to b up to an error of ϵ ". We have 4 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 four cases are: Hausdorff metrics from quantitive semilattices; p-Wasserstein metrics (hence also the Kantorovich metric) from barycentric algebras and also from pointed barycentric algebras and the total variation metric from a variant of barycentric algebras.

Original languageEnglish
Title of host publicationLICS '16 : Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science
Place of PublicationNew York, NY.
Pages700-709
Number of pages10
DOIs
Publication statusPublished - 5 Jul 2016
Event31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2016 - New York, United States
Duration: 5 Jul 20168 Jul 2016

Conference

Conference31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2016
CountryUnited States
CityNew York
Period5/07/168/07/16

Keywords

  • algebraic reasoning
  • quantitative algebra
  • probabilistic programming
  • semantics
  • computer circuits
  • reconfigurable hardware
  • equality relations
  • equational theory
  • Kantorovich metric

Fingerprint Dive into the research topics of 'Quantitative algebraic reasoning'. Together they form a unique fingerprint.

Cite this