How to Learn Paige–Tarjan Partition Refinement: Blocks, Splitters, Bisimulation, Relational Coarsest Partitions and O(m log n) Engineering

When can two states safely be treated as the same without changing what a system can do? Paige–Tarjan partition refinement answers that question by repeatedly separating states that only looked equivalent because we had not yet asked the right distinguishing question.

This Learning Hall article develops partition refinement from coloured bags of states to bisimulation, stable partitions, efficient splitters and professional model-reduction engineering. It complements the existing DFA Minimization Algorithms learning article. That article owns automata minimisation; this one focuses on the broader relational-coarsest-partition and bisimulation problem for transition systems.

Quick Read

A partition groups states into blocks that are currently considered equivalent.
A splitter exposes a behavioural difference inside a block.
Refinement never merges blocks; it only divides them when evidence requires it.
The process stops when the partition is stable: no permitted splitter can distinguish states still grouped together.
For bisimulation, states in one block must have matching transition behaviour with respect to every block.
Efficient implementations avoid rescanning the whole graph after every split and exploit smaller-half accounting.
In standard finite relational settings, Paige–Tarjan-style refinement can achieve O(m log n) time, where n is the number of states and m the number of transitions.
The professional applications include model checking, behavioural equivalence, quotient construction and state-space reduction.

1. Beginner Level: Start With Bags of States

Imagine six states: A, B, C, D, E and F. Some are marked “accepting” and some “non-accepting”. Before inspecting transitions, a reasonable first partition might be:

{A, B, C, D}   {E, F}

We are not claiming A, B, C and D are truly equivalent. We are saying only that our current evidence does not yet separate them. A partition is therefore a working hypothesis about sameness.

Now suppose A and B can move into {E,F}, but C and D cannot. The block {E,F} acts as a question: “Which states can step into this block?” That question splits {A,B,C,D} into {A,B} and {C,D}. We have refined the hypothesis using observable behaviour.

2. What Is a Partition?

A partition of a set of states is a collection of non-overlapping blocks whose union is the whole state set. Every state belongs to exactly one block. Two states are provisionally equivalent when they share a block.

We begin from an initial partition that already respects distinctions the problem says must never be erased. In a labelled transition system, state labels or observations may determine the starting blocks. In a deterministic automaton, accepting and non-accepting states must start apart.

This is a specification issue, not an implementation detail. If states with different observable labels are placed in the same initial block, later refinement may be solving the wrong equivalence problem.

3. The Notional Machine: Splitters Ask Behavioural Questions

For a directed relation, define the predecessor set of a block S:

pre(S) = { x : x has a transition to some state in S }

Now take another block B. If some members of B are in pre(S) and some are not, S distinguishes them. We split B into:

B ∩ pre(S)
B \ pre(S)

That is the core visual model: keep a set of bags, choose one bag as a splitter, mark the states that can reach it, then cut any mixed bag into marked and unmarked parts.

4. A Small Worked Example

Consider states A, B, C, D, X and Y. X and Y are terminal goal states, so start with:

P = { {A,B,C,D}, {X,Y} }

Suppose A→X, B→Y, C→A and D→B. Using S={X,Y}, the predecessor set among the first block is {A,B}. We therefore refine:

{A,B,C,D}  →  {A,B}  {C,D}

Now {A,B} itself becomes behaviourally meaningful. Since C and D both transition into {A,B}, it does not split {C,D}. If later evidence shows C and D lead into different refined blocks, they will separate then. Refinement is incremental: a distinction becomes visible only after the partition is fine enough to express it.

5. Stability: When Refinement Can Stop

A partition is stable when no relevant splitter can divide any remaining block. Intuitively, members of the same block agree about which blocks they can transition into in the way required by the chosen equivalence.

For strong bisimulation, if p and q are in one block, every transition from p must be matchable by an appropriate transition from q into the same equivalence class, and vice versa. When the partition is stable under the relational refinement condition, each block represents a behavioural equivalence class.

6. Educational Pseudocode

P = initial_partition(states)
work = initial_splitters(P)

while work is not empty:
    S = remove_one_splitter(work)
    marked = predecessors(S)

    for each block B touched by marked:
        left  = B ∩ marked
        right = B \ marked

        if left and right are both non-empty:
            replace B in P by left and right
            update work using the refinement policy

return P

This learner version shows the invariant but hides several performance-critical details. The original Paige–Tarjan relational-coarsest-partition machinery carefully controls which compound blocks and splitters are active. Production implementations also maintain block membership, predecessor lists and counters so that a split touches only affected states and edges.

7. Why “Smaller Half” Matters

A naive algorithm might rescan every edge after every split. That can turn an elegant idea into an expensive implementation. The famous efficiency insight is to organise splitter processing so that expensive work is charged to a piece that is no larger than about half of the block it came from.

A state can move into a successively smaller charged block only O(log n) times. If transition work follows those states, each edge is similarly revisited only logarithmically many times. This accounting pattern is what makes O(m log n) refinement possible in the standard finite relational setting.

