Olivier Finkel
email: finkel@math.univ-paris-diderot.fr

Dominique Lecomte
email: dominique.lecomte@upmc.fr

Pierre Simonnet
email: simonnet@univ-corse.fr

An Upper Bound on the Complexity of Recognizable Tree Languages

Keywords: infinite trees, tree automaton, regular tree language, Cantor topology, topological complexity, Borel hierarchy, game quantifier, Wadge classes, Wadge degrees, universal sets, provably-∆ 1 2

The third author noticed in his 1992 PhD Thesis [Sim92] that every regular tree language of infinite trees is in a class (D n (Σ 0 2 )) for some natural number n ≥ 1, where is the game quantifier. We first give a detailed exposition of this result. Next, using an embedding of the Wadge hierarchy of non self-dual Borel subsets of the Cantor space 2 ω into the class ∆ 1 2 , and the notions of Wadge degree and Veblen function, we argue that this upper bound on the topological complexity of regular tree languages is much better than the usual ∆ 1 2 .

Introduction

A way to study the complexity of languages of infinite words or infinite trees accepted by various kinds of automata is to study their topological complexity, [LT94, PP04, GTW02, Sta97, Tho90, ADMN07]. In this paper we consider the topological complexity of regular languages of trees.

On one side the topological complexity of deterministic regular languages of trees has been determined. Niwinski and Walukiewicz proved that a tree language which is accepted by a deterministic Muller tree automaton is either in the class Π 0 3 or Π 1 1 -complete, [START_REF] Niwinski | A gap property of deterministic tree languages[END_REF]. And the Wadge hierarchy of deterministic regular languages of trees has been determined by Murlak,[START_REF] Murlak | The Wadge hierarchy of deterministic tree languages[END_REF][START_REF] Arnold | On the topological complexity of tree languages[END_REF].

On the other side in the course of years, more and more complex (non-deterministic) regular languages of trees have been found. Skurczynski proved that, for every natural number n ≥ 1, there are some Π 0 n -complete and some Σ 0 n -complete regular tree languages, [START_REF] Skurczynski | The Borel hierarchy is infinite in the class of regular sets of trees[END_REF]. Notice that it is an open question to know whether there exist some regular sets of trees which are Borel sets of infinite rank. Niwinski showed that there are some Σ 1 1 -complete regular sets of trees accepted by Büchi tree automata, and some Π 1 1 -complete regular sets of trees accepted by deterministic Muller tree automata, [START_REF] Niwinski | An example of non Borel set of infinite trees recognizable by a Rabin automaton[END_REF]. Some examples of regular tree languages at some transfinite levels of the difference hierarchy of analytic sets were given by Simonnet and Finkel in [START_REF] Simonnet | Automates et théorie descriptive[END_REF][START_REF] Finkel | On recognizable tree languages beyond the Borel hierarchy[END_REF]. Hummel proved in [START_REF] Hummel | Unambiguous tree languages are topologically harder than deterministic ones[END_REF] that there exists some (unambiguous) regular tree language which is topologically more complex than any set in the difference hierarchy of analytic sets. Arnold and Niwinski showed in [START_REF] Arnold | Continuous separation of game languages[END_REF] that the game tree languages W (ι,κ) form a infinite hierarchy of non Borel regular sets of trees with regard to the Wadge reducibility.

An upper bound on the complexity of regular languages of trees follows from the definition of acceptance by non deterministic Muller or Rabin automata and from Rabin's complementation Theorem: every regular set of trees is a ∆ 1 2 -set, see [START_REF] Rabin | Decidability of second-order theories and automata on infinite trees[END_REF][START_REF] Perrin | Infinite words, automata, semigroups, logic and games[END_REF][START_REF] Thomas | Automata on infinite objects[END_REF][START_REF] Lescow | Logical specifications of infinite computations[END_REF].

The third author noticed in his 1992 PhD Thesis [START_REF] Simonnet | Automates et théorie descriptive[END_REF] that every regular tree language of infinite trees is in a class (D n (Σ 0 2 )) for some natural number n ≥ 1, where is the game quantifier. We first give a detailed exposition of this result. Next, using an embedding of the Wadge hierarchy of non self-dual Borel subsets of the Cantor space 2 ω into the class ∆ 1 2 , and the notions of Wadge degree and Veblen function, we argue that this upper bound on the topological complexity of regular tree languages is much better than the usual ∆ 1 2 . The paper is organized as follows. In Section 2 we recall the notions of Muller tree automaton and regular tree language. The notions of topology are recalled in Section 3. We give the upper bound on the complexity of regular tree languages in Section 4. We argue that it is a much better upper bound than ∆ 1 2 in Section 5.

Recognizable tree languages

We now recall usual notation of formal language theory.

• In the sequel, Σ will be a finite alphabet with at least two letters. A non-empty finite word over Σ is a sequence x = a 1 • • • a k , where a i ∈ Σ for i = 1, . . . , k, and k ≥ 1 is a natural number. The length of x is k, and denoted by |x|. The empty word has no letter and is denoted by λ; its length is 0. Σ is the set of finite words (including the empty word) over Σ. A finitary language over Σ is a subset of Σ .

• The first infinite ordinal is ω. An ω-word over Σ is an ω-sequence a 1 • • • a n • • •, where a i ∈ Σ for each natural number i ≥ 1. When σ is an ω-word over Σ, we write σ = σ(1)σ(2) • • • σ(n) • • •, where σ(i) ∈ Σ for each i, σ[n] = σ(1)σ(2) • • • σ(n)
for each n ≥ 1, and σ[0] = λ. The set of ω-words over Σ is denoted by Σ ω . An ω-language over Σ is a subset of Σ ω .

• The usual concatenation product of two finite words u and v is denoted by u•v (and sometimes just uv). This product is extended to the product of a finite word u and an ω-word v: the infinite word u • v is then the ω-word such that:

