💻 computer science

Minimal and Canonical Quotients for Simulation Equivalences

This paper extends results on canonical and minimal quotients to weak simulation equivalence and coupled similarity by presenting abstract procedures for generating unique representatives and state-transition-minimal LTSs, while also proving that the minimization problem for these equivalences is NP-complete.

Original authors: Eduardo Costa Martins, Tim Willemse

Published 2026-07-02

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Eduardo Costa Martins, Tim Willemse

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 have a massive, tangled ball of yarn representing a computer program's behavior. This ball is a "Labelled Transition System" (LTS). It shows every possible move the program can make, every state it can be in, and every action it can take. Often, this ball is huge and full of redundant loops—places where the program does the exact same thing twice, or takes a long, winding path to get somewhere it could have reached instantly.

The goal of this paper is to figure out how to untangle this ball into its smallest, cleanest, and most unique shape without changing what the program actually does. In computer science, we call this process "quotienting" or "minimisation."

Here is the story of what the authors discovered, explained through simple metaphors.

The Two Types of "Simplification"

The authors looked at two specific ways to decide if two programs are "the same" (equivalent):

Weak Simulation: Think of this as checking if one program can mimic another's moves, even if it takes a few extra "silent" steps (like a pause) to get there.
Coupled Similarity: A slightly stricter version where the programs must not only mimic each other but also be able to "catch up" to each other if one gets ahead.

The paper asks two big questions about simplifying these programs:

Canonicity: Is there only one perfect, unique way to shrink the ball? (Like a fingerprint: if you shrink two identical balls, do you get the exact same tiny ball?)
Minimality: Can we shrink the ball to the absolute smallest size possible?

The "Universal" Shrinker (The ∀-Quotient)

First, the authors tried a standard method called the "Universal Quotient." Imagine you have a group of twins in a room. This method says, "If you look identical, sit in the same chair." It merges all identical states into one.

The Result: This works well to remove duplicates. However, it's like merging twins but leaving all their extra, unnecessary clothes on. The resulting ball is smaller, but it's not the smallest it could be. It might still have extra strings of yarn (transitions) that aren't needed.
The Problem: For these specific types of program equivalence, this standard method doesn't always produce a unique shape (canonicity), nor does it always produce the tiniest possible shape (minimality).

The "Desaturation" Trick (Making it Unique)

To get a unique shape (canonical), the authors introduced a new trick called $\tau$ -Desaturation.

The Metaphor: Imagine a program takes a silent step (a $\tau$ -step) to a new room, and then immediately does a visible action (like pressing a button). If the program could have just pressed the button directly from the starting room, why take the silent detour?
The Fix: The authors say, "Cut the silent step. If you were going to press the button after the silence, just press it immediately." They repeat this until no silent detours are left.
The Outcome: Once you remove all these silent detours and merge identical states, you get a shape that is unique. No matter how you start, if you apply this rule, you always end up with the exact same final ball. This solves the "Canonicity" problem.

The "Saturation" Trap (The Hard Part)

Now, the authors wanted to find the smallest possible ball (Minimality). They realized that sometimes, to make the ball smaller, you actually have to add a silent step first, just so you can remove a bunch of other steps later.

The Metaphor: Imagine you have a room with five different doors leading to the same hallway. It's messy. But if you add a secret tunnel (a silent step) from the outside directly into the hallway, suddenly all five doors become redundant and can be locked up and removed. You added one thing to remove five things.
The Problem: The question becomes: Which silent step should you add to get the biggest reduction?
- Should you add a tunnel to Door A?
- Or Door B?
- Or maybe a combination?

The authors discovered that finding the best combination of silent steps to add is incredibly difficult. It's like trying to solve a Set Cover puzzle.

The Set Cover Analogy:
Imagine you have a list of chores (the transitions you want to remove) and a list of tools (the silent steps you can add). Each tool can handle a specific set of chores. You want to pick the smallest number of tools to get all the chores done.

