Jacques Duparc
email: jacques.duparc@unil.ch

Alessandro Facchini
email: alessandro.facchini@unil.ch

The Topological Complexity of Models of the µ-Calculus On The Alternation Free Fragment and Beyond

Keywords: µ-calculus, Wadge games, topological complexity, parity games, alternating tree automata, descriptive set theory

Recently Murlak and one of the authors have shown that the family of trees recognized by weak alternating automata (or equivalently, the family of tree models of the alternation free fragment of the modal µcalculus) is closed under three set theoretic operations that corresponds to sum, multiplication by ordinals < ω ω and pseudo exponentiation with the base ω1 of the Wadge degree. Moreover they have conjectured that the height of this hierarchy is exactly ε0. We make a first step towards the proof of this conjecture by showing that there is no set definable by an alternation free µ-formula in between the levels ω ω and ω1 of the Wadge Hierarchy of Borel Sets. However, very little is known about the Wadge hierarchy for the full µ-calculus, the problem being that most of the sets definable by a µ-formula are even not Borel. We make a first step in this direction by introducing the Wadge hierarchy extending the one for the alternating free fragment with an action given by a difference of two Π 1 1 complete sets.

Introduction

A natural measure of complexity for the propositional modal µ-calculus is the alternation depth of a formula: the number of non-trivial nestings of alternating least and greatest fixpoints. By a result of Bradfield [START_REF] Bradfield | The Modal µ-Calculus Alternation Hierarchy is Strict[END_REF][START_REF] Bradfield | Simplifying the Modal µ-Calculus Alternation Hierarchy[END_REF], it is well known that the fixpoint alternation depth hierarchy is strict. Subsequently, Arnold nicely showed in [START_REF] Arnold | The µ-Calculus Alternation-Depth Hierarchy is Strict on Binary Trees[END_REF] that the hierarchy is also strict over binary trees. The µ-calculus is very strongly related to infinite games and automata theory. On one hand the evaluation games for this logic are parity games. On the other hand, from the automata theory point of view, over trees a µ-formula corresponds to an alternating tree automaton. Given these correlations, it is not surprising that the levels of the hierarchy of Mostowski indices coincide with the ones of the alternation depth hierarchy. From this fact, Bradfield's result implies the strictness of the hierarchy of Mostowski indices for alternating tree automata.

If we consider sets of models of µ-formulae as sets of infinite trees, from a set-theoretical point of view, these are sets of reals. It is therefore very natural to relate the logical complexity of a µ-formula to the topological complexity of its set of models. However those sets of reals are much more complicated than languages recognized by usual automata or even tree automata. Sets of models of µ-formulae are ∆ 1 2 sets, which correspond to sets being both Σ 1 2 and Π 1 2 . Even if this is simply the second projective class, it is by far much less understood that the first one: the class of ∆ 1 1 sets. Indeed, by a well known theorem of Suslin, Borel sets correspond to ∆ 1 1 sets, which were set up by Baire in a nice hierarchy as soon as they were introduced. Nevertheless such a natural hierarchy for ∆ 1 2 sets still remains an open problem (even under determinacy). However there is a natural hierarchy for ∆ 1 2 sets : the Wadge hierarchy, induced by an infinite two-player game which yields under determinacy a well-founded, extremely fine, pre-ordering. Unfortunately there is yet no description of this ∆ 1 2 Wadge hierarchy. This paper makes a first, very little, step towards the study of the connections between the fixpoint alternation depth hierarchy, or the hierarchy of Mostowski indices, and the Wadge hierarchy for ∆ 1 2 sets. In the first part of the paper, we extend the set theoretical operations defined in terms of alternating tree automata presented first in [START_REF] Duparc | On the Topological Complexity of Weakly Recognizable Tree Languages[END_REF] by introducing the operation given by an action of a recognizable topological property -even a non Borel one -over a class of trees. In [START_REF] Duparc | On the Topological Complexity of Weakly Recognizable Tree Languages[END_REF], the authors considered properties recognizable by weak alternating tree automata, or equivalently by alternation free formulae. In this way they proved that the family of trees recognized by wak alternating automata is closed under three set theoretic operations that corresponds to sum, multiplication by ordnals < ω ω and pseudo exponentiation with the base ω 1 of the Wadge degree. They then conjectured that the height of this hierarchy is exactly ε 0 . We make a first step towards the proof of this conjecture by showing that there is no weakly recognizable set in between the levels ω ω and ω 1 of the Wadge Hierarchy of Borel Sets

In the final part of the paper we make a first step towards the description of the Wadge hierarchy for the full modal µ-calculus by introducing the Wadge hierarchy extending the one for weak alternating tree automata with the help of a sort of action of a difference of two Π 1 1 complete sets.

Preliminaries

Tree Automata

Let W be a non empty alphabet. A tree over Σ is a partial function t : W * → Σ with a prefix closed domain. given by the restriction of t over 0≤i≤n i {0, 1}. An alternating tree automaton A = Σ, Q, Q ∃ , Q ∀ , q I , δ, Ω consists of a finite input alphabet Σ, a finite set Q of states partitioned into existential states Q ∃ and universal states Q ∀ , an initial state q I , a transition relation δ ⊆ Q × Σ × {ε, 0, 1} × Q and a priority function Ω : Q → ω, which is bounded. The (Mostowski) index of the automaton is given by [ι, κ], where ι is the minimal value and κ is the maximal value of the priority function Ω. We can assume that ι ∈ {0, 1} and that for every n ∈ {ι, . . . , κ}, there is a q ∈ Q such that Ω(q) = n.

The run of the alternating automaton A on a conciliatory input tree t ∈ T ≤ω Σ is defined in terms of a parity game. A parity game

G = V, V 0 , V 1 , E, Ω is a bipartite labelled graph, with the partition (V 0 , V 1 ) of the set of verteces V , edge relation E ⊆ V × V and priority function Ω : Q → ω, which is bounded. A vertex v is a successor of a vertex v ′ if (v ′ , v) ∈ E (or v ∈ E(v ′ )).
A play from some vertex v 0 ∈ V i , i = 0, 1 procedes as follows: player i chooses a successor