(u • v)(k) = u(k) if k ≤ |u|, and (u • v)(k) = v(k -|u|) if k > |u|.
• The prefix relation is denoted by : a finite word u is a prefix of a finite word v (respectively, an infinite word v), denoted u v, if and only if there exists a finite word w (respectively, an infinite word w), such that v = u • w.

• We now introduce the languages of infinite binary trees whose nodes are labelled in a finite alphabet Σ. A node of an infinite binary tree is represented by a finite word over the alphabet {l, r}, where l means "left" and r means "right". An infinite binary tree whose nodes are labelled in Σ is identified with a function t : {l, r} → Σ. The set of infinite binary trees labelled in Σ will be denoted by T ω Σ .

• Let t be a tree. A branch b of t is a subset of the set of nodes of t which is linearly ordered by the tree partial order and closed under prefix relation, i.e., if x and y are nodes of t such that y ∈ b and x y, then x ∈ b. A branch b of a tree is said to be maximal if there is no branch of t containing strictly b.

Let t be an infinite binary tree in T ω Σ . If b is a maximal branch of t, then this branch is infinite. Let (x i ) i≥0 be the enumeration of the nodes in b which is strictly increasing for the prefix order. The infinite sequence of labels of the nodes of such a maximal branch b, i.e., t(x 0 )t(x 1 )

• • • t(x n ) • • •, is called a path. It is an ω-word over Σ.
We now define tree automata and regular tree languages. Definition 2.1 A (nondeterministic topdown) tree automaton is a quadruple A = (Q, Σ, ∆, q 0 ), where Q is a finite set of states, Σ is a finite input alphabet, q 0 ∈ Q is the initial state and ∆ ⊆ Q × Σ × Q × Q is the transition relation. The tree automaton A is said to be deterministic if the relation ∆ is a functional one, i.e., if for each (q, a) ∈ Q × Σ there is at most one pair of states (q , q ) such that (q, a, q , q ) ∈ ∆. A run of the tree automaton A on an infinite binary tree t ∈ T ω Σ is a infinite binary tree ρ ∈ T ω Q such that ρ(λ) = q 0 and, for each x ∈ {l, r} , (ρ(x), t(x), ρ(x • l), ρ(x • r)) ∈ ∆. Definition 2.2 A Muller (nondeterministic topdown) tree automaton is a 5tuple A = (Q, Σ, ∆, q 0 , F), where (Q, Σ, ∆, q 0 ) is a tree automaton and F ⊆ 2 Q is the collection of designated state sets. A run ρ of the Muller tree automaton A on an infinite binary tree t ∈ T ω Σ is said to be accepting if, for each path p of ρ, the set of states appearing infinitely often in this path is in F. The tree language L(A) accepted by the Muller tree automaton A is the set of infinite binary trees t ∈ T ω Σ such that there is (at least) one accepting run of A on t. The class REG of regular, or recognizable, tree languages is the class of tree languages accepted by some Muller automaton.

Remark 2.3 A tree language is accepted by a Muller tree automaton iff it is accepted by some Rabin tree automaton iff it is accepted by some parity tree automaton. We refer for instance to [Tho90, GTW02, PP04, ADMN07] for the definition of Rabin tree automaton and of parity tree automaton.

Topology

We assume the reader to be familiar with basic notions of topology which may be found in [START_REF] Moschovakis | Descriptive set theory[END_REF][START_REF] Lescow | Logical specifications of infinite computations[END_REF][START_REF] Kechris | Classical descriptive set theory[END_REF][START_REF] Staiger | ω-languages[END_REF][START_REF] Perrin | Infinite words, automata, semigroups, logic and games[END_REF]. There is a natural metric on the set Σ ω , which is called the prefix metric and defined as follows. For σ, σ ∈ Σ ω and σ = σ let δ(σ, σ ) = 2 -l pref(σ,σ ) where l pref(σ,σ ) is the first natural number n such that the (n + 1) st letter of σ is different from the (n + 1) st letter of σ . This metric induces on Σ ω the usual topology for which open subsets of Σ ω are of the form

W • Σ ω , where W ⊆ Σ . A set L ⊆ Σ ω is closed if its complement Σ ω \ L is an open set.
The topological space Σ ω is a Cantor space equipped with the usual Cantor topology.

