Quantitative algebraic reasoning

Mardare, Radu and Panangaden, Prakash and Plotkin, Gordon; (2016) Quantitative algebraic reasoning. In: Proceedings of the 31st Annual ACM-IEEE Symposium on Logic in Computer Science, LICS 2016. Association for Computing Machinery (ACM), USA, pp. 700-709. ISBN 9781450343916

[img]
Preview
Text (Mardare-etal-LICS2016-Quantitative-algebraic-reasoning)
Mardare_etal_LICS2016_Quantitative_algebraic_reasoning.pdf
Final Published Version
License: Unspecified

Download (328kB)| Preview

    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.