3
$\begingroup$

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?

$\endgroup$

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.