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)

  • $\begingroup$ Sorry if I appear pedantic, does your merging $p$ and $q$ also mean redirecting all transitions that would start from $q$ to from $p$? $\endgroup$
    – John L.
    Dec 4, 2018 at 0:51
  • $\begingroup$ No, you want your automaton to stay deterministic. Outgoing transitions from $q$ simply don't exist anymore. $\endgroup$
    – Andreas T
    Dec 4, 2018 at 8:06

1 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.

enter image description here

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:

enter image description here

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.