My question is related to the seminal paper On $\omega$-regular sets by K. Wagner, which introduced a hierarchy which is now know as the Wagner- (or Wadge-) hierarchy of $\omega$-regular sets.

In this paper he introduces several invariants which could be computed from a given automaton for some $\omega$-language, and then he proceeds that these are invariants of the language, i.e. independent of the specific automaton used to compute them. In the course of this proof a special relation is introduced, and on the properties of this relation, for which a proof is not given in the paper, I have some questions.

I introduce all definitions. All automata considered are supposed to be deterministic. For a given deterministic automaton $\mathcal A = (X, Q, f, q_0, \mathcal F)$ and $\mathcal F \subseteq \mathcal P(Q)$ (i.e. a table of subsets of states, see Mueller acceptance) we write $T(\mathcal A)$ for the set of all words such that there exists some $Z \in \mathcal F$ such that the states that are traversed infinitely often are precisely the states in $Z$. Now define $$ M(\mathcal A) = \{ Z' \mid T((X, Q, f, q_0, \{Z'\})) \ne \emptyset \} $$ i.e. the sets $Z'$ such that some word loops infinitely often through all the states in $Z'$. Then define $$ M^+(\mathcal A) := M(\mathcal A) \cap \mathcal F, \quad M^-(\mathcal A) := M(\mathcal A) \cap \overline{\mathcal F} $$ and inductively: \begin{align*} M_1^+(\mathcal A) & := M^+(\mathcal A), \\ M_1^-(\mathcal A) & := M^-(\mathcal A), \\ M_{2m}^+(\mathcal A) & := \{ Z' \mid Z' \in M^-(\mathcal A) \land \exists Z''( Z'' \in M_{2m-1}^+ \land Z'' \subseteq Z') \}, \\ M_{2m}^-(\mathcal A) & := \{ Z' \mid Z' \in M^+(\mathcal A) \land \exists Z''( Z'' \in M_{2m-1}^- \land Z'' \subseteq Z') \}, \\ M_{2m+1}^+(\mathcal A) & := \{ Z' \mid Z' \in M^+(\mathcal A) \land \exists Z''( Z'' \in M_{2m}^+ \land Z'' \subseteq Z') \}, \\ M_{2m+1}^-(\mathcal A) & := \{ Z' \mid Z' \in M^-(\mathcal A) \land \exists Z''( Z'' \in M_{2m}^- \land Z'' \subseteq Z') \}. \\ \end{align*} and \begin{align*} m^+(\mathcal A) & := \max( \{0\} \cup \{ m \mid M_m^+(\mathcal A) \ne \emptyset )\}) \\ m^-(\mathcal A) & := \max( \{0\} \cup \{m \mid M_m^-(\mathcal A) \ne \emptyset )\}) \end{align*} Set $m := \max(m^+(\mathcal A), m^-(\mathcal A))$ and for $Z', Z''$ write $Z'' \to Z'$ iff some state from $Z'$ is reachable from some state of $Z''$ and define further \begin{align*} N_1^+(\mathcal A) & := M_m^+(\mathcal A) \\ N_1^-(\mathcal A) & := M_m^-(\mathcal A) \\ N_{2n}^+(\mathcal A) & := \{ Z' \mid Z' \in M_m^-(\mathcal A) \land \exists Z''( Z'' \in N_{2n-1}^+(\mathcal A) \land Z'' \to Z' \}) \\ N_{2n}^-(\mathcal A) & := \{ Z' \mid Z' \in M_m^+(\mathcal A) \land \exists Z''( Z'' \in N_{2n-1}^-(\mathcal A) \land Z'' \to Z' \}) \\ N_{2n+1}^+(\mathcal A) & := \{ Z' \mid Z' \in M_m^+(\mathcal A) \land \exists Z''( Z'' \in N_{2n}^+(\mathcal A) \land Z'' \to Z' \}) \\ N_{2n+1}^-(\mathcal A) & := \{ Z' \mid Z' \in M_m^-(\mathcal A) \land \exists Z''( Z'' \in N_{2n}^-(\mathcal A) \land Z'' \to Z' \}). \\ \end{align*} and then similar \begin{align*} n^+(\mathcal A) := \max(\{0\} \cup \{n \mid N_n^+(\mathcal A) \ne \emptyset \}) \\ n^-(\mathcal A) := \max(\{0\} \cup \{n \mid N_n^-(\mathcal A) \ne \emptyset \}). \end{align*} Now define the relation:

$A \le B$ iff there are $\omega$-DFA's $\mathcal A, \mathcal B$ accepting $A$ and $B$ and such that \begin{align*} \max(m^+(\mathcal A), m^-(\mathcal A)) & < \max(m^+(\mathcal B), m^-(\mathcal B)) \quad \mbox{or}\quad \\ \max(m^+(\mathcal A), m^-(\mathcal A)) & = \max(m^+(\mathcal B), m^-(\mathcal B)), n^+(\mathcal A) \le n^+(\mathcal B) \mbox{ and } n^-(\mathcal A) \le n^-(\mathcal B) \end{align*}

and then the claim is, that

The relation $\le$ is reflexive and transitive.

But I do not see it, as if $A \le B$, $B \le C$ then we have automata $\mathcal A, \mathcal B, \mathcal B'$ and $\mathcal C$ for $A,B$ and $C$ and such that among $\mathcal A$ and $\mathcal B$ and $\mathcal B'$ and $\mathcal C$ hold the relations as written above, but depending on what values $m$ takes for the different automata, for example if \begin{align*} m_{\mathcal A} & = 5 \\ m_{\mathcal B} & = 8 \\ m_{\mathcal B'} & = 3 \\ m_{\mathcal C} & = 4 \end{align*} then we would have $A \le B, B \le C$ but I do not see that we would have $A \le C$ (contrary the above numbers give $A \ge C$, but we need to have other automata such that $A \le C$).

So does anybody sees why the relation should be transitive?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.