💻 computer science

Computing Distinguishing Formulae for Threshold-Based Behavioural Distances

This paper presents a unified framework for threshold-based behavioural distances induced by quantitative modalities, demonstrating that distinguishing formulae for both two-valued and quantitative logics can be extracted in polynomial time, a result that yields new efficient algorithms for specific systems such as Markov chains, metric transition systems, and fuzzy transition systems.

Original authors: Jonas Forster, Lutz Schröder, Paul Wild, Barbara König, Pedro Nora

Published 2026-02-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jonas Forster, Lutz Schröder, Paul Wild, Barbara König, Pedro Nora

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to compare two complex machines, like two different self-driving cars or two different AI chatbots. In the old days, computer scientists asked a simple "Yes or No" question: "Are these two machines exactly the same?" If the answer was "No," the comparison stopped there. It didn't tell you how different they were, just that they weren't identical twins.

But in the real world, things are rarely black and white. One car might be 99% similar to the other, while another might be only 50% similar. We need a way to measure that distance.

This paper introduces a new, unified "ruler" for measuring how different complex systems are, and it gives us a fast, efficient way to write a "report card" (a formula) that explains exactly why two systems are different.

Here is the breakdown using everyday analogies:

1. The Problem: The "Fuzzy" Ruler

Think of a Threshold-Based Distance like a "tolerance level" in a factory.

Imagine you are checking if two apples are the same size.
The Old Way (Binary): Is Apple A exactly the same size as Apple B? If Apple A is 1mm bigger, the answer is "No, they are different." That's it.
The New Way (Threshold): We say, "They are 'close enough' if the difference is less than 5mm." If the difference is 2mm, they are "similar." If it's 10mm, they are "very different."

The authors focus on systems where we allow a little bit of error (the threshold, or $\epsilon$ ). They want to know: "How much error do I need to allow before I can say these two systems are effectively the same?"

2. The Tool: The "Magic Lenses" (Predicate Liftings)

To measure these systems, the authors use special tools they call Predicate Liftings.

The Analogy: Imagine you have a black-and-white photo (a simple "Yes/No" fact). You put it through a special lens, and suddenly, it becomes a color photo with shades of gray (a "How much?" fact).
Example: In a probability system (like a coin flip), a simple fact is "The coin landed on Heads." The "lens" turns this into a number: "There is a 70% chance of Heads."
The paper shows that if you have these lenses, you can build a ruler that works for any type of system, whether it's a robot, a network, or a fuzzy logic system.

3. The Game: The "Detective and the Alibi"

To figure out the distance between two systems, the authors invent a game between two characters: Spoiler (the Detective) and Duplicator (the Alibi Maker).

The Setup: Spoiler claims, "These two systems are actually very different!"
The Move: Spoiler points to a specific feature (like "System A has a 90% chance of turning left, but System B only has a 10% chance").
The Defense: Duplicator tries to say, "No, they are still similar within our allowed error margin." Duplicator must find a matching feature in the other system to prove the point.
The Result: If Spoiler can keep finding differences that Duplicator can't explain away, Spoiler wins. The "score" of the game is the distance between the two systems.

The paper proves that this game is a perfect way to measure the distance.

4. The Breakthrough: The "Fast Report Card"

The most exciting part of the paper is the algorithm.

The Old Problem: Usually, when you find a difference between two complex systems, writing down the explanation (the "formula") takes a huge amount of time and creates a document so long it's impossible to read. It's like trying to write a novel to explain why two cars are different.
The New Solution: The authors created a method to generate these explanations quickly (in polynomial time).
The Metaphor: Instead of writing a novel, they generate a concise, bullet-point summary (a "DAG" or Directed Acyclic Graph). It's like a cheat sheet that says: "System A is different because at step 3, it chose 'Left' with 90% confidence, while System B chose 'Right' with 10% confidence."
Why it matters: This allows computers to not only know that two systems are different but to explain why in a way that is fast enough to be used in real-world applications like self-driving cars or secure AI.