• There is also a natural topology on the set T ω Σ [Mos09, [START_REF] Lescow | Logical specifications of infinite computations[END_REF][START_REF] Kechris | Classical descriptive set theory[END_REF]. It is defined by the following distance. Let t and s be two distinct infinite trees in T ω Σ . Then the distance between t and s is 1 2 n where n is the smallest natural number such that t(x) = s(x) for some word x ∈ {l, r} of length n. The open sets are then in the form T 0 • T ω Σ where T 0 is a set of finite labelled trees. T 0 • T ω Σ is the set of infinite binary trees which extend some finite labelled binary tree t 0 ∈ T 0 , t 0 is here a sort of prefix, an "initial subtree" of a tree in t 0 • T ω Σ . It is well known that the set T ω Σ , equipped with this topology, is homeomorphic to the Cantor space 2 ω , hence also to the topological spaces Σ ω , where Σ is finite.

• We now define the Borel Hierarchy of subsets of Σ ω . It is defined similarly on the space T ω Σ . Definition 3.1 For a countable ordinal ξ ≥ 1, the classes Σ 0 ξ and Π 0 ξ of the Borel Hierarchy on the topological space Σ ω are defined as follows:

Σ 0 1 is the class of open subsets of Σ ω , Π 0 1 is the class of closed subsets of Σ ω , and, for any countable ordinal ξ ≥ 2, Σ 0 ξ is the class of countable unions of subsets of Σ ω in η<ξ Π 0 η , Π 0 ξ is the class of countable intersections of subsets of Σ ω in η<ξ Σ 0 η . For a countable ordinal ξ, a subset of Σ ω is a Borel set of rank ξ if it is in Σ 0 ξ ∪Π 0 ξ but not in η<ξ (Σ 0 η ∪ Π 0 η ).
• There exists another hierarchy beyond the Borel hierarchy, which is called the projective hierarchy. The classes Σ 1 n and Π 1 n of the projective hierarchy, defined for natural numbers n ≥ 1, are obtained from the Borel hierarchy by successive applications of the operations of projection and complementation. The first level of the projective hierarchy is formed by the class Σ 1 1 of analytic sets and the class Π 1 1 of co-analytic sets, which are the complements of analytic sets.

In particular, the class of Borel subsets of Σ ω is strictly contained in the class of analytic sets, which are obtained by projection of Borel sets.

Definition 3.2 A subset A of Σ ω is analytic if there is a Borel subset B of (Σ×2) ω , where 2 = {0, 1}, such that σ ∈ A ⇔ ∃θ ∈ 2 ω with (σ, θ) ∈ B, where (σ, θ) is the infinite word over the alphabet Σ×2 such that (σ, θ)(i) = (σ(i), θ(i)) for each natural number i ≥ 1.
Remark 3.3 In the above definition we could take B in the class Π 0 2 , [START_REF] Moschovakis | Descriptive set theory[END_REF].

The Borel hierarchy and the projective hierarchy on T ω Σ are defined from open sets in the same manner as in the case of the topological space Σ ω .

• The notion of Wadge reducibility is defined via the reduction by continuous functions. In the sequel, Θ will be a finite alphabet with at least two letters. For

L ⊆ Σ ω and L ⊆ Θ ω , L is said to be Wadge reducible to L , denoted by L ≤ W L , if there exists a continuous function f : Σ ω → Θ ω , such that L = f -1 (L ). If ξ ≥ 1 is a countable ordinal and n ≥ 1 is a natural number, then a set F ⊆ Σ ω is said to be Σ 0 ξ (respectively, Π 0 ξ , Σ 1 n , Π 1 n )-complete if, for any set E ⊆ Θ ω , E ∈ Σ 0 ξ (respectively, E ∈ Π 0 ξ , E ∈ Σ 1 n , E ∈ Π 1 n ) iff E ≤ W F .
The ω-language R = (0 • 1) ω is a well known example of a Π 0 2 -complete subset of {0, 1} ω . It is the set of ω-words over {0, 1} having infinitely many occurrences of the letter 1. Its complement {0, 1} ω \ (0 • 1) ω is a Σ 0 2 -complete subset of {0, 1} ω . The set of infinite trees in T ω Σ , where Σ = {0, 1}, having at least one path in the ω-language R is Σ 1 1 -complete.

• We now define the difference hierarchy over a class Γ. Let n be a natural number, and (A p ) p<n be an increasing sequence of subsets of some space Z. The set D n [(A p ) p<n ] is the set of elements z ∈ Z such that z ∈ A p \ q<p A q for some p < n whose parity is opposite to that of n. We can now define the class of n-differences of Γ-subsets of Z, where Z = Σ ω or Z = T ω Σ :

D n (Γ) := {D n [(A p ) p<n ] | A p is in the class Γ for each p < n}.
It is well known that, for every countable ordinal ξ ≥ 1, the hierarchy of differences of Σ 0 ξ -sets is strict, i.e., the inclusion

D m (Σ 0 ξ ) ⊂ D n (Σ 0 ξ ) holds if m < n.
Notice that the difference hierarchy has an extension to countable ordinal ranks, see for instance [START_REF] Moschovakis | Descriptive set theory[END_REF][START_REF] Kechris | Classical descriptive set theory[END_REF], but we shall not need this in the sequel.

Moreover, every regular ω-language is a boolean combination of Σ 0 2 -sets, and belongs to some class D n (Σ 0 2 ), for some natural number n ≥ 1. We shall also consider these classes D n (Σ 0 2 ) in the sequel.

It is also well known that the hierarchy of differences of analytic sets is strict. It was proved by Hummel in [START_REF] Hummel | Unambiguous tree languages are topologically harder than deterministic ones[END_REF] that there exists some (unambiguous) regular tree language which is topologically more complex than any set in the difference hierarchy of analytic sets because there exists some (unambiguous) regular tree language which does not belong to the σ-algebra generated by the analytic sets.

An Upper Bound

We first recall the definition of Gale-Stewart games.

Definition 4.1 ([Kec95]) Let A ⊆ Σ ω . The Gale-Stewart game G(A)
is a game with perfect information between two players. Player 1 first writes a letter a 1 ∈ Σ, then Player 2 writes a letter b 1 ∈ Σ, then Player 1 writes a 2 ∈ Σ, and so on . . . After ω steps, the two players have composed a word σ = a 1 b 1 a 2 b 2 . . . of Σ ω . Player 1 wins the play iff σ ∈ A, otherwise Player 2 wins the play.

Let A ⊆ Σ ω and G(A) be the associated Gale-Stewart game. A strategy for Player 1 is a function F 1 : (Σ 2 ) → Σ and a strategy for Player 2 is a function

F 2 : (Σ 2 ) Σ → Σ. Player 1 follows the strategy F 1 in a play if for each natural number n ≥ 1 a n = F 1 (a 1 b 1 a 2 b 2 • • • a n-1 b n-1 ).
If Player 1 wins every play in which she has followed the strategy F 1 , then we say that the strategy F 1 is a winning strategy (w.s.) for Player 1. The notion of winning strategy for Player 2 is defined in a similar manner.

The game G(A) is said to be determined if one of the two players has a winning strategy.

We now recall the definition of the game quantifier. (2) If Γ is a class of sets and L ⊆ Σ ω , then L ∈ Γ if and only if there is P ⊆ Σ ω ×2 ω in Γ such that L = P .

Note that one can replace Σ ω with the homeomorphic space T ω Σ in this definition, replacing also P with a Γ-subset of T ω Σ × 2 ω . We obtain like this the definition of subsets of T ω Σ in the class (Γ). Note that we consider the alphabet 2 = {0, 1} and not the finite alphabets with at least two letters Σ in order to avoid troubles in the proof of Proposition 5.8 to come. This leads us to prove the following lemma. Proof. The proof is similar to that of Lemma 3.14 in [START_REF] Finkel | Infinite games specified by 2-tape automata[END_REF]. We may assume that Σ is a natural number and with a usual convention that Σ = {0, 1, . . . , Σ -1}. Let ϕ : Σ ω → 2 ω be defined by ϕ(a 1 a 2 ...) := (11) a 1 0(11) a 2 0... Note that ϕ is a continuous injection. We set D 1 := ϕ[A], so that D 1 codes A. We also set

D 2 := {α ∈ 2 ω | ∃a 1 , ..., a 2n ∈ Σ ∃k < Σ-1 (11) a 1 0...(11) a 2n 01 2k+1 0 α}, D 3 := {α ∈ 2 ω | ∃a 1 , ..., a 2n+1 ∈ Σ (11) a 1 0...(11) a 2n+1 01 2Σ-1 α}.
As D 2 and D 3 are open, O := D 2 ∪ D 3 is open too. The sets D 2 , D 3 are the results of infinite plays where two players alternatively write a letter 0 or 1 and the infinite word written by the two players in ω steps is out of K := ϕ[Σ ω ], due to the letters written by Player 2. More precisely, D 2 is the set of plays where Player 2 writes the (2n+1)th letter 0 while it was Player 1's turn to do this. And D 3 is the set of plays where Player 2 does not write a letter 0 soon enough when it is his turn to do this.

If now the two players write alternatively a letter 0 or 1 in such a way that the infinite word written by them in ω steps is in K and of the form (11) a 1 0(11) a 2 0..., then the letters 0 have been written alternatively by Player 1 and by Player 2, and these letters 0 determine the natural numbers a i . Thus the natural numbers a 2i+1 have been chosen by Player 1, and the natural numbers a 2i+2 have been chosen by Player 2 (for i ∈ ω).

If Player 1 has a winning strategy s in the game G(A), then consider a play in the game G(A ). If the two players alternatively write a letter 0 or 1 and the infinite word α written by them in ω steps is in K and of the form (11) a 1 0(11) a 2 0..., then the game is like a game where each player writes a letter in Σ at each step of the play, and Player 1 can apply s to ensure that (a i ) i≥1 ∈ A, which implies that ϕ((a i ) i≥1 ) ∈ D 1 ⊆ A , so Player 1 wins the play. If α is out of K due to the letters written by Player 2, then α ∈ D 2 ∪ D 3 ⊆ A , and Player 1 wins the play again. This shows that Player 1 has a winning strategy in G(A ).

If Player 1 has a winning strategy s in the game G(A ), then consider a play in the game G(A) where Player 2 does not make the final word α in D 2 ∪ D 3 . Player 1, following s , must write letters so that the final word α belongs to K. Then the game is reduced to the game G(A) in which the two players alternatively write letters a i in Σ. But Player 1 wins the game and this implies that Player 1 has a winning strategy in G(A).

We now give the upper bound on the complexity of regular tree languages.

Theorem 4.4 Let A be a Muller tree automaton. Then the tree language L(A) is in the class (D n (Σ 0 2 )), for some natural number n ≥ 1. Proof. Let A = (Q, Σ, ∆, q 0 , F) be a Muller tree automaton, where (Q, Σ, ∆, q 0 ) is a tree automaton and F ⊆ 2 Q is the collection of designated state sets.

The idea is to use a game which was considered by Gurevich and Harrington in [START_REF] Gurevich | Trees, automata, and games[END_REF]. For t ∈ T ω Σ we consider the Gale-Stewart game G(T t ), where the set T t ⊆ (∆ ∪ {l, r}) ω is defined as follows. Intuitively, in the game G(T t ), Player 1 writes transitions of the automaton A, i.e., letters of ∆, and Player 2 writes letters l or r, so that at the end of a play he has actually composed a path in the tree t.

At the first step, Player 1 chooses a transition (q 0 , t(λ), q, q ) ∈ ∆. Next, Player 2 chooses l or r. If Player 2 chooses l this means he has chosen the left son of the root node of the tree and thus Player 1 has to choose a transition of the form (q, t(l), q , q ). If Player 2 chooses r this means he has chosen the right son of the root node of the tree and thus Player 1 has to choose a transition of the form (q , t(r), q , q ). The game continues like this and Player 1 wins this game if the set of states (played by Player 1) which appear infinitely often on the path chosen by Player 2 belongs to F.

Formally, if α ∈ Θ ω , then we define (α) 1 , (α) 2 ∈ Θ ω by (α) 1 (k) := α(2k -1) and (α) 2 (k) := α(2k). T t is the union of α ∈ (∆ ∪ {l, r}) ω | ∃k ≥ 1 (α) 2 (k) / ∈ {l, r} with α ∈ (∆ ∪ {l, r}) ω | ∀k ≥ 1 (α) 1 (k) ∈ ∆ and (α) 2 (k) ∈ {l, r} and α(1)(1) = q 0 and (α)

1 (k)(2) = t((α) 2 [k -1]) and (α) 1 (k + 1)(1) = (α) 1 (k)(3) if (α) 2 (k) = l (α) 1 (k)(4) if (α) 2 (k) = r and {q ∈ Q | ∀j ∈ ω ∃m ≥ j (α) 1 (m)(1) = q} ∈ F .
By definition of the Muller acceptance condition for the tree automaton A, t ∈ L(A) ⇔ Player 1 has a winning strategy in the game G(T t ).

Indeed, if t ∈ L(A), then there is a witness ρ ∈ T ω Q and we can define a strategy ρ for Player 1 by ρ(x) := (ρ(x), t(x), ρ(xl), ρ(xr)), and ρ is winning for Player 1. Conversely, if ρ is a winning strategy for Player 1, then the formula ρ(x) := ρ(x)(1) defines a witness for the fact that t ∈ L(A).

We apply Lemma 4.3 to the finite alphabet ∆ ∪ {l, r}, which gives a continuous injection ϕ : (∆ ∪ {l, r}) ω → 2 ω and an open subset O of 2 ω . Then we set

P := {(t, α) ∈ T ω Σ × 2 ω | α ∈ ϕ[T t ]
∪ O}, so that t ∈ L(A) ⇔ Player 1 has a winning strategy in the game G(P t ) ⇔ t ∈ P .

It remains to see that

P is in D n (Σ 0 2 ) for some natural number n ≥ 1. If B := D n [(A p ) p<n ] is in D n (Σ 0 2 ) and C is a closed set, then B ∩ C = D n [(A p ∩ C) p<n ] is also in D n (Σ 0 2 ). If U is an open set, then B ∪ U = D n [(A p ∪ U ) p<n ] if n is odd, and B ∪ U = D n [(A 0 \U, A 1 ∪ U, ..., A n-1 ∪ U )] if n is even, so that B ∪ U is also in D n (Σ 0
2 ). This shows that the class D n (Σ 0 2 ) is closed under intersections with a closed set and unions with an open set. As it is also closed under images by homeomorphisms and ϕ is a homeomorphism onto its compact range, it is enough to show that T is in D n (Σ 0

2 ) for some natural number n ≥ 1. This is known to be equivalent to the statement "T is a boolean combination of Σ 0 2 -sets", and this follows from the definition of the Muller acceptance condition of the tree automaton A. Indeed,

-the condition "∃k ≥ 1 (α) 2 (k) / ∈ {l, r}" is open,
-the condition involving k and the big parentheses in the definition of T t is closed, -the condition involving F says that there is F in the finite set F such that, for each q in the finite set Q, either q ∈ F and ∀j ∈ ω ∃m ≥ j (α) 1 (m)(1) = q (this is a Π 0 2 condition), or q / ∈ F and ∃j ∈ ω ∀m ≥ j (α) 1 (m)(1) = q (this is a Σ 0 2 condition). This finishes the proof.

5 The Upper Bound is much better than ∆ 1 2 In this section, we are going to show that the upper bound given in the preceding section is actually much better than the usual one, ∆ 1 2 . • We first define the Wadge hierarchy, which is a great refinement of the Borel hierarchy, and is defined via reductions by continuous functions, [START_REF] Duparc | Wadge hierarchy and Veblen hierarchy: Part 1: Borel sets of finite rank[END_REF][START_REF] Wadge | Reducibility and determinateness in the Baire space[END_REF].

Definition 5.1 (Wadge [START_REF] Wadge | Reducibility and determinateness in the Baire space[END_REF]) Let L ⊆ Σ ω and L ⊆ Θ ω . We say that L and L are Wadge equivalent if L ≤ W L and L ≤ W L. This will be denoted by L ≡ W L . We shall also say that

L < W L iff L ≤ W L and L ≤ W L. We say that L is self dual if L ≡ W ¬L (¬L is the complement of L), otherwise we say that L is non self dual.
The relation ≤ W is reflexive and transitive, and ≡ W is an equivalence relation. The equivalence classes of ≡ W are called Wadge degrees. The Wadge hierarchy W H is the class of Borel subsets of a space Σ ω , equipped with ≤ W and ≡ W . For L ⊆ Σ ω and L ⊆ Θ ω , if L ≤ W L and L = f -1 (L ), where f is a continuous function from Σ ω into Θ ω , then f is called a continuous reduction of L to L . Intuitively, it means that L is less complicated than L , because in order to check whether σ ∈ L, it suffices to check whether f (σ) ∈ L (where f is a continuous function). Hence the Wadge degree of an ω-language is a measure of its topological complexity.

Note that in the above definition, we consider that a subset L ⊆ Σ ω is given together with the alphabet Σ. This is important as it is shown by the following simple example. Let L 1 = {0, 1} ω ⊆ {0, 1} ω and L 2 = {0, 1} ω ⊆ {0, 1, 2} ω . So the languages L 1 and L 2 are equal but considered over the different alphabets Σ 1 = {0, 1} and Σ 2 = {0, 1, 2}. It turns out that

L 1 < W L 2 . In fact L 1 is open and closed in Σ ω 1 while L 2 is closed but not open in Σ ω 2 .
We can now define the Wadge class of a set L.

Definition 5.2 Let L be a subset of Σ ω . The Wadge class of L is

[L] = {L | L ⊆ Θ ω for a finite alphabet Θ and L ≤ W L}.
Recall that each Borel class Σ 0 ξ and Π 0 ξ is a Wadge class. It follows from the study of the Wadge hierarchy that a set

L ⊆ X ω is Σ 0 ξ (respectively, Π 0 ξ )-complete iff it is in Σ 0 ξ but not in Π 0 ξ (respectively, in Π 0 ξ but not in Σ 0 ξ ).
Using the notion of a Wadge game, and the fact that the determinacy of Wadge games follows from Martin's Theorem stating that every Gale-Stewart Game G(B), with B a Borel set, is determined, see [START_REF] Kechris | Classical descriptive set theory[END_REF], Wadge proved the following result.

Theorem 5.3 (Wadge) Up to complement and ≡ W , the class of Borel subsets of the spaces Σ ω is a well ordered hierarchy. We can find an ordinal |W H|, called the length of the hierarchy, and a map

d 0 W from W H onto |W H| \ {0}, such that, for all L, L ⊆ Σ ω , -d 0 W L < d 0 W L ⇔ L < W L , -d 0 W L = d 0 W L ⇔ [L ≡ W L or L ≡ W ¬L ].
• Let ω 1 be the first uncountable ordinal. The Wadge hierarchy of Borel sets of finite rank has length 1 ε 0 where 1 ε 0 is the limit of the ordinals α n defined by α 1 = ω 1 and α n+1 = ω αn 1 if n is a natural number. Then 1 ε 0 is the first fixed point of the ordinal exponentiation of base ω 1 . The length of the Wadge hierarchy of Borel sets in ∆ 0 ω = Σ 0 ω ∩ Π 0 ω is the ω th 1 fixed point of the ordinal exponentiation of base ω 1 , which is a much larger ordinal. The length of the whole Wadge hierarchy is described in [START_REF] Wadge | Reducibility and determinateness in the Baire space[END_REF][START_REF] Duparc | Wadge hierarchy and Veblen hierarchy: Part 1: Borel sets of finite rank[END_REF], and uses the Veblen functions. To recall the definition of these functions, we need the notion of cofinality of an ordinal which may be found in [START_REF] Jech | Set theory[END_REF] and which we briefly recall now.

Definition 5.4 Let ζ be a limit ordinal. The cofinality of ζ, denoted by cof (ζ), is the least ordinal β such that there exists a strictly increasing sequence of ordinals

(ζ i ) i<β , of length β, such that sup i<β ζ i = ζ and ζ i < ζ for each i < β.
This definition is usually extended to 0 and to the successor ordinals: cof (0) = 0 and cof (ζ + 1) = 1 for every ordinal ζ.

The cofinality of a limit ordinal is always a limit ordinal with ω ≤ cof (ζ) ≤ ζ. The ordinal cof (ζ) is in fact a cardinal (see [START_REF] Jech | Set theory[END_REF]). If the cofinality of a limit ordinal ζ is ≤ ω 1 , then only the following cases may happen: cof (ζ) = ω or cof (ζ) = ω 1 . In the sequel we do not need to consider cofinalities which are larger than ω 1 . In the sequel, ω 2 willl be the first ordinal of cardinality greater than ℵ 1 , the cardinal of ω 1 . Note that each ordinal ζ < ω 2 has cofinality smaller than or equal to ω 1 .

Definition 5.5 The Veblen hierarchy (V ξ ) ξ<ω 1 of functions from ω 2 \ {0} into itself is defined as follows. V 0 is the function that enumerates ordinals of cofinality ω 1 or 1 that are closed under ordinal addition, i.e., V 0

(1) = 1, V 0 (ζ + 1) = V 0 (ζ) • ω 1 , V 0 (ζ) = ω ζ 1 when cof (ζ) = ω 1 , V 0 (ζ) = ω ζ+1 1 when cof (ζ) = ω.
For ξ > 0, V ξ is the function that enumerates ordinals of cofinality ω 1 or 1 that are closed under each function V η for any η < ξ.

We can now describe the length of the whole Wadge hierarchy of Borel sets on a Cantor space Σ ω or T ω Σ . It is the ordinal sup ξ<ω 1 V ξ (2). This is really a huge ordinal, with regard to the ω th 1 fixed point of the ordinal exponentiation of base ω 1 , which is the length of the Wadge hierarchy of Borel sets in ∆ 0 ω .

• We now recall the notion of a universal set which will be useful in the sequel.

Definition 5.6 Let Γ be a class of sets. We say that U ⊆ 2 ω ×Σ ω is universal for the Γ subsets of Σ ω if U is in Γ, and for each A ⊆ Σ ω in Γ there is β ∈ 2 ω such that A is the vertical section

U β := {α ∈ Σ ω | (β, α) ∈ U} of U at β.
The following result is mentioned in [START_REF] Louveau | The strength of Borel Wadge determinacy[END_REF].

Theorem 5.7 Let Γ be the Wadge class of a non self-dual Borel subset of 2 ω . Then there is a universal set for the Γ subsets of Σ ω .

k := s(a 1 b 1 a 2 ...b k-1 a k ) if k ≥ 2.
Notice that a strategy s for Player 2 is an element of 2 (2 2 ) * 2 . As (2 2 ) * 2 is countable, we can identify 2 (2 2 ) * 2 with the Cantor space 2 ω . Note that the map e : (s, α) → s * α is continuous from 2 (2 2 ) * 2 ×2 ω into 2 ω . This is actually emphasized by considering the Wadge hierarchy of non self-dual Borel subsets of 2 ω . By Corollary 5.11 we know that this hierarchy can be embedded into a hierarchy of classes Γ, included into ∆ 1 2 . On the other hand the Borel class Σ 0 2 is known to be a non self-dual Wadge class and the Wadge degree (in the sense of Theorem 5.3) of any Σ 0 2 -complete set is equal to ω 1 . Moreover, for each natural number n ≥ 1, the class D n (Σ 0

2 ) is also a non self-dual Wadge class and the Wadge degree of any D n (Σ 0 2 )-complete is equal to (ω 1 ) n , [START_REF] Wadge | Reducibility and determinateness in the Baire space[END_REF][START_REF] Duparc | Wadge hierarchy and Veblen hierarchy: Part 1: Borel sets of finite rank[END_REF]. Therefore, we see that this ordinal is actually much smaller than the first fixed point of the ordinal exponentiation of base ω 1 (the length of the Wadge hierarchy of Borel sets of finite ranks), than the ω th 1 fixed point of the ordinal exponentiation of base ω 1 (the length of the Wadge hierarchy of Borel sets in ∆ 0 ω ), and a fortiori than the ordinal sup

ξ<ω 1 V ξ (2),
which is the length of the Wadge hierarchy of (non self-dual) Borel subsets of the Baire space or the Cantor space. In conclusion the upper bound we gave is much smaller than ∆ 1 2 , as summarized in the following theorem.

Theorem 5.13 The hierarchy of classes Γ, for non self-dual Borel Wadge classes Γ of 2 ω , is a hierarchy of length sup ξ<ω 1 V ξ (2) included in the class ∆ 1 2 , while the regular tree languages are contained in the first (ω 1 ) ω levels of this hierarchy.

• We also note that regular tree languages are in the class provably-∆ 1 2 (see [Kan97, page 180]). This is essentially proved in [HKMN08] from Rabin's Theorem [START_REF] Rabin | Decidability of second-order theories and automata on infinite trees[END_REF]. Thus all regular tree languages have the Baire property (see [START_REF] Kanamori | The Higher Infinite[END_REF]page 180]).

This gives an answer to a question of the third author in [START_REF] Simonnet | Automates et théorie descriptive[END_REF].

As noticed by the referee of this paper, this also follows from [START_REF] Gogacz | Measure properties of game tree languages[END_REF], since all R-sets are Baire-measurable as well as Lebesgue measurable and it is proved in [START_REF] Gogacz | Measure properties of game tree languages[END_REF] that regular tree languages are R-sets.

Concluding remarks

We gave an upper bound on the topological complexity of recognizable tree languages and showed, using an embedding of the Wadge hierarchy of non self-dual Borel sets of 2 ω , that this upper bound is actually much smaller than ∆ 1 2 .

The anonymous referee of this paper indicated us that since the first appearance in 1992 of the above Theorem 4.4 in the PhD Thesis of the third author of this paper, quite a few authors made various observations in a few papers that we now mention.

In J. Bradfield's paper [START_REF] Bradfield | Fixpoints, games and the difference hierarchy[END_REF], and in [BDQ05] by J. Bradfield, J. Duparc and S. Quickert, a link between the game quantifier and the µ-calculus is described, and Corollary 11 of [START_REF] Bradfield | Fixpoints, games and the difference hierarchy[END_REF] explicitely states an upper bound in a style similar to the one presented in our paper. In [START_REF] Michalewski | On topological completeness of regular tree languages[END_REF], D. Niwinski and H. Michalewski are also interested in the problem of finding upper bounds for the class of regular tree languages. Using a method developed by J. Saint Raymond in [START_REF] Raymond | Quasi-bounded trees and analytic inductions[END_REF], they prove that the game tree language W 1,3 is complete for the class of Σ 1 1 -inductive sets. The Σ 1 1 -inductive sets are known to contain more complex sets than the σ-algebra generated by the analytic sets. Moreover, the referee indicated us that one can actually verify that the language given in S. Hummel's paper [START_REF] Hummel | Unambiguous tree languages are topologically harder than deterministic ones[END_REF] is reducible to W 1,3 and is not complete for the class of Σ 1 1 -inductive sets. In another recent paper [GMMS14] T. Gogacz, H. Michalewski, M. Mio and M. Skrzypczak show a one-to-one correspondence between the levels of the hierarchy of Kolmogorov R-sets and parity index of regular languages which extends the theorem from [START_REF] Michalewski | On topological completeness of regular tree languages[END_REF]. Since due to a theorem of Burgess the R-sets are known to be in correspondence with the game quantifier, on a technical level this covers Theorem 4.4. We also notice that another estimation of the kind of Theorem 5.13 is present in [START_REF] Gogacz | Measure properties of game tree languages[END_REF], where it is shown that regular languages of infnite trees occupy exactly the first ω-levels of Kolmogorov's hierarchy; and on the other hand it is known that there exist ω 1 levels in this hierarchy, all of them contained in the class ∆ 1 2 . Theorem 5.13 may then be seen as a generalization of the estimation following from [START_REF] Gogacz | Measure properties of game tree languages[END_REF].

We now state some important open questions.

• A difficult problem in the study of the topological complexity of recognizable tree languages is to determine the Wadge hierarchy of tree languages accepted by non deterministic Muller or Rabin tree automata. A subquestion is to know whether there is a regular language of infinite trees which is a Borel set of infinite rank.

• A related problem is to study the determinacy of Wadge games between tree automata; this would be a first step towards the possibility of using these games to determine the topological complexity of a regular tree language. Note that in the case of one-counter Büchi automata it has been shown that the determinacy of such games needs some large cardinal assumption (see [START_REF] Finkel | The determinacy of context-free games[END_REF]).

We now state some important open questions which are more related to the computer science roots of regular languages since they also involve decidability questions.

• While many questions about deterministic regular languages of infinite trees have been shown to be decidable [START_REF] Arnold | On the topological complexity of tree languages[END_REF], many corresponding questions about nondeterministic regular languages of infinite trees are still open.

Concerning the decidability of the topological complexity of regular languages, it has been shown recently by M. Bojanczyk and T. Place in [START_REF] Bojanczyk | Regular languages of infinite trees that are boolean combinations of open sets[END_REF] that one can decide whether a regular language accepted by a given tree automaton is a boolean combination of open sets. This result has been extended by A. Facchini and H. Michalewski in [START_REF] Facchini | Deciding the Borel complexity of regular tree languages[END_REF], where the authors prove that one can decide whether a regular tree language is in the class ∆ 0 2 . The question is still open for the other levels of the Borel hierarchy, or whether a regular tree language is Borel, analytic, coanalytic, or in any class Γ present in this paper.

  Definition 4.2 ([Mos09]) (1) If P ⊆ Σ ω ×2 ω , then we define P := σ ∈ Σ ω | Player 1 has a winning strategy in the game G(P σ )} where P σ = {α ∈ 2 ω | (σ, α) ∈ P }.