The authors proved that for these specific program types, finding the absolute best set of tools is NP-complete.
What this means: There is no fast, easy algorithm to solve this perfectly for every single case. As the program gets bigger, the time it takes to find the perfect smallest version explodes. It's a "hard" problem in the mathematical sense.

The Solution: A Two-Step Strategy

Since finding the perfect minimum is hard, the authors propose a practical procedure:

Step 1: Get the Unique Shape. First, use the "Desaturation" trick to get the unique, canonical ball. This is fast and easy.
Step 2: Try to Shrink It Further. Then, use a "Set Cover" solver (a specialized computer tool designed for hard puzzles) to see if you can add a few silent steps to remove even more clutter.

They acknowledge that while this second step is computationally heavy, the "puzzles" (the set cover instances) generated by real programs are usually small enough that modern computers can handle them.

Summary of Findings

Unique Shape: Yes, there is a way to turn any of these programs into a single, unique, standard shape (Canonical).
Smallest Shape: Yes, there is a way to make them as small as possible (Minimal).
The Catch: While getting the unique shape is easy, finding the smallest shape is mathematically very hard (NP-complete). It's like the difference between organizing a closet neatly (easy) and finding the absolute most efficient way to pack a suitcase for a trip (very hard).
The Method: You can get a good result by first organizing it neatly, and then using a smart solver to see if you can pack it even tighter.

The paper concludes that while we can always find a standard version of these systems, the quest for the absolute smallest version is a complex challenge that requires advanced puzzle-solving techniques, not just simple rules.

Technical Summary: Minimal and Canonical Quotients for Simulation Equivalences

Problem Statement

Labelled Transition Systems (LTSs) serve as the foundational semantic model for various higher-level specification languages. A common technique for managing the state space explosion problem is quotienting, which merges equivalent states to produce a smaller, semantically equivalent system. While quotienting functions and their properties (canonicity and minimality) are well-established for strong bisimilarity, branching bisimilarity, and trace equivalence, their behavior for weak simulation equivalence and coupled similarity remains under-explored.

Existing results for other equivalences show varying degrees of success:

For bisimilarity, quotients are canonical (unique up to isomorphism) and minimal.
For trace equivalence, minimal quotients may not be unique, and computing them is PSPACE-complete.
For weak simulation and coupled similarity, it is unknown whether canonical or minimal quotients exist, nor is the complexity of computing them established.

This paper investigates the existence of canonical and minimal quotients for weak simulation equivalence ( $\equiv_S$ ) and coupled similarity ( $\equiv_{CS}$ ), and analyzes the computational complexity of finding them.

Methodology

The authors develop abstract procedures to transform an arbitrary LTS into a representative of its equivalence class. The methodology relies on a sequence of transformations based on the properties of simulation preorders and specific $\tau$ -laws (axioms governing unobservable actions).

1. Universal Quotient and Redundancy Removal

The process begins with the $\forall$ -quotient, which merges all equivalent states. However, this alone is insufficient as it may introduce "inert" transitions (transitions between equivalent states) and "duplicate" transitions.