The deeper lesson transfers far beyond this algorithm: when repeated splitting seems expensive, ask whether each object can be charged to a component that shrinks geometrically.

8. Correctness: Two Things Must Be Proved

A correctness argument has two sides.

Soundness of splitting: whenever the algorithm separates two states, the chosen behavioural condition genuinely distinguishes them.
Maximality of what remains: when no splitter can refine the partition further, states left together satisfy the intended stable equivalence, and the result is the coarsest such refinement of the initial partition.

Notice the monotonic structure. The algorithm never merges states after separating them. Every step moves from a coarse hypothesis to a finer one. Termination follows because a finite set has only finitely many possible strict splits before every block is a singleton.

9. Paige–Tarjan Versus Hopcroft DFA Minimisation

Both algorithms use partition refinement and efficient splitters, so their surface patterns look related. Their canonical jobs are not identical. Hopcroft’s algorithm is classically presented for deterministic finite automata, using symbols and inverse transitions to refine accepting-state equivalence. Paige–Tarjan develops a more general relational coarsest-partition framework that supports bisimulation-style equivalence on transition systems.

Learning both is useful because it teaches transfer without collapsing distinct problems into one name. The shared idea is “refine only when behaviour forces a distinction”; the exact stability condition and data structures depend on the model.

10. Data Structures for a Professional Implementation

Block membership: each state should know its current block in O(1) time.
Block contents: splitting should move only the states in the smaller or touched part rather than copy entire arrays.
Predecessor adjacency: inverse edges make pre(S) computable from edges entering splitter states.
Counters: transition counts can distinguish how a state connects to candidate splitter pieces without rescanning all of its edges.
Touched-block lists: process only blocks that actually contain marked states.
Work sets: avoid duplicate splitter scheduling and define deterministic processing when reproducibility matters.

Memory layout matters on large graphs. A theoretically optimal implementation that scatters small objects across memory can lose to a simpler contiguous representation on real hardware. Measure both asymptotic work and locality.

11. Common Failure Modes

Wrong initial partition: states with observably different labels are grouped together.
Wrong direction: the implementation uses successors where the refinement rule needs predecessors.
Global rescans: every block or edge is reconsidered after each small split.
Stale block IDs: moved states still point to an obsolete block object.
Duplicate work: the same splitter is queued repeatedly without need.
Simulation confused with bisimulation: one-way matching and two-way behavioural equivalence are different relations.
Unspecified labels: edge labels or action types are ignored even though the semantics require them.
Partial-transition semantics hidden: missing transitions may mean dead-end, failure or an implicit sink; choose explicitly.

12. Testing the Result, Not Just the Code Path

A strong test suite checks mathematical properties of the returned partition.

Every state appears in exactly one output block.
The output refines the initial partition; it never crosses a forbidden initial boundary.
The output is stable under the chosen transition-equivalence rule.
Running refinement again returns the same partition up to block ordering.
For small random graphs, compare against a deliberately slow reference that repeatedly recomputes behavioural signatures until no block changes.
Build the quotient transition system and verify that equivalent states map consistently.

Property-based testing is particularly effective because many bugs preserve the right number of blocks while assigning one or two states incorrectly.

13. Where Professionals Use Partition Refinement

Partition refinement appears in model checking, protocol verification, labelled transition systems, process algebra, state-space quotienting and behavioural equivalence. Shrinking a system to its quotient can make downstream verification dramatically smaller while preserving the observations relevant to the equivalence.

Modern research extends these ideas beyond plain graphs to coalgebraic systems and more general behavioural structures. The transferable insight remains the same: represent the current indistinguishability relation explicitly, discover a witness that breaks one block, and propagate only the consequences that witness creates.

14. A Beginner-to-Professional Learning Ladder

Beginner: colour states by blocks and manually split them using one visible predecessor question.
Intermediate: implement a simple repeated-refinement algorithm and explain what stability means.
Advanced: prove soundness, compare bisimulation with DFA equivalence, and add predecessor lists plus touched-block processing.
Professional: implement efficient work-set accounting, instrument edge visits, support labelled transitions, verify against a slow oracle and benchmark large sparse state spaces.

15. Practice Problems

Given a six-state graph, perform refinement by hand until stable and draw the quotient graph.
Construct two states that have the same out-degree but are not bisimilar.
Write a slow signature-refinement reference algorithm for testing.
Instrument how often each edge is examined in a naive implementation versus a smaller-half implementation.
Add transition labels and explain how the splitter rule must change.
Find an example where the wrong initial partition produces an invalid equivalence.
Compare Paige–Tarjan-style bisimulation refinement with Hopcroft DFA minimisation without treating them as interchangeable.

16. Sources and Further Reading

Final idea: Paige–Tarjan is a lesson in disciplined discrimination. Start with states that might be equivalent, ask only behaviourally legitimate questions, split exactly where the evidence demands it, and stop when no question can reveal a remaining difference. The algorithm becomes professional-grade when that reasoning is preserved while the implementation ensures each new distinction is propagated without repeatedly paying for the whole graph.

Small Group Tutorials