3
$\begingroup$

Deterministic parity automata $(Q, \Sigma, q_0, \Delta, c)$ are powerful enough to recognize all $\omega$-regular languages. However, the number of priorities they require for a language can become arbitrarily high. For example, the languages $L_{i,j} = \{ \alpha \in \{i, \dots, j\}^\omega \mid \text{The highest number occurring infinitely often in } \alpha \text{ is even} \}$ require at least $j-i+1$ priorities. I was not able to prove this theorem so far by myself, in particular I am stuck at the case that the automaton uses exactly the priorities from $i+1$ to $j$. I could not lead this assumption to a contradiction.

Any help or link to a paper would be appreciated.

$\endgroup$

1 Answer 1

5
$\begingroup$

Take a look at the following paper: Relating hierarchies of word and tree automata. They cite the result you are interested in.

As a more concrete answer, consider the following argument: let's look at the language $M_n=\{w\in \{0,...,n\}^\omega: \limsup w_i \text{ is even}\}$ (the same as your language with $i=0$), and assume it has a parity automaton $A$ with ranks $1,...,n+1$ (note that proving it doesn't have a parity automaton with ranks $1,...,n$ is not enough, as it's still possible for it to have ranks $0,...,n-1$).

We will construct a word that is accepted by $A$, but is not in the language (or vice-versa). Denote by $k$ the number of states in $A$. Consider the run of $A$ on the word $0^\omega$. It's accepting, so the limsup degree is even, and so at least $2$. Moreover, it must occur during the first $k$ steps, otherwise, since $A$ is deterministic, we have a non-accepting cycle. In addition, this is true for every $0^k$ infix of any word.

Now, consider the word $(0^k1)^\omega$. This word is not accepted, so the limsup degree is odd, but must be at least 3, since the $0^k$ infixes induce the degree $2$. Finally, this odd degree must occur within the first $k$ cycles of $0^k1$, for similar reasons as above.

We can repeat these alternating examples, constructing a word of the form $(0^k1)^k2$, and so on, with each word requiring a higher degree. However, since we only have degrees $1,...,n+1$, then eventually we will have a word that uses the letters $0,...,n-1$, whose limsup degree is $n+1$. From there, continuing this construction will still leave the limsup degree $n+1$, but will change the word from accepted to non-accepted, or vice-versa. In either case, the automaton fails to recognize the language.

$\endgroup$
4
  • 1
    $\begingroup$ I do not see how the "Flower Lemma" helps me with my proof. It seems to me like the two theorems 20 and 21 in that paper just refer to other works, none of which I can find online. $\endgroup$
    – Andreas T
    Aug 22, 2015 at 22:42
  • $\begingroup$ You are right, the flower lemma doesn't help here. I changed the answer to include a concrete proof. $\endgroup$
    – Shaull
    Aug 23, 2015 at 4:30
  • $\begingroup$ Thank you, for some reason I did not think of repeating the word k times, even though I used that strategy many other times. Your answer helped improve and shorten my proof a lot. $\endgroup$
    – Andreas T
    Aug 23, 2015 at 13:59
  • $\begingroup$ I should mention that this technique is loosely based on the Flower Lemma, since this word is a witness for the existence of a flower, in a way. $\endgroup$
    – Shaull
    Aug 23, 2015 at 14:49

Your Answer

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

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