Lemma 4. 3

 3 We can find a continuous injection ϕ : Σ ω → 2 ω and an open subset O of 2 ω such that, for each subset A of Σ ω , the set A := ϕ[A] ∪ O satisfies the following property: Player 1 has a winning strategy in the game G(A) if and only if Player 1 has a winning strategy in the game G(A ).

Proof.

  Let A, B ⊆ 2 ω . We consider the Wadge game G(A, B) associated with A and B. It is the Gale-Stewart game defined by Player 2 wins the play ⇔ (a 1 a 2 ... ∈ A ⇔ b 1 b 2 ... ∈ B). If s is a strategy for Player 2 and α ∈ 2 ω , then we denote by s * α the element b 1 b 2 ... of 2 ω given by the answers of Player 2 in the play where Player 1 plays α := a 1 a 2 ... and Player 2 follows s. Formally, (s * α)(1) := b 1 := s(a 1 ) and, inductively, (s * α)(k) := b

Acknowledgement. We wish to thank the anonymous referee for very useful comments on a preliminary version of this paper which lead to a great improvement of the paper, and for indicating us some related studies that are now present in the bibliography.

Theorem 2.7 and Remark 4 after the proof of Theorem 3.1 in [START_REF] Louveau | The strength of Borel Wadge determinacy[END_REF] provide a subset L of 2 ω in Γ such that Player 2 has a winning strategy in the game G(A, L) for each subset A of 2 ω in Γ. We set V := {(s, α) ∈ 2 (2 2 ) * 2 × 2 ω | s * α ∈ L}. As e is continuous, V is in Γ. If A ⊆ 2 ω is in Γ, then Player 2 wins the Wadge game G(A, L), which gives s in 2 (2 2 ) * 2 such that A = V s . This shows that we can consider V as universal for the Γ subsets of 2 ω , up to identification.

