Counterexample for simple parity automaton reduction

Question

I am dealing with deterministic parity automata and state space reduction (not minimization).

If we define $\equiv_L$ to be the equivalence relation that sets two states equal iff starting from those states the automaton recognizes the same $\omega$-language, merging those states is in general not an operation that preserves language. The canonical example is a parity automaton with two states $q_a, q_b$ that moves to $q_a$ whenever reading an $a$ and to $q_b$ whenever reading a $b$. Giving both states a different parity yields a counter example.

Now what if we refine this relation so that $p \sim q$ is true iff $p \equiv_L q$ and in addition the two states have to have the same color assigned to them. I feel like there has to be a counter example but I can't think of one. That is my question; what is a simple counter example that shows that merging states like this can alter the langauge?

(in case it is not clear what I mean by "merging": merging $p$ and $q$ means removing $q$ from the automaton and redirecting all transitions that would move into $q$ to target $p$ instead)

Answer 1

After some thought, I found a counter example. It has four states and there might be one with only three states, but this one works too.

States 1, 2, and 3 are language equivalent. 1 and 3 also have the same color, so they can be merged. If we merge 3 into 1, this is the result:

In the original automaton, $(aab)^\omega$ has the run $(103)^\omega$ which only sees color 1. In the reduced automaton, $(aab)^\omega$ has the run $101(201)^\omega$, which also visits color 0 infinitely often.