Help with understanding Hopcroft's algorithm

So I wrote an implementation of Hopcroft's algorithm. While testing, I discovered that it would sometimes produce an automaton that wasn't equivalent to the original. At first, I figured it must be a bug in my code, but after going over the algorithm by hand with a small example, it seems to be a bug in my understanding of the algorithm. Can someone help me correct my understanding?

Here is the algorithm, copied from the paper "Re-describing and algorithm by Hopcroft" by Knuutila. (This version differs a little from the one on Wikipedia, but I have essentially the same problem with that one too.)

let P = {F, F^c}, where F is the set of accepting states
let W = {(F, x) for every x in the alphabet}
while W is non-empty:
    remove an arbitrary element (A, x) from W
    let X be the set of states that move into A on input x
    for every Y in P that intersects non-trivially with X:
        replace Y in P by (Y intersect X) and Y \ X
        for every symbol x:
            if (Y, x) in W:
                replace (Y, x) in W by (Y intersect X, x) and (Y \ X, x)
            else
                add either (Y intersect X, x) or (Y \ X, x) to W
return P

Note that there are two sources of non-determinism in this algorithm: we can remove an arbitrary element from W, and if (Y, x) is not in W then we have a choice as to whether to add (Y intersect X, x) or (Y \ X, x). Unless I have misunderstood something, the algorithm is supposed to be correct no matter what choices we make.

Now, here is my example:

The alphabet is {a, b, c} and the only accepting state is 4, so we start the algorithm with P = 0123|4 and W = {(4, a), (4, b), (4, c)}.

In the first round, suppose we choose (4, b) as our arbitrary element of W. Nothing moves to 4 on input b, so the inner loop is empty. We get back to the outer loop with P=0123|4 and W = {(4, a), (4, c)}.

Next, suppose we choose (4, c). Then X = 12, which intersects non-trivially with 0123, splitting it into 03|12. Since no (0123,

Hopcroft's algorithm works well on complete DFA. (ie. for $M=\{Q,\Sigma,\delta,q_0,F\}$, the transition function $\delta:Q\times\Sigma\to Q$ is a total function).

For incomplete DFA with partial state transition function $\delta$. You can always convert it to complete DFA $M'=\{Q',\Sigma,\delta',q_0,F\}$ where $$Q'=Q\cup\{q_{err}\}$$ and $\delta'$ extends $\delta$ by define $\delta_a(q)=q_{err}$ for all undefined $\delta_a(q), \delta_a\in\delta,q\in Q\cup\{q_{err}\}$.

StackExchange Computer Science Q#47061, answer score: 3