💻 computer science

A Diagrammatic Axiomatisation of Behavioural Distance of Nondeterministic Processes

This paper presents a sound and complete diagrammatic axiomatisation of behavioural distance for nondeterministic processes using Milner's charts and string diagrams, offering a variable-free, compositional framework that shifts focus from language equivalence to bisimilarity.

Original authors: Wojciech Różowski, Robin Piedeleu, Alexandra Silva, Fabio Zanasi

Published 2026-05-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Wojciech Różowski, Robin Piedeleu, Alexandra Silva, Fabio Zanasi

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

The Big Picture: Measuring How "Different" Two Machines Are

Imagine you have two robots. In the old days of computer science, we only asked a simple question: "Are these two robots exactly the same?" If they were, great. If not, they were considered completely different. It was a "yes or no" answer.

But in the real world, things are rarely perfect. Maybe Robot A takes one extra step to turn left, or Robot B pauses for a split second before speaking. They aren't exactly the same, but they are also not totally different. They are close.

This paper introduces a way to measure how close two complex, unpredictable computer processes are. Instead of a simple "same/different" switch, the authors create a ruler that measures the "distance" between them.

The Problem: The "Choose Your Own Adventure" Book

The specific type of computer process the authors study is called a Nondeterministic Process. Think of this like a "Choose Your Own Adventure" book where the story can branch in many directions at once.

Deterministic: You read a page, and there is only one next page.
Nondeterministic: You read a page, and there are three possible next pages, and the story could go down any of them.

When you have two of these branching storybooks, comparing them is hard. If they both have a "dead end" (a place where the story stops) at different points, how far apart are they?

The Solution: String Diagrams (The "Flowchart" Language)

To solve this, the authors use a special language called String Diagrams.

The Analogy: Imagine a flowchart or a circuit board. You have wires coming in, boxes in the middle (which do things), and wires going out.
Why use them? Traditional math for these processes uses variables and complex text (like algebra). String diagrams are visual. They look like the actual flow of the process.
- A box is an action (like "press a button").
- A wire is the flow of information.
- Crossing wires means swapping things around.
- Loops mean the process repeats itself (recursion).

The authors argue that drawing these diagrams is much easier and more intuitive than writing out complex equations, especially when you want to prove things about them.

The Core Innovation: The "Distance Ruler"

The paper's main achievement is creating a set of rules (axioms) that let you calculate the distance between two diagrams without actually running the computers.

Think of it like a mathematical recipe for measuring difference:

The Zero Point: If two diagrams are identical (or behave exactly the same), their distance is 0.
The Max Point: If they are completely unrelated, the distance is 1.
The Halving Rule: This is the clever part. If two processes are different, but you can make them look the same by adding one more "step" (like pressing a button) to both, the distance between them is half the distance of what comes next.
- Analogy: Imagine two runners. If they are currently at the same spot, distance is 0. If one is one step ahead, they are "close." If one is two steps ahead, they are "less close." The math in the paper says: Every time you add a step to the beginning of the process, the "distance" between the two processes gets cut in half.

How They Proved It Works

The authors didn't just guess these rules; they proved two critical things:

Soundness (The Rules Don't Lie): If their rules say two diagrams are "distance 0.25" apart, they actually are 0.25 apart. The math holds up.
Completeness (The Rules Catch Everything): If two diagrams are actually 0.25 apart, the rules can find that number. There are no hidden distances the rules miss.

They did this by showing that any complex diagram can be broken down into a standard "normal form" (like simplifying a fraction). Once simplified, they could use a mathematical technique called fixpoints (repeating a calculation until it stops changing) to measure the exact distance.

The "Unfolding" Trick

One of the paper's key metaphors is unfolding.
Imagine a tangled ball of yarn (a complex process with loops). The authors show that you can "unfold" this ball into a long, straight line (a tree structure).

Once unfolded, you can see exactly where the two processes diverge.
If they diverge after 2 steps, the distance is $1/4$ (because $1/2 \times 1/2$ ).
If they diverge after 3 steps, the distance is $1/8$ .

The paper proves that you can do this "unfolding" and measuring entirely within the visual language of the string diagrams, without needing to translate them into messy text code first.

Summary

In short, this paper gives computer scientists a visual toolkit to measure how similar or different two unpredictable computer programs are.

Old way: "Are they the same? Yes/No."
New way: "How far apart are they? Here is a ruler, and here are the rules to measure it using pictures."

This is a foundational step. It doesn't build a specific app or fix a bug today, but it provides the mathematical foundation (the ruler and the rules) that future engineers can use to build better, more reliable systems that handle uncertainty and error gracefully.

1. Problem Statement

The paper addresses the challenge of quantitatively comparing the behaviors of nondeterministic processes.

Context: Traditional process algebra and automata theory rely on Boolean notions of equivalence (e.g., bisimilarity, language equivalence). While useful, these are often too rigid for modern systems involving probabilistic or quantitative aspects, where one needs to measure how far apart two behaviors are rather than just if they are identical.
Specific Gap: While behavioral distances have been studied for probabilistic systems and deterministic automata (DFA), there is a lack of a sound and complete axiomatic framework for nondeterministic processes (specifically Milner's charts).
Challenge: Nondeterminism shifts the semantic focus from language equivalence to bisimilarity. Existing algebraic syntaxes (like regular expressions with binders) struggle to capture these behaviors compositionally without complex substitution mechanisms. Furthermore, extending quantitative reasoning to nondeterministic systems requires handling the "Hausdorff lifting" of metrics, which is technically difficult to axiomatize.

2. Methodology

The authors adopt a diagrammatic approach using string diagrams (the graphical language of symmetric monoidal categories) to represent and reason about process behaviors.

Semantic Model (Charts): The paper focuses on Milner's charts, which generalize finite-state nondeterministic automata (NFA) by replacing acceptance states with variable outputs. The semantics are defined over a category of regular behaviors ( $\Omega$ ), equipped with a pseudometric structure.
Metric Definition: The behavioral distance is defined via a coalgebraic framework. It utilizes:
1. Transition Lifting: Lifting a metric on states to a metric on transitions (labelled edges and variable outputs).
2. Hausdorff Lifting: Lifting the metric to sets of transitions (to handle nondeterminism).
3. Fixpoint Characterization: The distance is the least fixpoint of a monotone operator on the lattice of pseudometrics. It is concretely characterized by the stratification of bisimilarity (Hennessy-Milner logic), where the distance is $2^{-n}$ if two processes are bisimilar up to depth $n$ but not $n+1$ .
Syntax (String Diagrams): The authors use string diagrams as the syntax. This choice offers:
- Variable-free representation: Recursion is handled via feedback loops (traces) rather than explicit binders and substitution.
- Compositional Semantics: The diagrams map naturally to the categorical structure of regular behaviors.
- Int Construction: To handle bidirectional data flow (inputs/outputs) and feedback loops, the authors utilize the Int construction to transform the traced monoidal category of behaviors into a compact closed category, allowing for local wire bending.

3. Key Contributions

A. A Quantitative Inference System

The paper proposes a set of quantitative equational rules (inference system) to derive bounds on behavioral distances ( $s \equiv_\epsilon t$ ).

Standard Metric Rules: Reflexivity, Symmetry, Triangle Inequality, and a "Continuity" rule (if $s \equiv_{\epsilon'} t$ for all $\epsilon' > \epsilon$ , then $s \equiv_\epsilon t$ ).
Compositional Rules: Rules for sequential composition and parallel composition (tensor) that preserve non-expansiveness.
Domain-Specific Rules:
- (Pref): Prefixing with an action $a$ halves the distance ( $d(a.s, a.t) = \frac{1}{2}d(s, t)$ ). This captures the intuition that distinguishing two processes takes one more step.
- (Codel): A diagram with no initial state (deadlock) is at distance 0 from the empty chart.
- Equational Axioms: A set of axioms (A1-B11) capturing strong bisimilarity (distance 0), including laws for nondeterministic choice, variable merging, and recursion (Conway theory axioms).

B. Soundness and Completeness

The central technical achievement is the proof that the inference system is both sound and complete.

Soundness (Theorem 16): Every derivable quantitative equation $f \equiv_\epsilon g$ is valid (i.e., the actual behavioral distance $d(\llbracket f \rrbracket, \llbracket g \rrbracket) \leq \epsilon$ ).
Completeness (Theorem 31): If the behavioral distance between two diagrams is $\leq \epsilon$ $\leq ϵ$ , then the equation $f \equiv_\epsilon g$ $f \equiv_{ϵ} g$ is derivable using the proposed rules.
- Proof Strategy: The completeness proof involves transforming arbitrary diagrams into a normal form (representing a finite prechart). It then simulates the calculation of the Hausdorff lifting and the fixpoint iteration (Kleene's theorem) syntactically using the inference rules. The Continuity (Cont) rule is crucial for closing the gap between the syntactic approximation and the exact limit.

C. Categorical Structure

The paper establishes that the category of regular behaviors ( $\text{RegBeh}$ ) is a Conway Theory (a specific type of traced monoidal category) and that the pseudometric structure makes it an enriched category over the category of pseudometric spaces ( $\text{PMet}$ ). This ensures that all categorical operations (composition, tensor, trace/dagger) are non-expansive.

4. Results

Formal Characterization: The paper provides the first complete axiomatization of behavioral distance for Milner's charts (nondeterministic processes with outputs).
Syntactic Simulation of Metrics: The authors demonstrate that complex metric calculations, such as the Hausdorff distance between sets of transitions, can be simulated purely through syntactic manipulation of string diagrams.
Example Application: The paper includes a detailed derivation showing how to prove that two specific charts (one with a deadlock after two 'a's, the other with infinite 'a's) are at a distance of exactly $1/4$ . This is achieved by unrolling the recursion and applying the (Pref) rule twice.

5. Significance

Bridging Theory and Practice: By moving from Boolean equivalence to quantitative distance, the work enables more nuanced analysis of systems where "almost equivalent" is a meaningful concept (e.g., in verification of approximate systems or probabilistic systems).
Unified Diagrammatic Framework: The use of string diagrams avoids the complexity of variable binding and substitution found in traditional process algebras. This suggests a path toward a unified framework for axiomatizing equivalences and distances across various computational models (deterministic, nondeterministic, probabilistic, weighted).
Foundation for Future Work: The paper lays the groundwork for extending these results to weighted transition systems and probabilistic automata, where behavioral distances are even more critical. It also suggests potential applications in reasoning about decompilation algorithms and Guarded Kleene Algebra with Tests (GKAT).
Theoretical Advancement: It connects coalgebraic behavioral metrics, quantitative equational logic, and diagrammatic algebra, showing how these fields can be integrated to solve long-standing problems in process theory.

In summary, this paper successfully translates the abstract, coalgebraic definition of behavioral distance for nondeterministic processes into a concrete, diagrammatic, and fully axiomatized calculus, proving that quantitative reasoning about process behavior can be performed entirely through syntactic manipulation of string diagrams.