5. Real-World Applications

The authors show that this "universal ruler" works for many specific scenarios:

Markov Chains (Probabilistic Systems): Think of a weather forecast. The paper helps measure how different two weather models are, even if they have slightly different probabilities.
Fuzzy Systems: Think of a thermostat that says "It's kind of warm." The paper helps measure how "warm" two different thermostats think the room is.
Metric Systems: Think of a GPS. If one GPS says a turn is 50 meters away and another says 55 meters, the paper helps quantify that difference precisely.

Summary

In short, this paper builds a universal measuring tape for complex, uncertain systems. It proves that we can measure the "distance" between any two systems by playing a simple game of "spot the difference." Most importantly, it provides a fast, efficient algorithm to write a clear, short explanation of exactly why those systems are different, turning a complex mathematical problem into a practical tool for engineers and scientists.

1. Problem Statement

In quantitative systems (e.g., probabilistic, weighted, or fuzzy systems), traditional two-valued behavioral equivalences (like bisimulation) are often too coarse. They cannot capture the "degree" of similarity between states, which is crucial for robustness analysis in fields like machine learning, differential privacy, and mobile security.

While behavioral distances (pseudometrics) offer a finer-grained comparison, existing frameworks often struggle with two specific challenges:

Logical Characterization: Finding modal logics that precisely characterize these distances (i.e., where the logical distance equals the behavioral distance).
Algorithmic Extraction: Efficiently computing distinguishing formulae (formulas that prove two states are far apart) for these distances. While polynomial-time algorithms exist for standard two-valued bisimulation, extending this to quantitative, threshold-based distances has been an open problem, particularly for the Lévy-Prokhorov distance on Markov chains.

The paper addresses the specific class of threshold-based behavioral distances, where the distance between states is defined by the infimum of $\varepsilon$ such that the states are $\varepsilon$ -bisimilar (allowing probability/weight deviations up to $\varepsilon$ ).

2. Methodology

The authors employ Universal Coalgebra to provide a unified framework. Their methodology proceeds through the following steps:

Coalgebraic Modeling: Systems are modeled as $F$ -coalgebras $(X, \xi)$ , where $F$ is a functor representing the system type (e.g., sub-distributions for Markov chains, powersets for transition systems).
2-to-V Predicate Liftings: The framework is parametrized by a set $\Lambda$ of 2-to-V predicate liftings. These lift two-valued predicates ( $A \subseteq X$ ) to quantitative predicates (values in $[0,1]$ ) on the functorial image $FX$. A prime example is the probability operator $P(A)(\mu) = \mu(A)$ .
Threshold-Based Simulations: They define $\varepsilon$ -simulations where the quantitative predicate values of related states are allowed to deviate by at most $\varepsilon$ . The behavioral distance $d_\Lambda$ is the infimum of such $\varepsilon$ .
Lax Extensions: They construct a quantitative lax extension $L_\Lambda$ induced by these liftings, proving that the behavioral distance defined via $\varepsilon$ -simulations coincides with the distance induced by this lax extension (Theorem 3.9).
Sugeno Modalities: To bridge the gap to quantitative logic, they convert the 2-to-V liftings into V-to-V liftings (quantitative modalities) using Sugeno integration. These are termed Sugeno modalities ( $S_\lambda$ $S_{λ}$ ).
- Formula: $S_\lambda(f)(a) = \bigvee_{\varepsilon \in [0,1]} (\varepsilon \wedge \lambda(f_\varepsilon)(a))$ , where $f_\varepsilon$ is the $\varepsilon$ -cut of the quantitative predicate $f$ .
Codensity Games: They introduce a Spoiler-Duplicator game (a codensity game) played on the coalgebras.
- Spoiler tries to demonstrate a deviation $> \varepsilon$ .
- Duplicator tries to maintain $\varepsilon$ -similarity.
- Winning strategies for Spoiler correspond to the existence of distinguishing formulae.

3. Key Contributions

A. Unified Framework for Threshold-Based Distances

The authors establish that a wide range of known behavioral distances (including Lévy-Prokhorov on Markov chains, Hausdorff distances on metric/fuzzy systems) fall under the umbrella of threshold-based distances induced by 2-to-V predicate liftings. They prove that these distances coincide with those induced by specific quantitative lax extensions.

B. Logical Characterizations (Hennessy-Milner Theorems)

They introduce two distinct logics that characterize the behavioral distance $d_\Lambda$ on finitely branching systems:

Two-Valued Logic ( $L_2(\Lambda)$ ): Uses standard boolean connectives and modalities with thresholds. It introduces a notion of "satisfaction up to $\varepsilon$ " ( $x \models_\varepsilon \phi$ $x ⊨_{ε} ϕ$ ), meaning the state satisfies the formula with an error margin of $\varepsilon$ $ε$ .
- Result: $d_\Lambda(x, y) \le \varepsilon$ iff $y$ logically $\varepsilon$ -simulates $x$ .
Quantitative Logic ( $L(S[\Lambda])$ ): Uses the Sugeno modalities and non-expansive propositional operators (truncated addition/subtraction).
- Result: The Sugeno logical distance (supremum of truth-value differences) coincides exactly with the behavioral distance $d_\Lambda$ . This provides a Kantorovich-style characterization for these distances.

C. Polynomial-Time Extraction of Distinguishing Formulae

This is the paper's most significant algorithmic contribution.

Mechanism: They extract distinguishing formulae from Spoiler's winning strategies in the codensity game using dynamic programming.
Complexity:
- The algorithm runs in polynomial time (assuming the underlying predicate liftings are polynomial-time solvable).
- The resulting formulae have quadratic modal rank.
- Crucially, the formulae are represented as Directed Acyclic Graphs (DAGs) with polynomial (specifically quartic) size.
- Note: The tree size of such formulae is known to be exponential in the worst case, but the DAG representation (sharing subformulae) keeps it polynomial.

4. Key Results and Examples

The framework instantiates to several new and known results:

Markov Chains (Lévy-Prokhorov Distance):
- The paper provides the first polynomial-time algorithm to extract distinguishing formulae for the Lévy-Prokhorov distance (also known as $\varepsilon$ -distance) on Markov chains.
- It recovers the result that the "generally" modality (from probabilistic knowledge representation) characterizes this distance.
- It unifies the two-valued logic of Desharnais et al. and the quantitative logic of Wild et al. under one generic extraction method.
Metric Transition Systems:
- Derives polynomial-time extraction for Hausdorff behavioral distances on metric transition systems, recovering and generalizing previous results.
Fuzzy Transition Systems:
- Provides a new characteristic logic and extraction algorithm for fuzzy diamond modalities.
Generative Probabilistic Systems:
- Extends the results to systems with labeled transitions.

5. Significance

Bridging Theory and Practice: The paper moves beyond theoretical existence proofs (which often rely on continuity arguments or infinite enumerations) to provide constructive, efficient algorithms for generating witnesses (formulae) for behavioral distances.
Unification: It demonstrates that diverse behavioral metrics (Lévy-Prokhorov, Hausdorff, fuzzy) are instances of a single coalgebraic mechanism based on threshold-based simulations and Sugeno integration.
Complexity Breakthrough: By achieving polynomial-time extraction for quantitative distances, the authors overcome the barrier that previously made such computations intractable for large systems. This is vital for applications in formal verification, machine learning robustness (e.g., verifying that a model's output distribution doesn't shift too much under perturbation), and differential privacy.
New Logic: The introduction of the Sugeno modality as a computationally tractable alternative to expectation-based modalities (like the Kantorovich metric) offers a new tool for reasoning about vague or probabilistic properties.

In summary, the paper establishes a robust, generic coalgebraic framework that not only characterizes threshold-based behavioral distances logically but also provides the first efficient algorithms to compute the specific logical formulas that certify these distances.