v 1 ∈ E(v 0 ). Then, either v 1 ∈ V 0 or v 1 ∈ V 1 .
In the first case, player 0 chooses a successor v 2 ∈ E(v 2 ), in the second case player 1 chooses a successor v 2 ∈ E(v 2 ). And so on for v 2 , etc. If a player cannot make a move, he looses. If the play is infinite, we say that player 0 wins if and only if the greatest priority occurring inifinitely often in the sequence Ω(v 0 )Ω(v 1 )Ω(v 2 ) . . . is even. A parity game is called a weak parity game if, as a winning condition, we say that player 0 wins (either a finite or an infinite play) if and only if the greatest priority occurring in the play is even. Consider an alternating automaton A and a conciliatory input tree t ∈ T ≤ω Σ . The corresponding parity game G A,t is then defined as follows.

• the set V 0 is {0, 1} * × Q ∃ • the set V 1 is {0, 1} * × Q ∀ • from each vertex (v, q) and for each (q ′ , a) ∈ δ(q, t(v)), ((v, q), (va, q ′ )) ∈ E,
• for every vertex (v, q), Ω((v, q)) = Ω(q). We say that A accepts t iff player 0 has a winning strategy in the parity game G A,t .

A weak alternating tree automaton A is defined exactly as an alternating parity automaton, except that the run is given by a weak parity game.

There is a strong connection between the hierarchy of Mostowski indices of alternating automata and the fixpoint hierarchy of the modal µ-calculus. In the later, the complexity of a formula is measured by the number of non trivial nestings of least (µ) and greatest (ν) fixpoints. So Σ µ 1 is the set of formula having only least fixpoint operators, Π µ 1 is the set of formula having only greatest fixpoint operators, Σ µ 2 is the µ-closure of Π µ 1 formulae, Π µ 2 is the ν-closure of Σ µ 1 formulae, and so on and so forth3 . Then it can be shown that a language of binary trees is definable by a Σ µ n (resp. Π µ n ) formula of the modal µ-calculus iff it is recognizable by some alternating automata of index [1, n] (resp. [0, n -1]). On the other side, the class of weak alternating tree automata correspond exactly to the alternation free fragment of the modal µ-calculus.

We will also be interested in formulae with no fixpoint at all, that is modal formulae. These correspond to what are called strict automata. A strict tree automaton is an automaton with a strict partial order on states, and such that all possible transitions from a state q lead to another state q ′ wich is strictly smaller than q. It is then easy to verify that a language of binary trees is definable by a modal formula iff it is recognizable by a strict automaton.

The laguage recognized by a parity tree automaton A, denoted by L(A), is the set of trees accepted by A. Note that our parity tree automata work on conciliatory trees, that is along infinite and finite branches, while "standard" tree automata work only on infinite trees (full trees). Thus, instead of L(A), one considers L ω (A) = L(A) ∩ T ω Σ . The reason of our choice will become clear thereafter. In subsections 2.3 and 3.1 we will see that for any alternating automaton on conciliatory tree we can find an alternating automata on full trees which has the same index and, in some sense, the same topological complexity.

We say that an automata B simulates another automaton A if L(A) = L(B). In this case we write A ≡ B.

Given an automaton A and a state q = q I , by A q we denote the automaton corresponding exactly to A except the fact that the initial state now is q and not q I . If q is reachable from q I in the graph of the automaton A, then we say that A q is subautomaton of A, denoted by A > A q . Clearly, the set {A q : A > A q } is finite.

Assume we are given any two parity automata A and B. Without loss of generality, suppose that Q A = Q B . Then, for every q ∈ Q A we denote by A(q/B) = Σ, Q, Q ∃ , Q ∀ , q I , δ, Ω the automaton obtained as follows:

• Q • = Q •A ∪ Q •B , for • ∈ {∃, ∀}, • q I = q IA , • δ(p, * ) = δ A (p, * ), for every p ∈ Q A \ {q}, and δ(p, * ) = δ B (p, * ), for every p ∈ Q B , • δ(q, * ) = (ε, q IB ),
• Ω(p) = Ω A (p), for every p ∈ Q A , and Ω(p) = Ω B (p), for every p ∈ Q B Let A and B be any two parity automata. By A ∧ B (resp. A ∨ B), we denote the automaton recognizing L(A) ∩ L(B) (resp. L(A) ∪ L(B)). When C ≡ A ∧ B (resp. C ≡ A ∨ B), for some automata A and B, then we call C a conjunctive (resp. disjunctive) automaton. Sometimes we denote with 0.A (resp. 1.A) the automaton recognizing the language {t : t.0 ∈ L(A)} (resp. {t : t.1 ∈ L(A)}). By A we denote the automaton recognizing (L(A)) ∁ .

Hierarchy of Mostowski indices

Consider a type of parity tree automata. We consider the following partial order on indices of automata:

[ι, κ] ⊑ [ι ′ , κ ′ ] iff either {ι, . . . , κ} ⊆ {ι ′ , . . . , κ ′ } or {ι + 2, . . . , κ + 2} ⊆ {ι ′ , . . . , κ ′ }
The hierarchy induced by the partiale order ⊑ is called the hierarchy of Mostowski indices, or simply the Mostowski hierarchy, of the considered type of automata.

[1, 1] [1, 2] [1, 3] . . . . . . [0, 0] [0, 1] [0, 2] . . .
The hierarchy is said to be strict if there is an automaton at each level that cannot be simulated by any automaton of lower level. By a result of Bradfield [START_REF] Bradfield | The Modal µ-Calculus Alternation Hierarchy is Strict[END_REF][START_REF] Bradfield | Simplifying the Modal µ-Calculus Alternation Hierarchy[END_REF], we know that the Mostowski hierarchy of alternating tree automata, and therefore the fixpoint hierarchy of the modal µ-calculus, is strict. Arnold's proof of the same result [START_REF] Arnold | The µ-Calculus Alternation-Depth Hierarchy is Strict on Binary Trees[END_REF] can be adapted in order to show that the Mostowski hierarchy is also strict in the case of weak alternating tree automata.

Undressing the trees

It will be usefull to relate full and conciliatroy trees on to another. More specifically, given a full tree t ∈ T ω Σ∪{s} , the undressing of t, denoted by u(t), is the conciliatory tree defined as follows4 . Let v be the first node of t not labelled with s on the leftmost path of the tree (if there is no such node, then u(t) is empty). Then for each w ∈ {0, 1} * , consider two possibly infinite sequences:

• v 0 = v, w 0 = w, • v i+1 = v i b, w i+1 = w ′ i , if w i = bw ′ i and s = t(v i b), • v i+1 = v i 0, w i+1 = w i , if w i = bw ′ i and s = t(v i b), If w n = ε for some n, then w ∈ dom(u(t)) and u(t)(w) = t(v n ). Otherwise, w / ∈ dom(u(t)
). The idea of the undressing of t is that we want to skip some nodes and replace it with one of its sons, in our case by its left son. That is, if we are in a node v such that s ∈ t(v), then we want to replace v with v0. But in order to do it nicely, we must do it in a top-down manner.

Given a conciliatory language L, we define L s as the set of trees that belong to L after undressing, that is:

L s := {t ∈ T ω Σ∪{s} : u(t) ∈ L}
Note that, given any alternating automaton A, it is enough to add the set {(q, s, 0, q) : q ∈ Q A } to the transition relation δ A in order to obtain an alternating automaton

A * such that L ω (A * ) = (L(A)) s .
3 The Wadge Hierarchy

Playing Wadge Games

Consider the space T ω Σ equipped with the standard Cantor topology. Then, if T, U ⊆ T ω Σ , we say that T is continuously (or Wadge) reducible to U , if there exists a continuous function f such that T = f -1 (U ). We write T ≤ w U iff T is continuously reducible to U . This particular ordering is called the Wadge ordering. If T ≤ w U and U ≤ w T , then we write T ≡ w U . If T ≤ w U but not U ≤ w T , then we write T < w U . Thus, the Wadge hierarchy is the partial order induced by < w on the equivalence classes given by ≡ w .

Let T and U be two arbitrary sets of full binary trees. The Wadge game G w (T, U ) is played by two players, player I and player II. Both player build a tree, say t I and t II . At every round, player I plays first, and both players add a finite number of children to the terminal nodes of their corresponding tree. Player II is allowed to skip its turn, but not forever.

We say that player II wins the game iff t I ∈ T ⇔ t II ∈ U . This game was designed precisely in order to obtain:

Lemma 1 ([Wad84]). Let T, U ⊆ T ω P . Then T ≤ w U iff Player I has a winning strategy in the game G W (T, U ). Recall that a language L is called self dual if it is equivalent to its complement, otherwise it is called non-self dual. From Borel determinacy, if T, U ⊆ T ω Σ are Borel, then G W (T, U ) is deter- mined.
As a consequence, a variant of Martin-Monk's result shows that < w is well-founded. Thus, we can define by induction the Wadge degree for sets of finite Borel rank:

• d w (∅) = d w (∅ ∁ ) = 1 • d w (L) = sup{d w (M ) + 1 : M is non self dual, M < w L} for L > W ∅.
Recognizable languages we are considering do not need to be full binary trees, but also conciliatory binary trees. Thus, following [START_REF] Duparc | Wadge Hierarchy and Veblen Hierarchy Part 1: Borel Sets of Finite Rank[END_REF], let us define a conciliatory version of the Wadge game. Suppose T and U is a pair of conciliatory languages. Then the conciliatory Wadge game G c (T, U ) is played by two players: player I and player II. Both players build a tree, say t I and t II . At every round, player I plays first, and both players add a finite number of children to the terminal nodes of their corresponding trees, and both players are allowed to skip their turn, even forever. We say that player II wins the game iff t I ∈ T ⇔ t II ∈ U .

If player II has a winning strategy in G c (T, U ), we write T ≤ c U . As in the classical case, if T ≤ c U and U ≤ c T , then we write T ≡ c U . If T ≤ c U but not U ≤ c T , then we write T < c U . Thus, the conciliatory hierarchy is the partial order induced by < c on the equivalence classes given by ≡ c .

It is clear that the conciliatory hierarchy embeds naturally into the classical Wadge hierarchy by the mapping L → L s . Indeed, a strategy in one game can be translated into a strategy in the other by noting that an arbitrary skipping in the conciliatory game gives the same power as playing nodes whose labeling contains s.

The conciliatory degree of Borel sets of conciliatory trees is then defined as:

• d c (∅) = d c (∅ ∁ ) = 1 • d c (L) = sup{d c (M ) + 1 : M < c L} for L > W ∅.
It is possible to characterize a non self dual T as a language such that, up to Wadge equivalence, it corresponds to L s , for some well-choosen conciliatory language L ([Dup01], [START_REF] Duparc | On the Topological Complexity of Weakly Recognizable Tree Languages[END_REF]). Thus, since for every conciliatory language L of finite Borel rank it holds that d w (L s ) = d c (L), if we restrict our attention to non self dual sets, we can work in the conciliatory hierarchy instead of the classical Wadge hierarchy. By an abuse of notation, from now on we always use the subscript w .

We start defining a basic operation on sets of trees. Let L, M ⊆ T ≤ω Σ . We define the set L → M as the set of trees t ∈ T ≤ω Σ∪{a} , with a / ∈ Σ, satisfying any of the following conditions:

• t.0 ∈ L and a = t(1 n ) for all n,
• 11 n is the first node on the path 11 * such that a = t(11 n ) and t.11 n 1 ∈ M .

A player in charge of L → M is like a player in charge of L endowed with an extra move, which can be used only once, that erases everything played before. Then she can restart the play being in charge of M . We say that a non self dual set L ⊆ T ω Σ is initializable when L ≥ w L → L. If we assume projective determinacy5 , it is possible to show that < w is wellfounded on ∆ 1 2 sets. Thus, as before, it is possible to define by induction the Wadge degree for this class of sets.

Proposition 1 ( [START_REF] Duparc | The Normal Form of Borel Sets of Finite Rank[END_REF]). (PD) Let L, M ⊆ T ω Σ be two non self dual sets, 1. Assume that M is initializable, that L < w M and that for every initializable set of trees

N , if L < w N , then M ≡ w N or M ∁ ≡ w N . Then it holds that d w (M ) = d w (L) ω 1 . 2. Any set of Wadge degree d w (L) ω 1 is initializable.
These properties will be usefull in Section 6.

The Wadge Hierarchy of Weak Alternating Automata

The Hierarchy from Below and a Conjecture

In [START_REF] Duparc | On the Topological Complexity of Weakly Recognizable Tree Languages[END_REF], it was shown by the authors that the family of weakly recognizable tree languages, which are all Borel, is closed under the set-theoretical counterpart of ordinal sum (+), multiplication (•) by ordinals < ω ω , and pseudoexponentiation with base ω 1 . Since every weakly recognizable language is definable by an alternation free formula of the modal µ-calculus, it holds that the familiy of sets of binary trees definable by an alternation free formula is also closed under the preceding three set-theoretical operations.

We recall from [DM07] how these three operations are defined. Moreover, in discussing pseudo-exponentiation with base ω 1 , we will explain how it can be generalized to any recognizable topological property P .

Addition: Suppose that L(A), L(B) ⊆ T ≤ω Σ . We define the set L(B) + L(A) as the set of trees t ∈ T ≤ω Σ∪a satisfying any of the following conditions:

• t.0 ∈ L(A) and a = t(1 n ) for all n,

• 11 n is the first node on the path 11 * such that a = t(11 n ) and either a = t(11 n 1) and t.11 n 11 ∈ L(B) or a = t(11 n 1) and t.11

n 11 ∈ L(B)
This set is weakly recognizable ([DM07]). The weak alternating automaton recognizing it is denoted by B + A.

From the point of view of the player in charge of the set L(B) + L(A) in a Wadge Game, everything goes as if she was starting the game being in charge of L(A). So, provided she plays in such a way that a always holds in the rightmoust branch of the tree, the question whether the resulting infinite tree she will have produced at the end of the run belongs to L(B) + L(A) or not reduces to the question whether the tree starting from the left son of the root belongs to L(A) or not. But at any moment of the run she can play a node 11 n not labelled with a. Then, everything looks like the whole (finite) tree played since the beginning of the game is erased and he is now in charge of: L(B) if a is the label of the node (11 n 1), (L(B)) ∁ else.

Remark 1 ( [START_REF] Duparc | The Normal Form of Borel Sets of Finite Rank[END_REF][START_REF] Duparc | Wadge Hierarchy and Veblen Hierarchy Part 1: Borel Sets of Finite Rank[END_REF]). Let A, B, A ′ , B ′ be four weak alternating tree automata such that the languages they recognize are all non self dual. Then

• (L(A) + L(B)) ∁ ≡ w L(A) + (L(B)) ∁ , • The operation + preserves the Wadge ordering: if L(A ′ ) ≤ w L(A) and L(B ′ ) ≤ w L(B) then L(A ′ ) + L(B ′ ) ≤ w L(A) + L(B) • d w (L(A) + L(B)) = d w (L(A)) + d w (L(B)).
Multiplication by ω: Suppose that L(A) ⊆ T ≤ω Σ . We define L(A) • ω as the set of trees t ∈ T ≤ω

Σ∪{a} having no label a on path 1 * or satisfying the following conditions for some 0 < 1 ≤ k and n:

• 1 k is the first node labelled by a on the path 1 * , • i is the minimal such that for all i < j ≤ k the path 1 j 0 + has no label a, • 1 i 0 n is the first whith label a on the path 1 j 0 + , • either a = t(1 i 0 n 0) and t.1 i 0 n 00 ∈ L(A) or a = t(1 i 0 n 0) and t.

1 i 0 n 0 / ∈ L(A)
Then there is a weak alternating automata which recognizes L(A)•ω ([DM07]). We denote this automaton by A ω.

From the player's point of view when involved in Wadge Games, a player who is in charge of the set L(A) • ω is like a player who at the beginning of the play is trivially rejecting, with the additional option to decide after an arbitrary turn number k < ω to restart the run being in charge of

L(A) ≤ w L(B) then L(A) • ω ≤ w L(A) • ω 3. d w (L(A) • ω) = d w (L(A)) ω
Action over an arbitrary recognizable tree language: Before introducing the pseudo-exponentiation with base ω 1 , we introduce a more general operation called the action over L(A), where A can be any alternating tree automaton. In order to do so, let P be a certain topological property recognizable by an alternating tree automaton B P , like for instance "being a complete closed set", or "being a difference of two complete closed sets". Then the action of P over L(A), denoted by (P ; A) is defined as the class of tree recognized by the automaton given by replacing state by the following gadget 6 . % % J J J J J y y t t t t t @ @ @ @ @ ~~~~~(

n, ∃) ε, * { { w w w w w w w w w ε, * (n, •) @ @ @ @ @ ~~~~~r eplace with / / / o / o / o / o / o / o / o (n, ∀) 1, * # # G G G G G G G G G 0, * (n, ∀) 1, * # # G G G G G G G G G 0, * / / (n, •) 0, * c c G G G G G G G G G (n, •) | | z z z z % % J J J J J B P B P
where • ∈ {∃, ∀}, and every transition ending in (n,

•) is now ending in (n, ∃). Let L(A) ⊆ T ≤ω Σ . Suppose L(B) has property P . For t ∈ T ≤ω Σ let i P (t)(a 1 . . . a n ) = t(a 1 0a 2 . . . 0a n 0) if t.a 1 0a 2 . . . 0a n 1 ∈ L(B) s if t.a 1 0a 2 . . . 0a n 1 ∈ L(B)
Define L(A) ♮,P = {t ∈ T ≤ω Σ : u(i P (t)) ∈ L(A)} It is tedious but straightforward to verify that (P, A) defines the language L(A) ♮,P and that (P, A) is always an initializable set. By an abuse of notation, we sometims write (P, A) instead of L(A) ♮,P .

However, when we define the action of P on an alternating tree automaton, we must ensure that this operation is well defined with respect to the Wadge ordering. But, on one side by definition we have that the operation commutes with the complementation: (P, A) = (P, A) ∁ .

On the other side 7 , if player II has a winning strategy σ in G w (L(A, B), then she can directly lift σ to a winning strategy in G w ((P, A), (P, B)), for any recognizable P . Thus, this operation always preserves the Wadge ordering: if L(A) ≤ w L(B) then (P, A) ≤ w (P, B)

Having these two properties we are then assured that: 7 We assume projective determinacy when necessary.

Proposition 2. (PD) Let A and B any two alternating tree automata such that the languages they recognize are both non self dual. Then, for every recognizable P it holds that if L(A) < w L(B) then (P, A) < w (P, B)

But, let us come back to the pseudo-exponentiation of base ω 1 . The topological property of the action corresponding to this exponentiation corresponds to some Π 0 1 complete property. Thus, we may as well take P as the weakly recognizable language of tree having only the label a on the rightmoust branch. This is clearly a complete closed set.

Define

L(A) ♮ = {t ∈ T ≤ω Σ : u(i Π 0 1 (t)) ∈ L(A)}
Thus, the remark about the general case grants that (Π 0 1 , A) defines the language L(A) ♮ . Moreover, if A is a weak alternating automaton, (Π 0 1 , A) is also a weak alternating automaton. Therefore the class of weakly recognizable languages is closed under the action (Π 0 1 , ). From the player's point of view of Wadge Games, a player in charge of L(A) ♮ is like a player in charge of L(A) with an additional option to decide that a chosen node labeled in the past, joint with the subtree rooted in its right child, is to be ignored.

Remark 3 ([Dup95,Dup01]). Let A be any alternation free formulae such that

L(A) is non self dual. Then d w (L(A) ♮ ) = ω dw(L(A))+ρ 1 where ρ =    -1 if d w (L(A)) < ω, 0 if d w (L(A)) = β + n and cofβ = ω 1 , +1 if d w (L(A)) = β + n and cofβ = ω,
The definability of these three set-theoretical operations (sum, multiplication by ω, and pseudo-exponentiation with base ω 1 ) implies that the Wadge hierarchy of the Mostowski hierarchy of weak alternating automata, and therefore of the alternation free fragment, has height at least ε 0 . It was then conjectured in [START_REF] Duparc | On the Topological Complexity of Weakly Recognizable Tree Languages[END_REF] that, in fact, the height is precisely ε 0 .

In the next subsection we will made a first step forward by proving that there is no weakly recognizable tree language whose level is between ω ω and ω 1 . This means that if L is recognizable by a weak alternating automata, then

d w (L) < ω ω or d w (L) ≥ ω 1 .
In what follows, we will use another set-theoretical operation, which generalizes the multiplication by ω: the multiplication by a countable ordinal.

Countable multiplication:

We first define a operation that lets a player choose from a countable collection of sets of trees. Let f : ω → I be a bijection onto a countable set I. Assume that for every i ∈ I, L i ⊆ T ω Σ is a non self-dual Borel set. Define sup i∈I L i as the set of trees t ∈ T ≤ω Σ satisfying one of the following conditions:

• a = t(1 n ) for all n,
• 1 n is the first node on 1 * labelled by a and t.

1 n 0 ∈ L f (n) .
From a player point of view, being in charge of sup i∈I L i means "choosing" the set that the player wants to be in charge of among all the L i 's. This is done by playing for the first time on the rigthmost path an a and indicated with the lenght (modulo f ) of the path from the root to this node. This operation preserves the Wadge ordering.

The multiplication by countable ordinals is then defined as follows:

• L 1 = L • L (α + 1) = L α + L,
• L λ = sup β<λ L β, when λ is some limit ordinal.

Let λ be any countable ordinal. From the player point of view of Wadge Games, being in charge of the set L • λ is like being in charge of L, with the additional option to restart the run at any moment being in charge of L ∁ , and start again and again replacing L ∁ by L, and then L by L ∁ , etc. But provided that at every such changing the player descreases the countable ordinal λ. Therefore, during the play, this additional move will provide a decreasing finite sequence of ordinals, preventing her to reinitializing the play indifinitely.

Remark 4 ( [START_REF] Duparc | The Normal Form of Borel Sets of Finite Rank[END_REF][START_REF] Duparc | Wadge Hierarchy and Veblen Hierarchy Part 1: Borel Sets of Finite Rank[END_REF]). Let L, M be two non self-dual sets of trees of finite Borel rank, and α a countable ordinal. Then

1. (L • α) ∁ ≡ w L ∁ • α, 2. The operation •α preserves the Wadge ordering: if L ≤ w M then L • α ≤ w M • α 3. d w (L • α) = d w (L) α, 4. if d w (L) = α, then either L ≡ w ∅ • α or L ≡ w ∅ ∁ • α

A proof of the first step of the conjecture

In this subsection we introduce a class of reaching games based on the arena of the run of a alternating automaton over a finite tree. From the player point of view of Wadge games, these games precisely give us the power of the automaton we are considering on the border of the finite tree the considered player has played after a finite number of runs. We suppose that language recognized by an alternating automaton is a set of full binary trees.

Let A be an alternating automaton, and t[n] a finite tree. Then, consider the bipartite graph V, E corresponding to the run of A on t[n], excepted the fact that the partition of V is not given by (V 0 , V 1 ) but by (V * 0 , V * 1 ) defined as follows. We say that some vertex q, v belongs to V * 0 iff 1. it is not terminal and q ∈ Q ∃ , 2. it is terminal and q ∈ Q ∃ , but v / ∈ n {0, 1}.

We may now define the class of reaching games of A over t[n]. Such a reaching game is played by two players, player 0 and player 1, over the arena V * 0 , V * 1 , E . Let {S 1 , . . . , S n } be an enumeration of all the subsets of n {0, 1}. Given a subset S j , we say that Player 0 wins a play in the reaching game of A over t[n] with respect to S j iff the last position q, v ∈ V * 1 in the play is such that Player 1 cannot move and either v / ∈ n {0, 1} or v ∈ S j . This game is denoted by R(A, t[n], S j ).

Whitout loss of generality, we may suppose that for every v, w ∈ dom(t) we have t(v) = t(w) whenever v = w . Therefore, for every v ∈ t[n], there is a strict automaton B v and an unique state q v ∈ Q Bv such that for every alternating tree automaton A, t ∈ L(B v (q v /A)) iff t.v ∈ L(A). We may read B v as the automaton describing the only way to reach the node v starting from the root of the tree t. Moreover, for every n, there is a strict automaton B t[n] that completely describes this initial tree of height n + 1. That is, for every tree s,

if s ∈ L(B t[n] ), then s[n] = t[n].
Note that, for very S j , the number of winninig strategies for Player 0 in the reaching game R(A, t[n], S j ) is finite. Let {f 1 , . . . , f k } be an enumeration of the winning strategies for player 0 in R(A, t[n], S j ). Fix a winning strategy f i . Let F i ⊆ S j ∪ 0≤i<n i {0, 1} be the set of nodes such that, v ∈ F i iff there exists a final winning position having as second component v if player 0 plays according to f i . Clearly F i is finite. Suppose F i = {v i,1 , . . . , v i,k }. Then, for every v i,l ∈ F i , consider the finite set Φ i,l ⊆ Q A such that q ∈ Φ i,l iff q, v i,j is a possible final winning position when player 0 plays according to f i . Suppose Φ i,l = {q (i,1 l ) , . . . , q (i,n l ) }, for v i,l ∈ F i . Thus, the automaton

C i := B vi,1 q vi,1 /(A q (i,1 1 ) ∧. . .∧A q (i,n 1 ) ) ∧. . .∧B v i,k q v i,k /(A q (i,1 k ) ∧. . .∧A q (i,n k ) )
can be seen as describing the tree corresponding to the winning strategy f i for player 0 in the reaching game R(A, t[n], S j ).

More generally, given

V j := 1≤i≤l C i
and assuming that t ∈ L(A), Player 0 has a winning strategy in the reaching game R(A, t[n], S j ) iff t ∈ L(V j ). Consider now the set M R(A,t[n]) ⊆ {S 1 , . . . , S n } given by the following conditions: for every S i ∈ M R(A,t[n]) , 1. Player 0 has a winning strategy in R(A, t[n], S i ); 2. There is no S k ⊂ S i such that Player 0 has a winning strategy in R(A, t[n], S k ) By construction the following holds: Proposition 3. Let A be an alternating tree automaton and t ∈ T ω Σ . Then for every n, it holds that:

L(A ∧ B t[n] ) ≡ w L( Sj ∈M R(A,t[n]) V j )
This terminates the "automata theory" part of the proof of the main result, the other half of it being the following descriptive set theoretical result8 : Lemma 2 ( [START_REF] Duparc | A Hierarchy of Deterministic Context-Free ω-languages[END_REF]). Let A ⊆ T ω Σ be an initializable set of trees; λ, δ be some countable ordinals and

B ⊆ T ω Σ , if A • (δ + 1) ≤ w B ≤ w A • λ then there is a finite tree t such that    B t ≡ w A • (δ + 1), or B t ≡ w (A • (δ + 1)) ∁ .
where B t denotes the set of members of B extending t.

The core of the proof of our main result relies on finding a "reasonable" upper bound for the degrees of conjunctive and disjunctive automata. First of all we have to verify that9 : Lemma 3. Suppose A 1 , . . . A n are all weak alternating tree automata, and suppose for every 1 ≤ i ≤ n, L(A i ) is non self dual, d w (L(A i )) < ω 1 . Assume moreover that, for every j = 1, . . . , n, the Cantor normal form of base ω of

d w (L(A j )) is ij =mj ij =1 ω κi j n ij , with κ ij > κ ij +1
for every i j ∈ {1, . . . , m j -1} and n ij ∈ ω for every i j ∈ {1, . . . , m j }. Then:

1. d w (L(A 1 ∧ • • • ∧ A n )) ≤ sup{d w (L(A i )) : 1 ≤ i ≤ n} (2k) n ; 2. d w (L(A 1 ∨ • • • ∨ A n )) ≤ sup{d w (L(A i )) : 1 ≤ i ≤ n} (2k) n
where k < ω is the sum of all

ij =mj ij =1 n ij .
Before giving the proof of the lemma, we introduce the additive normal form (anf) of two countable ordinals. Assume any two countable ordinals α and β, with Cantor normal form of base ω respectively i=n i=1 ω κi n i , with κ i > κ i+1 for every i ∈ {1, . . . , n -1} and n i ∈ ω for every i ∈ {1, . . . , n}, and j=m j=1 ω ιj m j , with ι i > ι i+1 for every i ∈ {1, . . . , m -1} and m i ∈ ω for every i ∈ {1, . . . , m}. We let k = i=n i=1 n i + j=m j=1 m j and also let (γ 1 , . . . , γ m+n ) be an enumeration of {κ i : 1 ≤ i ≤ n} ∪ {ι j : 1 ≤ j ≤ m} that satisfies γ i ≥ γ j iff i ≤ j. Note that for every i γ i ≥ γ i+1 and γ i > γ i+2 are satisfied. Then the additive normal form of α and β is

anf(α, β) := i=n+m i=1 ω γi k.
By the definition of the additive normal form, it is very easy to verify that: Remark 5. For every pair of countable ordinals α and β, it holds that:

1. α ≤ anf(α, β) and β ≤ anf(α, β), 2. anf(α, β) = anf(β, α), 3. for every α ′ < α, we have anf(α ′ , β) < anf(α, β), 4. max{α, β} 2k ≥ anf(α, β).

Everything is now ready to prove Lemma 3.

Proof. We verify the first case by induction on n, the second case being analogous. The case n = 1 is trivial. Assume

L(A 1 ∧ • • • ∧ A n ) ≤ L(A k ) • (2k) n , with d w (L(A k )) = sup{d w (L(A i )) : 1 ≤ i ≤ n}. Without loss of generality, we assume that L(A n+1 ) ≤ w L(A k ). If we verify that L(A k n ∧ A n+1 ) ≤ w (L(A k ) • (2k) n ) • 2k ≡ w L(A k ) • (2k) n+1
, we are done. By Remark 5, in fact we demonstrate the following stronger result. Let A 1 , A 2 be two weak alternating automata such that L(A 1 ) and L(A 2 ) are non self dual and d w (L(A 1 )) = ξ 1 , d w (L(A 2 )) = ξ 2 are countable. Then:

( * ) d w (L(0.A 1 ∧ 1.A 2 )) ≤ anf(ξ 1 , ξ 2 )
The proof goes by induction on anf(ξ 1 , ξ 2 ) simoultaneously on the following three cases:

1. L(A 1 ) ≡ w ∅ • ξ 1 and L(A 2 ) ≡ w ∅ • ξ 2 , 2. L(A 1 ) ≡ w ∅ • ξ 1 and L(A 2 ) ≡ w ∅ ∁ • ξ 2 , 3. L(A 1 ) ≡ w ∅ ∁ • ξ 1 and L(A 2 ) ≡ w ∅ ∁ • ξ 2
Case 1: We have to describe a winning strategy for player II in the Wadge Game If we are able to show that player I has a winning strategy in this modified game, then we are done. At the beginning of the game, all three players are rejecting (since, from the player point of view of Wadge Games, they are all in charge of the empty set). Therefore, Player II has to stay rejecting untill both opponents are in charge of ∅ ∁ • ξ ′ i , with ξ ′ i < ξ i . At this time of the play, both player Ia and player Ib are momentaneously trivially accepting. When both opponents have reached such a position in the play, then player II has just to "decrease" her ordinal and reach a position where she is in charge of ∅ ∁ • anf(ξ ′ 1 , ξ ′ 2 ). This move can be done because by Remark 5 anf(ξ 1 , ξ 2 ) > anf(ξ ′ 1 , ξ ′ 2 ), and therefore we can apply the induction hypothesis in order to obtain a winning strategy for player II. Thus d w (L(0.A 1 ∧ 1.A 2 )) ≤ anf(ξ 1 , ξ 2 ) Case 2 and Case 3 are similar to the first case. We have just to consider in the second case the Wadge Game G w (L(0

G w (L(0.A 1 ∧ 1.A 2 ), ∅ • anf(ξ 1 , ξ 2 )).
.A 1 ∧ 1.A 2 ), ∅ • anf(ξ 1 , ξ 2 )) and in the third case the Wadge Game G w (L(0.A 1 ∧ 1.A 2 ), ∅ ∁ • anf(ξ 1 , ξ 2 )).
This proves ( * ), and therefore the induction step of point 1 of the lemma. ⊣

From Proposition 3 and Lemma 3 we immediatly obtain that:

Proposition 4. Let A be a weak alternating automaton, L(A) non self dual and 1 < d w (L(A)) < ω 1 . Let t be a full binary tree such that for a certain n it holds that L(A ∧ B t[n] ) < w L(A). Then there exists k ∈ N:

d w (L(A ∧ B t[n] )) = d w (L( Sj ∈M R(A,t[n]) V j )) ≤ λ k where λ = sup{d w L(A q ) : q ∈ Sj ∈M R(A,t[n]) i vi,j ∈Fi Φ i,j }.
As a corollary we obtain that:

Corollary 1. Assume A a weak alternating automaton, L(A) non self dual , 1 < d w L(A) < ω 1 and B ⊂ T ω B satisfying both B ≤ w L(A) and cof(d w B) = ω, then, for every n, there is λ < d w B such that for every tree t and every n:

if L(A ∧ B t[n] ) < w B then d w (L(A ∧ B t[n] )) < λ ω
This almost immediately leads to: Theorem 1. Let A be a weak alternating automaton, L(A) non self dual. Let α > 1 be a countable ordinal, and suppose d w L(A) = α. Then α < ω ω .

Proof. Towards a contradiction, we assume that α ≥ ω ω , and apply Corollary 1. Consider B a canonical set of Wadge degree ω ω . By corollary 1, there exists λ < d w (B) such that for every tree t and every n:

if L(A ∧ B t[n] ) < w B then d w (L(A ∧ B t[n] )) < λ ω
Fix such a λ. Since d w (B) = ω ω , we have that λ < ω ω . Therefore, there is n < ω such that λ < ω n . Hence λ ω < ω n+1 holds.

By Lemma 2, there is a tree t, an integer n such that either L(A) t ≡ w ∅ • (ω n+1 + 1) or L(A) t ≡ w (∅ • (ω n+1 + 1)) ∁ . Finally, since ω n+1 + 1 < ω ω , d w (L(A) t ) < λ ω holds, we obtain the following contradiction:

λ ω < ω n+1 < ω n+1 + 1 = d w (L(A) t ) < λ ω.
This concludes the proof of the theorem. ⊣ This theorem proves that there is no language recognizable by a weak alternating automaton in between the levels ω ω and ω 1 of the Wadge Hierarchy of Borel Sets, a first step in proving the whole conjecture about the Wadge Hierarchy of weakly recognizable tree languages.

A Wadge hierarchy for the third level of the hierarchy of Mostowski indices of recognizable language

In this section we assume projective determinacy. We extend the Wadge hierarchy of weak alternating automata by adding to the three previous operations

Proof. Clearly, it is enough to proof item 2. Suppose L(B) < w (D 2 (Π 1 1 ), A). Consider a set L of degree d w (L(B)) ω 1 . By Proposition 1.2, this set is initializable. Because (D 2 (Π 1 1 ), A) is also initializable, by Proposition 1.1, we have that L ≤ w (D 2 (Π 1 1 ), A). Therefore L(B) • ω < w (D 2 (Π 1 1 ), A). ⊣

By adapting some techniques introduced in [START_REF] Duparc | The Normal Form of Borel Sets of Finite Rank[END_REF], it is also possible to prove that:

Proposition 7. (PD) Let A, B any pairs of alternating tree automata. Then if L(B) < w (D 2 (Π 1 1 ), A) then (Π 0 1 , B) < w (D 2 (Π 1 1 ), A).

From Proposition 7, we obtain as a corollary:

Corollary 2. (PD) For every alternating tree automaton A Π 0 1 , (D 2 (Π 1 1 ), A) ≡ w (D 2 (Π 1 1 ), A).

As a matter of fact, Propositions 6 and 7 yield that given any two alternating automata A and B with d w (L(A)) + 1 = d w (L(B)), in between (D 2 (Π 1 1 ), A) and (D 2 (Π 1 1 ), B) there is enough space for a whole copy of the Wadge hierarchy of weak alternating tree automata.

It is clear that -up to Wadge equivalence -every level of this hierarchy corresponds to the class of models of a formula of the modal µ-calculus having alternation depth 2. However there is no formula corresponding to a finite iteration of the action of a difference of two Π 1 1 complete sets over an alternation free formula defining a game language of index [0, 1] or [1, 2]. Nevertheless we conjecture that:

Conjecture : The sub-hierarchy of the Wadge hierarchy induced, up to Wadge equivalence, by the closure of ∅ and W [0,1] under complementation, the settheoretical counterparts of ordinal sum, multiplication by ordinals < ω ω and the action of a complete closed set together with the action of a difference of two Π 1 1 complete set, corresponds to the Wadge hierarchy for the sets definable by a formula of alternation depth 2.

A proof of this conjecture would then imply that the eight of the Wadge hierarchy for this fragment of the modal µ-calculus is exactly ε ε0 .

Conclusion

In this paper, we made a first (very little) step towards the study of the connections between the fixpoint alternation depth hierarchy and the Wadge hierarchy for ∆ 1 2 sets. First of all, we have introduced the operation given by the action of some recognizable tree language over an alternating tree automata, which generalized the pseudo exponentiation with the base ω 1 presented in [START_REF] Duparc | On the Topological Complexity of Weakly Recognizable Tree Languages[END_REF]. In this last paper, it was conjectured that the height of the Wadge hierarchy for weakly alternating tree automata is exactly ε 0 . With the help of a nice combinatorial result and of a characterisation of the "power" of a player in a Wadge game after having played a finite number of runs, we were able to make a first step towards a complete answer to the conjecture. The operation introduced in the first part of the paper enables us to define actions with non Borel recognizable properties over sets of well-behaved languages with respect to the Wadge order. From this fact, in the final part of the paper we have done a first step towards the description of the Wadge hierarchy for the full modal µ-calculus by introducing an extension of the Wadge hierarchy for the alternating free fragment by mean of an action of a difference of two Π 1 1 complete sets.

  L(A) (resp. (L(A)) ∁ ), and start again and again replacing L(A) (resp. (L(A)) ∁ ) by (L(A)) ∁ (resp. L(A)) then (L(A)) ∁ (resp. L(A)) by L(A) (resp. (L(A)) ∁ ), etc. But provided that at every such changing the player descreases the finite ordinal k. Remark 2 ([Dup95,Dup01]). Let A, B be two weak alternating automata such that L(A) and L(B) are non self dual. Then 1. (L(A) • ω) ∁ ≡ w (L(A)) ∁ • ω, 2. The operation •ω preserves the Wadge ordering: if

  Those trees can have both infinite and finite branches. We call them conciliatory. A tree is called full if dom(t) = W * , and it is called binary if W = {0, 1}. In the sequel we only consider binary trees over Σ.Let T ≤ω Σ denote the set of all conciliatory binary trees over Σ and let T ω Σ denote the set of full binary trees over Σ. Given v ∈ dom(t), by t.v we denote the subtree of t rooted in v. By n {0, 1} we denote the set of words over {0, 1} of length n, and by t[n] we denote the finite initial binary tree of height n + 1

  Consider a slightly modified version of the Wadge Game, where player II is in charge of ∅ • anf(ξ 1 , ξ 2 )) and she plays at the same time against two different opponents, say player Ia and player Ib. Player Ia is in charge of ∅ • ξ 1 and player Ib is in charge of ∅ • ξ 2 . We say that player II wins the modified Wadge Game iff t II ∈ ∅ • anf(ξ 1 , ξ 2 ) and both t Ia ∈ ∅ • ξ 1 and t

Ib ∈ ∅ • ξ 2 or t II / ∈ ∅ • (δ 2 + δ 1 + n 2 + n 1 ) and either t Ia / ∈ ∅ • ξ 1 or t Ib / ∈ ∅ • ξ 2 .

For a formal definition, cf.[START_REF] Arnold | Rudiments of µ-Calculus[END_REF].

We follow here[START_REF] Duparc | On the Topological Complexity of Weakly Recognizable Tree Languages[END_REF].

From now on, when we assume projective determinacy in the statement of a proposition, we add the label PD.

If a node q is a member of Q ∃ (resp. Q ∀ ) and is such that Ω(q) = n, we denote it in the fugure by (n, ∃) (resp. (n, ∀).

Note that originally this lemma was stated for infinite words. We adapt it for full binary trees in a straightforward manner.

We correct here an inaccuracy in the corresponding Lemma published in[START_REF] Duparc | Describing the Wadge Hierarchy for the Alternation Free Fragment of µ-Calculus (I) -The Levels Below ω1[END_REF].

This result was recently streghntened by Arnold and Niwinski in[START_REF] Arnold | Continuous separation of game languages[END_REF], where they show that game languages form a hierarchy w.r.t. to Wadge reduciility.

Acknowledgment

We thank Raphael Carroy for discussions on Section 4, and particularly concerning the additive normal form of two countable ordinals.

⋆ Research supported by a grant from the Swiss National Science Foundation, n.

200021-116508: Project "Topological Complexity, Games, Logic and Automata".

(addition, multiplication by omega and action of some Π 0 1 complete set) an action of a difference of two Π 1 1 complete sets. By section 5, we know that if a Π 1 1 complete property is recognizable, then the corresponding action is also recognizable.

Consider the alphabet Σ [ι,κ] = {0, 1} × {ι, . . . , κ} with ι ∈ {0, 1} and ι ≤ κ. Then, to every tree t ∈ T ω Σ [ι,κ] , we associate a parity game G(t) as follows: a node v in the tree is a position for player 0 iff the first component of the node is 0, and the rank of the node corresponds to its second component. The set W [ι,κ] corresponds to the class of trees in T ω Σ [ι,κ] for which Player 0 has a winning strategy in the corresponding parity game P(t). For every index [ι, κ], the set W [ι,κ] is called the the game language of index [ι, κ]. It is easy to see that: Proposition 5. For every game language W [ι,κ] there is an alternating automaton of index [ι, κ] that recognizes it.

We denote by W [ι,κ] the alternating automata which recognizes W [ι,κ] . Game languages witnesses the strictness of the Mostowski hierarchy of the alternating tree automata, [Brad98b,Arn99] 10 . More precisely, each W [ι,κ] is complete for its corresponding level of the Mostowski hierarchy. Thus, any game language of index strictly greater than [0, 0] is not Borel. In particular,

. It follows easily that the language recognized by 0.W Π µ 2 ∧1.W [1,2] corresponds -up to Wadge equivalence -to a difference of two Π 1 1 complete sets. The action of such a difference of two Π 1 1 complete sets is therefore recognizable. We denote by (D 2 (Π 1 1 ), ) the alternating tree automaton recognizing it. Remember that by Proposition 2 we know that this operation is well defined in the way it (strictly) preserves the Wadge ordering:

If we consider the sub-hierarchy of the Wadge hierarchy induced, up to Wadge equivalence, by the closure of ∅ under complementation, the set-theoretical counterparts of ordinal sum, multiplication by ordinals < ω ω , and the action of a complete closed set together with the action of a difference of two Π 1 1 complete set, we enrich previous results with a new fragment of the Wadge hierarchy for alternating tree automata, and therefore for the modal µ-calculus. On one hand, we can verify that: Proposition 6. (PD) Let A, B, C be any alternating tree automata.

1. if L(B), L(C) < w (D 2 (Π 1 1 ), A) then L(B + C) < w (D 2 (Π 1 1 ), A); 2. if L(B) < w (D 2 (Π 1 1 ), A) then L(B) • ω < w (D 2 (Π 1 1 ), A).