Quantitative Equational Logic
Journal of the ACM · 31.08.2026 · 73 (4) · 1-52
DOI: 10.1145/3818603 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of the ACM, online erschienen am 11.08.2026. Verfasst von Giorgio Bacci und 3 weiteren Autor:innen. Die Arbeit nennt 85 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Natural Sciences and Engineering Research Council of Canada, EPSRC.
Abstract (Originalsprache)
We develop a quantitative analogue of equational reasoning, which we call quantitative equational logic. The quantitative equations use, instead of classical equality, quantitative equalities, which are equalities indexed with nonnegative reals. Thus, s = ɛ t means that “ s and t are points in a metric space and their distance is less than ɛ”. Quantitative equalities will be used to encode behavioural distances, with ɛ being an upper bound on the measure of dissimilarity between two terms. We develop the metatheory of this subject. We define a notion of quantitative algebra, which is the quantitative analogue of universal algebra. We prove a completeness theorem for quantitative equational logic, and we show that we obtain monads on suitable categories of metric spaces. We present a set of examples where the free algebra of a quantitative equational theory corresponds to some well-known structure. These examples are: Hausdorff metrics from quantitative semilattices; p -Wasserstein metrics (hence also the Kantorovich metric), and the total variation metric.
Förderung
- Natural Sciences and Engineering Research Council of Canada
- EPSRC
Zitieren
APA
Bacci, G., Mardare, R., Panangaden, P., & Plotkin, G. (2026). Quantitative Equational Logic. Journal of the ACM, 73(4), 1-52. https://doi.org/10.1145/3818603
Vancouver
Bacci G, Mardare R, Panangaden P, Plotkin G. Quantitative Equational Logic. Journal of the ACM. 2026;73(4):1-52. doi:10.1145/3818603
BibTeX
@article{Bacci2026,
author = {Bacci, Giorgio and Mardare, Radu and Panangaden, Prakash and Plotkin, Gordon},
title = {Quantitative Equational Logic},
journal = {Journal of the ACM},
year = {2026},
volume = {73},
number = {4},
pages = {1--52},
doi = {10.1145/3818603}
}
EUVIMED