Quantitative Equational Logic

37 concepts23 papers3 proposals

In classical computer science and formal logic, correctness is binary. Two programs are either exactly identical ($t = s$), or they are completely different. A system implementation either perfectly satisfies its specification, or it fails.

As highlighted by Dahlqvist et al. in The syntactic side of autonomous categories enriched over generalised metric spaces, this "all-or-nothing" paradigm breaks down when applied to modern computational domains like probabilistic algorithms, cyber-physical systems, and quantum computing. If a physical system or a randomized algorithm deviates from its specification by a fraction of a millisecond or a tiny probability threshold, classical logic completely rejects the model.

To resolve this fragility, researchers have developed Quantitative Equational Logic. Instead of asking whether two terms or systems are identical, this framework reformulates logic to measure how close they are, providing a rigorous mathematical foundation for approximate reasoning.

From Binary Truth to Distance-Indexed Relations

The core mechanism of quantitative equational logic replaces the standard binary equality relation ($=$) with a family of distance-indexed relations, written as:

$$t =_\epsilon s$$

where $\epsilon \ge 0$ represents a numerical upper bound on the distance between two elements in a metric space.

In Quantitative Algebraic Reasoning, Mardare et al. established a foundational framework where axioms specify how these distance bounds propagate through functional combinations. For example, a quantitative axiom might state that if two inputs are within a distance of $\epsilon$, their functional outputs must remain within a distance of $f(\epsilon)$. This allows the logic to capture Lipschitz continuity and other geometric properties directly within the syntax, as further developed by the authors in On the axiomatizability of quantitative algebras.

To make this logic universally applicable across different types of systems (such as tracking execution latency, energy costs, or probabilistic variation), the logic can be parameterized using an algebraic structure known as a quantale. As shown by Dahlqvist et al. in A Complete V-Equational System for Graded lambda-Calculus, replacing boolean truth values with elements from a quantale allows the exact same set of logical rules to reason about entirely disparate metrics. When parameterized by the Lawvere quantale ($[0, \infty]$), distances themselves become the primary truth values, enabling dedicated propositional logics where consistency checking remains fully decidable (Bacci et al. in Propositional Logics for the Lawvere Quantale).

Achieving Logical Completeness

For a quantitative logic to be useful, it must be complete: every valid statement about distances in a geometric model must be derivable using purely syntactic proof rules.

A series of breakthrough results proved that approximate equality can be fully axiomatized. Mardare et al. demonstrated strong completeness for bounded metric algebras in Quantitative Algebraic Reasoning, bridging the gap between abstract metric geometry and formal equational deduction. This means that instead of performing complex continuous math to verify a system, a developer can use discrete, symbolic rules to calculate error bounds.

This completeness holds true even under complex mathematical conditions:

  • Fixed-Points: In Fixed-Points for Quantitative Equational Logics, the authors proved that all valid properties of approximate fixed points—essential for analyzing iterative behaviors like loops or reinforcement learning algorithms—can be derived from finite sets of axioms.
  • Non-Compact Spaces: Even when dealing with non-compact quantitative logics, Hansen et al. showed in A Complete Approximation Theory for Weighted Transition Systems that a finitary complete axiomatization is achievable, meaning proofs do not require infinitely long rules.

Compositionality and Quantitative Effects

A major challenge in formal methods is scaling verification to large systems. This requires compositionality: the ability to reason about the distance bounds of a combined system by looking only at the distance bounds of its individual components.

By establishing a formal correspondence between the syntax of quantitative equations and the categorical semantics of monads on metric spaces, researchers can combine different quantitative behaviors cleanly. In Sum and Tensor of Quantitative Effects, the authors provided a modular way to construct complex systems from simple, reusable building blocks.

For instance, Bacci et al. utilized the tensor product of quantitative equational theories to provide the first modular, algebraic axiomatizations for Labelled Markov Processes and Markov Decision Processes, ensuring that quantitative effects like rewards and probabilities commute smoothly (Tensor of Quantitative Equational Theories). Similarly, the space of Radon probability measures equipped with the Wasserstein distance can be modeled as a free complete algebra for probabilistic choice, guaranteeing that the underlying geometry of the space is preserved during composition (Mardare et al. in Free complete Wasserstein algebras).

Application to System Verification and Refinement

In practical software engineering, quantitative equational logic fundamentally changes how we evaluate system specifications and implementations.

Real-Valued Satisfaction

Instead of treating logical satisfaction as a binary state, systems can be evaluated using real-valued modal logics. As shown by Thrane et al. in A Quantitative Characterization of Weighted Kripke Structures in Temporal Logic: Best Paper Award, redefinining satisfaction as a real-valued distance metric ensures that minor perturbations in system parameters result in only small changes to the satisfaction value. This prevents brittle verification outcomes. Under this framework, the metric distance between two systems corresponds directly to the maximum difference in the satisfaction levels of all possible formulas within the logic (Gupta et al. in Approximate reasoning for real-time probabilistic processes).

Quantitative Refinement Distance

When checking if a concrete implementation matches a high-level specification, binary refinement is replaced with a quantitative refinement distance. This metric quantifies the maximum cost or behavioral deviation incurred by an implementation (Chatterjee et al. in Compositional Quantitative Reasoning).

Binary Refinement:       [Specification] <--- (Pass / Fail) --- [Implementation]

Quantitative Distance:   [Specification] <--- (Distance: ε) --- [Implementation]

As explored by Larsen et al. in Quantitative Modal Transition Systems and Bauer et al. in Weighted Modal Transition Systems, this distance bounds how differently the two systems can behave. By using a discounted refinement distance, errors that occur later in an execution sequence can be decayed, allowing practitioners to rank implementations that "almost satisfy" a specification (Fahrenberg et al. in Compositionality for quantitative specifications).

This framework provides a robust mathematical toolkit for modern verification. It has been successfully applied to deduce bisimilarity distances on Markov chains (Bacci et al. in A Complete Quantitative Deduction System for the Bisimilarity Distance on Markov Chains), and traces its roots back to early insights that expectation-based frameworks collapse traditional path quantifiers into a single, continuous numerical value (Huth et al. in Comparing CTL and PCTL on labeled Markov chains). Even early concepts of domain abstraction rely on this core philosophy: grouping elements into equivalence classes to speed up reasoning while explicitly quantifying the "error" introduced by the simplification (Paper 88).

Key Foundational Work

Comparing CTL and PCTL on labeled Markov chains (1998) — contributed 1 concept elements to this direction.
Domain Abstraction and Limited Reasoning (1987) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_quantitative_equational_logic_d0b4a05a,
  title = {quantitative equational logic},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/quantitative-equational-logic/rdr_d0b4a05a112b439eb4cf17d2bf1715e1},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_quantitative_equational_logic_d0b4a05a_v1,
  title = {quantitative equational logic},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/quantitative-equational-logic/rdr_d0b4a05a112b439eb4cf17d2bf1715e1/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake