In formal verification and concurrency theory, determining whether two systems behave identically has traditionally relied on binary notions of equivalence, such as bisimulation. In a deterministic setting, two states are either equivalent or they are not. However, when dealing with stochastic, fuzzy, or continuous systems, this rigid binary view breaks down. A tiny perturbation in a transition probability makes two otherwise identical states completely non-bisimilar.
To solve this brittleness, researchers introduced quantitative behavioral metrics. These metrics map the difference between states to a continuous scale (typically $[0, 1]$), providing a robust way to measure similarity. Crucially, these distances provide a fundamental bound on the difference in long-run expected rewards or behaviors between two states. Historically, calculating these distances was computationally prohibitive, often requiring exponential-time algorithms. The core insight of this research direction is that quantitative behavioral similarity can be reframed as an optimization problem, allowing complex distance metrics to be computed or approximated in polynomial time.
Reducing Transitions to Linear Programs
The key breakthrough that made quantitative metrics practical was the realization that one-step distance calculations can be reduced to linear programming (LP).
As established by Ritankar S Majumdar et al. and later expanded in the full version by R Majumdar et al., the problem of finding the behavioral distance in Markov Decision Processes (MDPs) and turn-based games can be reduced to a quadratic-size linear programming problem.
To understand why this works, consider the distance between two states as an optimal transport or coupling problem. To find the minimum discrepancy between two probability distributions over next states, we look for a coupling—a joint distribution that matches the marginal transitions of both states while minimizing the expected distance between the destination states. Because the constraints of a coupling are linear, and the objective function (minimizing expected future distance) is also linear, the entire one-step distance characterization can be solved using standard polynomial-time LP solvers.
This framework is highly general. For instance, Oleg Sokolsky et al. leveraged a similar reduction to stochastic games and linear programming to efficiently compute behavioral similarity for graph-based program structures, enabling quantitative malware variant classification.
[State s] ---> Probability Distribution P ──┐
├──> Optimal Coupling (Linear Program) ──> Polynomial-Time Distance
[State t] ---> Probability Distribution Q ──┘
This polynomial-time tractability extends across a wide variety of system semantics:
- Continuous-Time Markov Chains (CTMCs): Earlier formulations suffered from an exponential growth in the number of constraints. However, Giorgio Bacci et al. demonstrated an "on-the-fly" approach showing that the behavioral distance can be characterized by an LP with a polynomial number of constraints relative to the system size.
- Fuzzy Transition Systems: When dealing with fuzzy systems, Taolue Chen 0001 et al. proved that the exact rational values of behavioral distances in discounted systems can be computed in polynomial time relative to the bit-length of the input, ensuring that precision is maintained without an exponential explosion in cost.
Taming the Intractability of Linear-Time Semantics
While computing branching-time metrics (which look at step-by-step tree structures) is polynomial-time solvable via LPs, computing linear-time trace distances (which look at the total probability of generating specific sequences of labels over time) is notoriously NP-hard. This creates a gap: linear-time properties are highly desirable for probabilistic model checking, but exactly computing them is intractable because tracking sequence histories causes an exponential state explosion.
To bypass this complexity, Giorgio Bacci et al. and the authors' subsequent journal work introduced an elegant approximation schema that bridges branching and linear semantics. They formulated a sequence of bounded branching-time pseudometrics called $k$-probabilistic bisimilarities.
Because these $k$-bisimilarity distances only evaluate the system's branching structure up to a finite depth $k$, they forget the exact history path and can be computed efficiently in polynomial time as a series of linear programs. Crucially, the authors proved that this directed sequence forms a net that converges point-wise to the actual linear-time trace distance as $k$ approaches infinity. By computing both lower and upper approximants, this schema dual-bounds the expensive linear-time trace distance, allowing researchers to estimate it with arbitrary precision in polynomial time.
k=1 (Local LP) ──> k=2 (Deeper LP) ──> k=3 ... ──> k=∞ (Target Trace Distance)
└─────────────────── Polynomial-Time Approximants ───────────────────┘ └────── NP-Hard Exact ──────┘
Continuous and Data-Driven Extensions
The underlying philosophy of reducing complex behavioral distances to tractable geometric or optimization primitives has also found utility in continuous control and data-driven systems.
For continuous and hybrid systems, tracking the distance between continuous trajectories is vital. Rupak Majumdar et al. developed the first polynomial-time algorithm for computing the Skorokhod distance between polygonal traces. They achieved this by reducing the problem to computing Fréchet distances between derived curves, resolving a long-standing computational challenge in continuous verification.
In the domain of data-driven control, systems are often analyzed via simplified abstractions. Adrien Banse et al. introduced an efficient algorithm to approximate the Kantorovich metric between Markov chains. Instead of relying on naive, computationally heavy LP formulations, their approach adaptively refines state-space abstractions based on the metric, demonstrating that fast behavioral distance approximations can directly accelerate the synthesis of complex control systems from data.
Key Foundational Work
Algorithms for Game Metrics (2008) — contributed 2 concept elements to this direction.
Simulation-Based Graph Similarity (2006) — contributed 1 concept elements to this direction.