Let Σ be a finite alphabet, and ψ : Σ ω → 2 ω be a homeomorphism. We set U := (Id 2 ω ×ψ) -1 (V), and it is routine to check that U is universal for the Γ subsets of Σ ω . Proposition 5.8 Let Γ be a class of sets. If there is a universal for the Γ subsets of Σ ω ×2 ω , then there is a universal for the Γ subsets of Σ ω .

Proof. Let U be a universal for the Γ subsets of Σ ω ×2 ω . We set V := U. Then V ⊆ 2 ω ×Σ ω is in Γ. Let A ⊆ Σ ω be in Γ, and P ⊆ Σ ω ×2 ω in Γ such that A = P . Then there is β ∈ 2 ω with P = U β . It remains to note that A = V β .

Corollary 5.9 Let Γ be the Wadge class of a non self-dual Borel subset of 2 ω . Then there is a universal for the Γ subsets of Σ ω .

Proof. Theorem 5.7 gives a universal for the Γ subsets of Σ ω ×2 ω , and Proposition 5.8 gives the result.

• We now turn to the key result of embeddability of the Wadge hierarchy into that obtained with the game quantifier.

Lemma 5.10 Let Γ be a class of sets closed under continuous pre-images. Then Γ is also closed under continuous pre-images.

Proof. Let L ⊆ Σ ω in Γ, P ⊆ Σ ω ×2 ω in Γ such that L = P , and f : Θ ω → Σ ω be continuous. As Γ is closed under continuous pre-images, the set

