EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Quantitative Equational Logic

Giorgio Bacci, Radu Mardare, Prakash Panangaden, Gordon Plotkin

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →