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 language | English |
|---|---|
| Title of host publication | LICS '16 : Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science |
| Place of Publication | New York, NY. |
| Pages | 700-709 |
| Number of pages | 10 |
| DOIs | |
| Publication status | Published - 5 Jul 2016 |
| Event | 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2016 - New York, United States Duration: 5 Jul 2016 → 8 Jul 2016 |
Conference
| Conference | 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2016 |
|---|---|
| Country/Territory | United States |
| City | New York |
| Period | 5/07/16 → 8/07/16 |
Keywords
- algebraic reasoning
- quantitative algebra
- probabilistic programming
- semantics
- computer circuits
- reconfigurable hardware
- equality relations
- equational theory
- Kantorovich metric