Covered Transitions: The authors generalize the notion of duplicate transitions to covered transitions. A transition $p \xrightarrow{\alpha} q$ is covered if there exists another transition $p' \xrightarrow{\alpha} q'$ such that $p$ can reach $p'$ via $\tau$ -steps and $q$ is simulated by $q'$ ( $q \sqsubseteq_x q'$ ).
Removing covered transitions preserves equivalence and reduces the state space, but the resulting LTS is neither necessarily canonical nor minimal.

2. $\tau$ -Desaturation (For Canonicity)

To achieve canonicity, the paper introduces $\tau$ -desaturation, based on the axioms $\tau.x = x$ and $\tau.(\tau.x + y) = \tau.x + y$ .

Operation: If a state $p$ has a $\tau$ -transition to $q$ ( $p \xrightarrow{\tau} q$ ), the transition is removed, and $p$ is "saturated" with all outgoing transitions of $q$ . For coupled similarity, this requires $q$ to have an outgoing $\tau$ -transition.
Effect: This transformation eliminates consecutive $\tau$ -transitions and reduces incoming transitions to states. Repeated application terminates, yielding a desaturated LTS.
Result: By combining the $\forall$ -quotient, $\tau$ -desaturation, removal of covered transitions, and removal of unreachable states, the authors define a reduced LTS. They prove that any two reduced LTSs that are equivalent are isomorphic, thereby establishing the existence of a canonical quotient.

3. $\tau$ -Saturation (For Minimality)

To achieve minimality, the authors introduce the inverse operation: $\tau$ -saturation.

Operation: If $q \sqsubseteq_x p$ , a $\tau$ -transition $p \xrightarrow{\tau} q$ can be added. This may render existing transitions "coverable," allowing them to be removed.
Optimization Challenge: The choice of which $\tau$ -transitions to add is non-deterministic. Different choices lead to different reductions. The problem of selecting the optimal set of $\tau$ -saturation steps to maximize reduction is shown to be equivalent to the Set Cover Problem.
Algorithm: The minimal quotient procedure computes the canonical quotient first, then identifies "coverable" transitions for each state. It solves a Set Cover instance for each state to determine the minimal set of $\tau$ -transitions to add, which subsequently allows for the removal of the maximum number of other transitions.

Key Contributions and Results

1. Existence of Canonical Quotients

The paper proves that for both weak simulation equivalence and coupled similarity, a canonical quotient exists.

Theorem 4.4: Two reduced LTSs (desaturated, no covered transitions, no unreachable states, no inert transitions, no equivalent states) are equivalent if and only if they are isomorphic.
Algorithm 1: A polynomial-time procedure is provided to compute this canonical quotient.

2. Complexity of Minimal Quotients

The paper establishes that computing a minimal quotient (one with the lexicographically smallest number of states and transitions) is NP-complete.

Theorem 5.5: Minimisation with respect to $\equiv_x$ is NP-hard. This is proven via a reduction from the Set Cover Problem.
Implication: Unlike bisimilarity minimization (which is polynomial), finding the absolute smallest equivalent LTS for simulation equivalences is computationally intractable in the general case.
Algorithm 2: A procedure is described that computes a minimal quotient by leveraging an oracle for the Set Cover Problem. While the algorithm itself is not polynomial-time (due to the NP-hard subproblem), it allows the use of state-of-the-art Set Cover solvers. The instances generated for these solvers are typically small (bounded by the out-degree of states).

3. Distinction from Bisimilarity

The results highlight a fundamental divergence from bisimilarity:

For bisimilarity, the minimal quotient is unique and computable in polynomial time.
For simulation equivalences, minimal quotients may not be unique (multiple non-isomorphic minimal LTSs can exist for the same equivalence class), and finding one is NP-complete.

Significance and Claims

The paper claims to extend the theoretical understanding of quotienting beyond the well-studied bisimulation and trace equivalences.

Generalization: The approach generalizes the concept of "duplicate transitions" and utilizes $\tau$ -laws specific to simulation preorders to derive canonical forms.
Practicality: While finding the absolute minimal quotient is NP-complete, the proposed method allows practitioners to leverage efficient Set Cover solvers to achieve significant reductions in state space, as the specific instances arising from LTS minimization are often small.
Modesty: The authors explicitly note that their results rely on the specific $\tau$ -laws of weak simulation and coupled similarity. They do not claim these results generalize to the entire linear time-branching time spectrum, suggesting that different equivalences may require distinct $\tau$ -laws and transformation strategies.

In conclusion, the paper provides the first abstract procedures for obtaining both canonical and minimal quotients for weak simulation and coupled similarity, characterizing the former as polynomial-time computable and the latter as NP-complete.