⇔ Player 1 has a winning strategy in the game

Corollary 5.11 The map Γ → Γ, defined on the collection of Wadge classes of a non self-dual Borel subset of 2 ω , is strictly increasing for the inclusion.

Proof. Let L, L be non self-dual Borel subsets of 2 ω , and Γ, Γ be the Wadge classes of L, L respectively. We assume that Γ Γ , so that L < W L . By Wadge's lemma, ¬L ≤ W L , so that Γ and Γ := {¬A | A ∈ Γ} are contained in Γ (see 21.14 in [START_REF] Kechris | Classical descriptive set theory[END_REF]). This implies that Γ ⊆ Γ , and in fact Γ ∪ Γ ⊆ Γ .

Assume, towards a contradiction, that Γ = Γ . Corollary 5.9 gives a universal U for the Γ subsets of 2 ω . We set

which is absurd.

Lemma 5.12 Let Γ be a class of Borel sets. Then Γ is contained in ∆ 1 2 .

Proof. Let L ⊆ Σ ω be in Γ, and P ⊆ Σ ω ×2 ω be in Γ such that L = P . If σ, τ are strategies for Players 1 and 2 respectively, then we denote by σ * τ the element of 2 ω obtained when Player 1 follows σ and Player 2 follows τ . As P is Borel, P β := {α ∈ 2 ω | (β, α) ∈ P } is Borel for each β ∈ Σ ω . By 20.5 in [START_REF] Kechris | Classical descriptive set theory[END_REF], the game defined by P β is determined. This implies that β ∈ L iff β ∈ P ⇔ Player 1 has a winning strategy in the game

The classes D n (Σ 0 2 ) appearing in Theorem 4.4 are contained in Σ 0 3 , which is a small part of the class of Borel sets. By Theorem 4.4 and Corollary 5.11, the tree languages of Muller tree automata are in the class Σ 0 3 . By 22.4 in [START_REF] Kechris | Classical descriptive set theory[END_REF], the sequence (Σ 0 ξ ) ξ<ω 1 is strictly increasing for the inclusion. By Corollary 5.11, the sequence ( Σ 0 ξ ) ξ<ω 1 is also strictly increasing for the inclusion. By Lemma 5.12, the elements of the latter sequence are contained in the class ∆ 1 2 . This shows already that the increasing sequence ( (D n (Σ 0 2 ))) n≥1 is only a small part of the hierarchy of ∆ 1 2 sets.