Pierre Simonnet
email: simonnet@univ-corse.fr

Benoit Cagnard
email: cagnard@univ-corse.fr

Baire and automata

Keywords: Automata, Borel functions, ω-regular sets, coanalytic sets

In his thesis Baire defined functions of Baire class 1. A function f is of Baire class 1 if it is the pointwise limit of a sequence of continuous functions. Baire proves the following theorem. A function f is not of class 1 if and only if there exists a closed nonempty set F such that the restriction of f to F has no point of continuity. We prove the automaton version of this theorem. An ω-rational function is not of class 1 if and only if there exists a closed nonempty set F recognized by a Büchi automaton such that the restriction of f to F has no point of continuity. This gives us the opportunity for a discussion on Hausdorff's analysis of ∆ 0 2 , ordinals, transfinite induction and some applications of computer science.

Introduction

We would like to dedicate this work to the memory of Pierre Dugac, who was a great historian of Mathematics, and the French specialist of Baire's work.

In his thesis Baire introduced the hierarchy of Baire classes of functions. A function f belongs to class 0 if it is continuous. A function f belongs to class 1 if it is the pointwise limit of a sequence of functions of class 0. A function f belongs to class 2 if it is the pointwise limit of a sequence of functions of class 1, and so on. The present work concerns functions f : A ω → B ω which are ω-rational (A ω and B ω sets of infinite words on finite alphabets A and B). We study these objects from a topological point of view. Let us describe the work done on ω-rational relations.

Acceptance of infinite words by finite automata was first considered in the sixties by Büchi in order to study decidability of the monadic second order of one successor over the integers [START_REF] Büchi | On a decision method in restricted second order arithmetic[END_REF]. Since this paper the ω-regular languages have been intensively studied especially because the topological space of infinite words with the usual prefix distance has very interesting properties [START_REF] Perrin | Infinite words[END_REF][START_REF] Thomas | Automata on infinite objects[END_REF][START_REF] Staiger | ω-languages[END_REF].

Rational relations on finite words are relations computable by finite automata with two tapes. They were first studied by Rabin and Scott [START_REF] Rabin | Finite automata and their decision problems[END_REF]. A number of their properties were established by Elgot and Mezei [START_REF] Elgot | on relations defined by generalised automata[END_REF]. The Decomposition Theorem characterizing functional rational transductions is one of them. A sequential function is a function whose graph is a rational relation with a condition of determinism on the input. A right (resp. left) sequential function reads words from right to left (resp. left to right). A functional rational transduction f satisfying f (ε) = ε is a composition of a left sequential function and of a right sequential function [START_REF] Eilenberg | Automata, Languages and Machines Vol A[END_REF][START_REF] Berstel | Transductions and Context Free Languages[END_REF][START_REF] Sakarovitch | Eléments de théorie des automates[END_REF]. The extension of rational relations to infinite words, called ω-rational relations, were first studied in [START_REF] Barzdin | Finite Automata, Behaviour and Synthesis[END_REF][START_REF] Lindner | Algebraische Codierungstheorie -Theorie der sequentiellen Codierungen[END_REF][START_REF] Boasson | Adherences of languages[END_REF][START_REF] Gire | Relation rationnelles infinitaires[END_REF]. ω-rational relations are relations computable by a finite automaton with two tapes with a Büchi acceptance condition (and a condition to avoid A * × B * , A ω × B * and A * × B ω ). In [START_REF] Gire | Two decidability Problems for infinite words[END_REF] Gire shows that functionality is decidable for a ω-rational relation. In [START_REF] Frougny | Synchronized relations of finite and infinite words[END_REF] Sakarovitch and Frougny show that ω-rational relations of A ω × B ω with bounded delay are exactly the ω-regular languages on the product alphabet A × B. In addition, they prove some undecidability results on ω-rational relations which can be deduced from corresponding undecidability results on rational relations over finite words. The reader should also see [START_REF] Latteux | Rational omega-Transductions[END_REF][START_REF] Choffrut | Uniformization of Rational Relations[END_REF] for other properties and references.

It is only in [START_REF] Finkel | On the topological complexity of infinitary rational relations[END_REF][START_REF] Finkel | Undecidability of topological and arithmetical properties of infinitary rational relations[END_REF] that the topological complexity of ω-rational relations is really investigated. Links between descriptive set theory and automata theory are not new. They go back to Büchi and Landweber's work [START_REF] Landweber | Decision problem for ω-automata[END_REF][START_REF] Büchi | Solving sequential condition by finite-state strategies[END_REF][START_REF] Trakhtenbrot | Finite Automata[END_REF]. Büchi talks very early about analytic set and games [START_REF] Büchi | Using determinancy of games to eliminate quantifers[END_REF]. In [START_REF] Wagner | Recursive ω-languages[END_REF] Wagner and Staiger shows that a subset of A ω (A finite) is recognized by a nondeterministic turing machine with Müller conditions if and only if it is an effective analytic set, that is to say a Σ 1 1 set (see Rogers [START_REF] Rogers | Theory of Recursive Functions and Effective Computability[END_REF] and Moschovakis [START_REF] Moschovakis | Descriptive Set Theory[END_REF] for a definition of the class Σ 1 1 ). In Staiger papers [START_REF] Staiger | Hierarchies of Recursive ω-languages[END_REF][START_REF] Staiger | Sequential mappings of ω-languages[END_REF][START_REF] Staiger | Research in the Theory of ω-languages[END_REF][START_REF] Staiger | Recursive Automata on Infinite Words[END_REF][START_REF] Staiger | ω-languages[END_REF] one can have a good overview of the subject. We give here a short account of Finkel's recent work.

Descriptive set theory is the study of definable sets in Polish spaces. A Polish space is a topological space P which is separable (it has a countable dense subset) and have a compatible metric d such that (P, d) is complete. Compact metric spaces are Polish(2 ω the Cantor space, [0, 1]). Complete separable metric spaces are Polish (R, C, C[0, 1]). The most important Polish space is the Baire space ω ω , that is the space of infinite sequence of integers. The family of Borel sets, of a polish space P , is the smallest family of subsets of P which contains open sets and is closed under complements and countable unions. A set E of a polish space P is an analytic set if it is a continuous image of the Baire space ω ω . Another equivalent definition say that E is an analytic set if it is the projection of a Borel set F ⊂ ω ω × P on P . It is easy to construct analytic sets. Let L ⊂ A * , and let L * be the monoid generated by L. Replace star operation * by ω operation, then L ω is an analytic set. If L is finite L ω is compact. If L is not finite L is countable, so we can enumerate elements of L = {u 0 , u 1 , . . . , u n , . . .}. Define an application φ : ω -→ A * by φ(n) = u n . Extend φ in monoid morphism φ : ω * -→ A * . Next extend φ in continuous application φ : ω ω -→ A ω . Since the graph of φ is closed, then L ω is analytic as projection of a closed set. In 1988 Louveau showed that there exists an L such that L ω is not Borel. Unfortunately, he only proved the existence of a such L, he didn't give effectively such a L. His work remains unpublished. An analytic complete set is an analytic set so that any other analytic set can be obtained by continuous inverse image of it. In 2000, Finkel showed that a very simple context free language L is such that L ω is analytic complete [START_REF] Finkel | Wadge Hierarchy of Omega Context Free Languages[END_REF]. Finally in 2001, Finkel showed that one can define an ω-rational relation R such that R is analytic complete (in particular R is not Borel) [START_REF] Finkel | On the topological complexity of infinitary rational relations[END_REF]. From this, and using the Post correspondance problem, Finkel discovered new undecidability results about ω-rational relations and gave another proof of the undecidability results of Sakarovitch and Frougny [START_REF] Finkel | Undecidability of topological and arithmetical properties of infinitary rational relations[END_REF].

In this paper an ω-rational function is an (everywhere defined) application f : A ω → B ω whose graph is an ω-rational relation. The ω-rational functions are of Baire class 2. Baire proves the following theorem.

Theorem 1 A function f is not of class 1 if and only if there exists a closed nonempty set F such that the restriction of f to F has no point of continuity.

We prove the automaton version of this theorem.

Theorem 2 An ω-rational function is not of class 1 if and only if there exists a closed nonempty set F recognized by a Büchi automaton such that the restriction of f to F has no point of continuity.

The original proof of Baire uses transfinite induction [START_REF] Baire | Oeuvres scientifiques[END_REF][START_REF] Dugac | [END_REF]. The proof presented in [START_REF] Kuratowski | Topology[END_REF][START_REF] Kechris | Classical Descriptive Set Theory[END_REF] is Hausdorff's proof ; we will give a detailed proof of it. The characterization theorem of Baire appears as a corollary of the analysis of ∆ 0 2 sets in an uncountable complete separable metric space. A ∆ 0 2 set is a set which is both F σ (countable union of closed sets) and G δ (countable intersection of open sets). The analysis of ∆ 0 2 sets uses a transfinite derivation over closed sets which is of the same kind of Cantor's derivation. Recall that Cantor discovered countable ordinals iterating in a transfinite way the operation of elimination of the isolated points of a closed set of reals (see Kechris Louveau [48]).

In fact our theorem is just a remark : when we restrict Hausdorff's derivation to ω-regular sets, it stops the derivation at an integer (a greatest fixpoint). This was remarked by the first author in 1986, who, in addition, showed a connection between an old separation theorem and work of Arnold and Nivat [START_REF] Arnold | Comportement de Processus[END_REF] about theory of parallelism.

Hausdorff's result is a first step in the study of Wadge's classes of Borel sets [105]. Wadge's degrees of Borel sets are essentially well ordered and the type order of the hierarchy is an old uncountable ordinal studied first by Veblen [START_REF] Veblen | Continuous increasing function from finite and transfinite ordinals[END_REF]. It is usual to present Wadge's degrees with games [START_REF] Wadge | Degrees of complexity of subsets of the Baire space[END_REF]. The restriction of the Wadge's hierarchy to ω-regular sets gives Wagner's hierarchy [START_REF] Wagner | On ω -regular Sets[END_REF]. This is easily seen with Büchi Landweber's result on games such that the winning set is an ω-regular set [START_REF] Büchi | Solving sequential condition by finite-state strategies[END_REF][START_REF] Trakhtenbrot | Finite Automata[END_REF]. The type order of Wagner's hierarchy is the countable ordinal ω ω . Our proof is of the same type of combinatorial proofs appearing in Wagner's paper [START_REF] Wagner | On ω -regular Sets[END_REF].

This separation result can be extended to all Wagner classes [START_REF] Simonnet | Automate et théorie descriptive[END_REF][START_REF] Simonnet | Un théorème de séparation sur les ensembles rationnels de mots infinis[END_REF], this is easy using well known things from descriptive set theory and Büchi Landweber's result on game [START_REF] Büchi | Solving sequential condition by finite-state strategies[END_REF]. On this subject one can also study the work of Barua [START_REF] Barua | Hausdroff-Kuratowski hierarchy of ω -regular languages and a hierarchy of Muller automata[END_REF]. These results are also automata analogue of effective results of Louveau [START_REF] Louveau | Some results in the Wadge Hierarchy of Borel Sets[END_REF] which give classical results in the plane [START_REF] Raymond | Boréliens à coupe K σ[END_REF][START_REF] Louveau | Borel classes and closed games Wadge-type and Hurewicztype results[END_REF].

For more on Wagner's hierarchy, we refer the reader to the works of Kaminski [START_REF] Kaminski | A classification of ω -regular languages[END_REF], Carton and Perrin [START_REF] Carton | The Wagner hierarchy[END_REF], Wagner [START_REF] Wagner | On ω -regular Sets[END_REF], Selivanov [START_REF] Selivanov | Fine hierarchy of regular ω-languages[END_REF], Staiger [START_REF] Staiger | ω-languages[END_REF][START_REF] Staiger | the Cantor Space and the Baire Space, G δ \F s igma is a Single Wadge-Degree, an effective proof[END_REF]. It turns out that the topological invariants for Wagner's classes can be described with the algebra of finite monoïds, see Carton and Perrin [START_REF] Carton | The Wagner hierarchy[END_REF], Wilke [START_REF] Wilke | An algebraic theory for regular languages of finite and infinite words[END_REF] and Perrin and Pin [START_REF] Perrin | Infinite words[END_REF]. For more on Wadge's hierarchy we refer the reader to the papers of Wadge [START_REF] Wadge | Degrees of complexity of subsets of the Baire space[END_REF]105], the book of Kechris [START_REF] Kechris | Classical Descriptive Set Theory[END_REF], and works from Louveau [START_REF] Louveau | Some results in the Wadge Hierarchy of Borel Sets[END_REF], Saint Raymond [START_REF] Raymond | Classification de Wadge. Note d'exposé[END_REF], Duparc [START_REF] Duparc | Wadge Hierarchy and Veblen Hierarchy : Part1 : Borels Sets of Finite Rank[END_REF] , Finkel [START_REF] Finkel | Borel Ranks and Wadge Degrees of Context Free omega-Languages[END_REF] , Ressayre [START_REF] Duparc | Computer Science and the Fine Structure of Borel Sets[END_REF].

For recent problems in theory of parallelism one can see [START_REF] Bergeron | An automated analysis of Ping-Pong Interactions in E-mail Services[END_REF]. Now we return to Elgot Mezei's decomposition theorem. A left sequential machine which reads infinite words is a continuous function. The idea to read from left to right in a right sequential finite state machine suggests non determinism. Moreover, if we work on infinite words rather than finite words, this suggests discontinuity and the Baire hierarchy. If an ω-rational function is not of Baire class 1, one can find a rational tree (tree with a finite number of subtrees) whose set of infinite branches is a Perfect set P (closed set without isolated points [START_REF] Kuratowski | Topology[END_REF]) and the restriction of f to P has no point of continuity. This may be interesting, even for finite words.

If the graph of f : A ω → B ω is recognized by a Büchi automaton on the product alphabet A × B we say that f is a synchronous function. Recently we have shown that one can decide if a synchronous function is Baire class 1 [START_REF] Cagnard | Automata Borel functions and real numbers in Pisot basis[END_REF]. Our proof is topological and it is an easy corollary of Sierpinski [START_REF] Sierpinski | Sur les fonctions de première classe[END_REF] and Landweber [START_REF] Landweber | Decision problem for ω-automata[END_REF]. In the present paper we would like to obtain some missing links with works by Beal, Carton, Choffrut, Frougny, Michel, Prieur, Sakarovitch. They have given more algorithmic proofs [START_REF] Choffrut | Une caractérisation des Fonctions Séquentielles et des fonctions sous séquentielles en tant que Relations Rationnelles[END_REF][START_REF] Béal | Squaring Transducers : an efficient procedure for deciding functionnality and sequentiality[END_REF][START_REF] Frougny | On-the-Fly algorithms and sequential machines[END_REF][START_REF] Frougny | Numeration Systems. Chapter 8 of M. Lothaire, Algebraic Combinatorics on Words[END_REF][START_REF] Prieur | How to decide continuity of rationnal functions on infinite words[END_REF][START_REF] Prieur | How to decide continuity of rationnal functions on infinite words[END_REF][START_REF] Béal | Determinization of transducers over finite and infinite words Theoret[END_REF][START_REF] Carton | Unambiguous Büchi automata[END_REF]. Talks with Finkel and Carton have given us the impression that for an ω-rational function, being of Baire class 1 is an undecidable property.

This paper is adressed to both computer scientists or set theorists and analysts. We hope that our presentation will be useful for computer scientists. For example, it may help to understand recent results of Duparc [START_REF] Duparc | A Hierarchy of Deterministic Context-Free ω-languages[END_REF] and Lecomte [START_REF] Lecomte | ω-powers and descriptive set theory[END_REF]. On the other hand will expect that a descriptive set theorist will learn automata theory through our examples. He may solve some definability problems about sets recognized by tree automata.

This paper is organized as follows. In sections 2, 3, 4, 5 we present some definitions and properties from automata theory and descriptive set theory. In section 6 we present an example which may be useful to understand the result of Baire. In section 7, we present the difference hierarchy and we give a detailed proof of Hausdorff's result in section 8. In section 9, we give the proof of Baire's result. In section 10, we prove the automaton version of Baire's result. In section 11, we present briefly the Wadge's game and separation games ; we think that this sheds light about results of sections 8 and 10. Finally, we start the discussion about relations between Hausdorff's analysis of ∆ 0 2 sets, ordinals, transfinite induction and applications of computer science.

Automata on infinite words

infinite words

For the concepts introduced in this section we refer the reader to [START_REF] Barzdin | Finite Automata, Behaviour and Synthesis[END_REF][START_REF] Eilenberg | Automata, Languages and Machines Vol A[END_REF][START_REF] Perrin | Infinite words[END_REF]. Let ω be the set of natural numbers (the first infinite ordinal). Complement of a set E will be noted Ě. Let A be a finite alphabet or countable alphabet (A = ω). All alphabets that we consider will have at least two letters. A finite word u over the alphabet A is a finite sequence of elements of A. The set of finite words on A will be called A * . The length (number of letters) of a word u will be noted |u|. A particular word is the empty word ǫ, |ǫ| = 0. As usual A + = A * -{ǫ}. With concatenation, A * is a monoïd with unit element ǫ. An infinite word α over alphabet A is an infinite sequence of elements of A : α = α(0)α(1)...α(n).... The set of infinite words on the alphabet A will be noted A ω . We note α[n] the finite word formed with the n first letters of the infinite word α, α[0] = ǫ, α [START_REF] Addison | The Theory of hierarchies[END_REF] = α(0). The set A ω , viewed as a product of infinitely many copies of A with the discrete topology, is a metrizable space :

d(α, β) = 1/2 n with n = min{i ∈ ω | α(i) = β(i)} if α = β 0 if α = β
The collection (uA ω ) u∈A * is a countable basis of clopen sets for this topology. Recall that if A is finite then (A ω , d) is a compact metric space. If A = ω, then (ω ω , d) is a complete metric space, known as the Baire space, which is not compact. The prefix ordering is called <. A finite word u ∈ A * is a prefix of the finite word v ∈ A * (resp infinite word α ∈ A ω ) if there exists a finite word w ∈ A * (resp infinite word β ∈ A ω ) so that v = u.w (resp α = u.β).

Automata on infinite words

Definition 1 A Büchi automaton A is a 5-tuple : A = A, Q, I, T, F , where A is a finite alphabet, Q is a finite set of states, I ⊂ Q is the set of initial states, T ⊂ Q × A × Q is the set of transitions and F ⊂ Q the set of final states. An infinite word α ∈ A ω is recognized by A if there is β ∈ Q ω such that : β(0) ∈ I, ∀ n ∈ ω, (β(n), α(n), β(n + 1)) ∈ T and β(n) ∈ F for infinitely many n. The set of words recognized by a Büchi automaton A is noted L ω (A).

Remark 1 Instead of Büchi automaton one can say automaton with Büchi's acceptation.

T can be viewed as a partial function δ :

Q × A → P(Q) where δ(p, a) = {q ∈ Q | (p, a, q) ∈ T }. Function δ can be extended to δ : Q × A * → P(Q) by δ(p, ua) = δ(δ(p, u), a)
where u is a finite word and a a letter and δ(p, ǫ) = p.

An infinite path c in A is an infinite word c = c(0)c(1)...c(n)...

∈ (Q × A × Q) ω such that ∀n ∈ ω, c(n) ∈ T . For each n, c(n) is of the form c(n) = (β(n), α(n), β(n + 1)
). This will be denoted by the following graphical notation of path.

c = β(0) α(0) ---→ β(1) α(1) ---→ β(2) α(2)
---→ . . . The infinite word α ∈ A ω , α = α(0)α(1) . . . α(n) . . ., is the label of the path c. Let us note Infinity(c) as the set of states which appears infinitely many times in c. A path c is said to be successful if β(0) ∈ I and Infinity(c) F = ∅. Note that an infinite word α is recognized by A if there is a successful path c in A of label α.

An automaton is called deterministic if it has a unique initial state and for each state p and each letter a there exists at most one transition (p, a, q) ∈ T . Consequently the transition partial function δ can be can be viewed as δ : Q × A → Q. Function δ can be extended to δ : Q × A * → Q by δ(p, ua) = δ(δ(p, u), a), where u is a finite word and a a letter and δ(p, ǫ) = p. Then for all infinite word α there exists at most one path c of label α.

Example 1 Let A be the deterministic Büchi's automaton on alphabet A = {0, 1}, with states Q = {0, 1}, initial states I = {0}, final states F = {1} and transitions T = {(0, 0, 0), (0, 1, 1), (1, 0, 1), (1, 1, 1)}. Figure 1 gives the representation of A. This automaton recognizes the set

O = {α ∈ 2 ω | ∃m α(m) = 1}.
If we takes F = {0} then this automaton recognizes the complement of O :

Ǒ = {α ∈ 2 ω | ∀m α(m) = 0}.
Example 2 Let B be the deterministic Büchi automaton on alphabet A = {0, 1}, with states Q = {0, 1}, initial states I = {0}, final states F = {1} and transitions T = {(0, 0, 0), (0, 1, 1), (1, 0, 0), (1, 1, 1)} Figure 2 gives the representation of

B. Let Q = {α ∈ 2 ω | ∃m ∀n ≥ m α(n) = 0}. This automaton recognizes the complement of Q : Q = {α ∈ 2 ω | ∀m ∃n > m α(n) = 1}.
} Figure 3 gives the representation of

C. Let Q = {α ∈ 2 ω | ∃m ∀n ≥ m α(n) = 0}, Q is a countable dense subset of 2 ω The automaton C recognizes Q. 0 1 2 1 0 0,1 0
Fig. 3: A non deterministic automaton which recognizes the countable dense set

Q = {α ∈ 2 ω | ∃m ∀n ≥ m α(n) = 0} Definition 2 A Muller automaton A is a 5-tuple : A = A, Q, I, T, F , where A is a finite alphabet, Q is a finite set of states, I ⊂ Q is the set of initial states, T ⊂ Q × A × Q is the set of transitions and F ⊂ P(Q).
An infinite word α ∈ A ω is recognized by A if there is an infinite path c of label α so that Infinity(c) ∈ F.

Example 4 Let again B be the deterministic automaton of example 2 and take F = {{0}}. Then this automaton recognizes Q.

If we take F = {{1}, {0, 1}} then this automaton recognizes Q.

2.3 S1S : the monadic second order theory of one successor

We now define the terms, atomic formulas, and formulas of S1S the monadic theory of one successor. Let V be a set of variables, its elements noted by x, y, z... , the constant symbol 0 and a unary function symbol s (as successor). We define the set of the terms T by : i) A variable is a term. ii) 0 is a term. iii) if t ∈ T then s(t) ∈ T . Let P be another set of variables. Its variables are noted X , Y, Z... and two predicate symbols =, ∈. Atomic formulas are of the form t = t ′ or t ∈ X where (t, t ′ ) ∈ T 2 and X ∈ P.

Definition 3 A formula of S1S is defined as follows :

i) An atomic formula is in S1S.

ii) If φ ∈ S1S then ¬φ, ∀xφ, ∃xφ and ∀X φ, ∃X φ are in S1S, where x ∈ V, X ∈ P.

iii) If φ and ψ are in S1S, then φ ∧ ψ, φ ∨ ψ, φ ⇒ ψ and φ ⇔ ψ are in S1S.

The interpretation of these formulas is the following : the variables of V are interpreted as natural numbers, symbol 0 as 0 ∈ ω, symbol s as the successor function in ω, the variables of P as subsets of ω and the predicate symbols as equality relation and membership relation in ω. If each integer is assimilated to a singleton and each subset of ω to an infinite word over alphabet {0, 1}, then a S1S formula φ(X 1 , X 2 , ..., X n ), with X 1 , X 2 , ..., X n free variables defines an ω-language L φ ⊂ 2 N × . . .

2 N n .
An ω-language L is said definable in S1S if there exists a formula φ in S1S such that L = L φ .

ω-regular sets

Recall the following result [START_REF] Trakhtenbrot | Finite Automata[END_REF][START_REF] Perrin | Infinite words[END_REF] :

Theorem 3 for all ω-language L, the following assertions are equivalent :

i) L = 1≤i≤n A i B ω i where A i , B i are regular sets and n ∈ ω -{0}. ii) L = L ω (A), where A is a non deterministic Büchi automaton. iii) L = L ω (A), where A is a deterministic Muller automaton. iv) L is definable in S1S.
The family of languages which verify the equivalent conditions of the preceding theorem are usually call the ω-regular sets. We denote by Rec(A ω ) the class of ω-regular sets on alphabet A. Following Louveau 1987, we denote by Auto the family of ω-regular sets. ω-regular sets are denoted by ω regular expression [START_REF] Perrin | Infinite words[END_REF].

Example 5 α ∈ O ⇔ ∃m α(m) = 1 An ω regular expression for O is 0 * 1(0 + 1) ω α ∈ Ǒ ⇔ ∀m α(m) = 0 An ω regular expression for Ǒ is 0 ω α ∈ Q ⇔ ∃m ∀n ≥ m α(n) = 0 An ω regular expression for Q is (0 + 1) * 0 ω α ∈ Q ⇔ ∀m ∃n > m α(n) = 1
An ω regular expression for Q is (0 * 1) ω

3 ω-rational relations

In this section, we introduce ω-rational relations which extend the notion of ω-langages (see [START_REF] Frougny | Synchronized relations of finite and infinite words[END_REF][START_REF] Gire | Relation rationnelles infinitaires[END_REF][START_REF] Gire | Two decidability Problems for infinite words[END_REF][START_REF] Lindner | Algebraische Codierungstheorie -Theorie der sequentiellen Codierungen[END_REF]).

Definition 4 A Büchi transducer T is a 6-tuple : T = A, B, Q, I, T, F , where A and B are finite alphabets, Q is a finite set of states, I ⊂ Q is the set of initial states, T ⊂ Q × A * × B * × Q is the finite set of transitions and F ⊂ Q the set of final states. An (infinite) path c in T is an infinite word c = c(0)c(1)...c(n)... ∈ (Q × A * × B * × Q) ω such that ∀n ∈ ω c(n) ∈ T . So for each n, c(n) is of the form c(n) = (q n , u n , v n , q n+1
), with u n ∈ A * and v n ∈ B * This will be denoted by the following graphical notation of path : (α,β) is the label of the path c. A path c is said to be successful if q 0 ∈ I and Infinity(c) F = ∅, where Infinity(c) is still the set of states which appears infinitely many times in c. Let α ∈ A * ∪ A ω and β ∈ B * ∪ B ω , (α, β) is recognized by T if there is a successful path c in T of label (α, β).

c = q 0 u0,v0 ---→ q 1 u1,v1 ---→ q 2 u2,v2 ---→ . . . Let α = u 0 u 1 . . . u n . . . and β = v 0 v 1 . . . v n . . .,
Remark 2 A path c of label (α, β) is called admissible if α and β are both infinite words. In [START_REF] Frougny | Synchronized relations of finite and infinite words[END_REF] it is shown that for every finite Büchi transducer T , it is possible to construct another one T ′ so that every successful path in T ′ is admissible and the paths that are both successful and admissible are the same in T and T ′ . In the sequel of this paper all the labels (α, β) will be in A ω × B ω .

An ω-rational relation is a subset of A ω × B ω which is recognizable by a Büchi's transducer. An ω-rational function f : A ω → B ω is a function whose graph is an ω-rational relation. Recall that a left sequential function f : A * → B * is a function that can be realized by a deterministic automaton with output (sequential transducer). A left sequential function can be extended immediately to f :

A ω → B ω ∪ B * . If the image of f is in B ω
then this is an example of continuous ω-rational function. This is the case when the deterministic automaton with output realizing f output one letter when he read a letter. We call 1-sequential functions these functions and these functions will be used as strategy for player 2 later.

Example 6 Let T be the Büchi transducer with A = B = {0, 1}, states Q = {1, 2, 3, 4, 5}, initial states I = {1, 3, 4}, final states F = {1, 3, 5} and transitions T = {(1, (0, 0), 1), (1, (1, 1), 2), (2, (0, 0), 1), (2, (1, 1), 2), (3, (1, 1), 3), (4, (0, 0), 4), (4, (1, 1), 4), (4, (0, 1), 5), (5, (1, 0), 5)} Figure 4 gives the representation of T . This automaton recognizes the graph of function S :

2 ω → 2 ω defined by S(α) = α if α has infinitely many 0's, S(1 ω ) = 1 ω and S(u01 ω ) = u10 ω for all u ∈ 2 * . Let µ 2 : 2 ω -→ [0, 1] defined by µ 2 (α) = ∞ i=0 α(i) 2 i+1
. One can easily check that S(α) is the lexicographic maximum of the binary representations of µ 2 (α) for all α ∈ 2 ω . S is known as normalization in base 2. In fact for any Pisot number θ, normalisation in base θ is an ω-rationnal function( see Frougny [START_REF] Frougny | Numeration Systems. Chapter 8 of M. Lothaire, Algebraic Combinatorics on Words[END_REF]).

✁ ✂ ☎✄ ✆✂ ✆✄ ☎ ✆✄ ☎ ✂ ☎✄ ✆✂ ✝ ✆✄ ☎ ✞ ✆✄ ☎ ✂ ☎✄ ✆✂ ✟ ✂ ☎✄ ☎ ✆✄ ✆✂

Borel sets in Polish spaces

For all of the topological concepts introduced in this section we refer the reader to [START_REF] Kuratowski | Topology[END_REF][START_REF] Kechris | Classical Descriptive Set Theory[END_REF][START_REF] Perrin | Infinite words[END_REF][START_REF] Srivastava | A course on Borel Sets[END_REF].

Ordinals

For a short and comprehensive presentation of ordinals we refer the reader to Srivastava [START_REF] Srivastava | A course on Borel Sets[END_REF]. We say that two sets E and F have the same cardinal if there is a bijection from E to F . We say that two well-ordered sets E and F have the same ordinal if there is an order-preserving bijection from E to F . To each well-ordered set W we can associate a particular well-ordered set t(W ) called the type of W which is the ordinal associate to W . Results in the theory of ordinals use the axiom of choice and axiom of remplacement.

It is common in set theory to identify an ordinal with the set of its predecessors, i.e., α = {β | β < α} and to identify the finite ordinals with the natural numbers. Here are the first ordinals 0, 1 = {0}, 2 = {0, 1}, 3 = {0, 1, 2} . . . n = {0, 1, . . . , n -1} The successor of an ordinal α is the least ordinal > α. An ordinal is successor if it is the successor of some ordinal, and it is limit if it is not 0 or successor.

The first infinite ordinal is ω = {0, 1, 2, . . . , n, n + 1, . . .}, it is a limit ordinal, its successor is ω + 1 = {0, 1, 2, . . . , n, n + 1, . . . , ω}.

Next we have ω + 2,. . ., ω + n,. . . , ω + ω = ω.2,. . ., ω.3,. . ., ω.n,. . ., ω.ω = ω 2 , . . ., ω n , . . ., ω ω . An ordinal is countable if its cardinal is countable. All ordinals we have seen are small countable ordinals. Let ω 1 be the set of countable ordinals, one can show that ω 1 is an uncountable well-ordered set and that its cardinality is lower or equal to 2 N . The Continuum hypothesis says that the cardinality of ω 1 is equal to 2 N .

The Borel hierarchy

Borel subsets of a topological space X are obtained from open sets using complementation and countable unions. When X is metrizable we can define the hierarchy of Borel sets of finite rank : Definition 5 Let X be a metrizable space, for n ∈ ω-{0}, we define by induction classes

Σ 0 n (X), Π 0 n (X) and ∆ 0 n (X) : Σ 0 1 (X) = G(X) the class of open sets of X Π 0 n (X) = { Ǎ | A ∈ Σ 0 n (X)}, where Ǎ is the complement of A. Σ 0 n+1 (X) = {∪ m A m | A m ∈ Π 0 n (X), m ∈ ω} ∆ 0 n (X) = Σ 0 n (X) ∩ Π 0 n (X)
In particular, we have :

Π 0 1 is the class of closed sets. Σ 0 2 = F σ is the class of countable unions of closed sets. Π 0 2 = G δ is the class of countable intersections of open sets.
One can prove that :

Σ 0 n ∪ Π 0 n ⊂ ∆ 0 n+1
This gives us the following picture where any class is contained in every class to the right of it :

Σ 0 1 Σ 0 2 Σ 0 3 Σ 0 n ∆ 0 1 ∆ 0 2 ∆ 0 3 . . . ∆ n . . . Π 0 1 Π 0 2 Π 0 3 Π 0 n
The Borel hierarchy is also defined for transfinite levels ξ < ω 1 , but we shall not need them in the present study. For all n ∈ ω the classes Σ 0 n (X), Π 0 n (X), ∆ 0 n (X) are closed under finite unions and intersections, moreover Σ 0 n (X) is closed under countable unions, Π 0 n (X) closed under countable intersections and ∆ 0 n (X) closed under complement. All these classes are closed by inverse image by continuous functions.

Example 7 The set O is open but is not closed, i.e., O ∈ Σ 0 1 and O / ∈ Π 0 1 . We will see that the set Q is F σ but is not G δ , i.e., Q ∈ Σ 0 2 and Q / ∈ Π 0 2 .
Sets which are recognized by deterministic Büchi automaton are G δ . One can see this easily as a deterministic automaton gives a continuous function f : A ω → Q ω . Replace q / ∈ F by 0 and q ∈ F by 1. The set recognized by a deterministic Büchi automaton is the inverse image of Q by a continuous function.

Sets which are recognized by deterministic Müller automaton are boolean combinations of sets which are recognized by deterministic Büchi automaton, so they are boolean combinations of Π 0 2 sets hence ∆ 0 3 .

Polish spaces

A Polish space P is a separable topological space which admits a compatible metric d such as (P, d) is complete. A closed subset of a Polish space is Polish. An open subset of a Polish space is Polish. A G δ subset of a Polish space is Polish. This is not true for F σ . Recall the Baire theorem : Theorem 4 Let X be a complete space, the intersection of countably many dense open sets in X is dense. This is equivalent to say that in a complete space X, the union of countably many closed sets of empty interior has empty interior.

Lemma 5

The set Q with the relative topology induced by the one of R is not Polish.

Proof: (Saint Raymond) We have :

Q = n∈ω {q n }
a countable union of closed sets. Suppose Q was Polish then by the preceding theorem there must be an n such that {q n } has an nonempty interior, otherwise Q would have an empty interior, hence will be empty. But every {q n } has an empty interior because Q is dense in itself. Hence Q can't be Polish.

In fact by Baire's theorem, every countable dense subset of a Polish space is not Polish. As a G δ subset of a Polish space is Polish, every countable dense subset of a Polish space is not G δ .

Remark 3 It is well known (for a descriptive set theorist) that every Polish space is homeomorphic to a G δ set in a compact metric space. For example the Baire space ω ω is homeomorphic to

Q = {α ∈ 2 ω | ∀m, ∃n > m, α(n) = 1}. To see this, define an application ϕ : ω -→ 2 * by ϕ(n) = 0 n 1. Notice that ϕ(ω) = 0 * 1 is a regular prefix code. Extend ϕ in monoïd morphism ϕ : ω * -→ 2 * , ϕ(ω * ) = (0 * 1) * . Next extend ϕ in continuous one to one application called again ϕ : ω ω -→ 2 ω . We have ϕ(ω ω ) = (0 * 1) ω = Q. The set of infinite subsets of ω is homeomorphic to Baire space ω ω .
When P is an uncountable Polish space , Borel hierarchy is strict. In the sequel P will be A ω or A ω × B ω or [a, b] with a and b reals.

Analytic sets and coanalytic sets

There exists another hierarchy beyond the Borel one, called the projective hierarchy, which is obtained from the Borel hierarchy by successive applications of operations of projection and complementation. We need just the first level of this hierarchy. Let B ⊆ P × ω ω , we will call proj P (B) the projection of B onto P , that is, proj P (B) = {α ∈ P/∃β ∈ ω ω (α, β) ∈ B}.

A set C ⊆ P is called analytic if there is a Borel set B ⊆ P × ω ω such that C = proj P (B). A set C ⊆ P is coanalytic if its complement is analytic. The class of analytic sets in P (resp. coanalytic) is called Σ 1 1 (P ) (resp. Π 1 1 (P )). Borel sets are analytic and coanalytic sets. The famous theorem of Suslin says that in Polish space P , if B ⊆ P is analytic and coanalytic then B is Borel.

Existence of analytic sets which are not Borel is a kind of myth for descriptive set theorists. In 1905 Lebesgue said that the projection of Borel set in the plane was a Borel set. This was false as Suslin discovered in 1917. He called a projection of Borel set an analytic set. Here is the French evidence of Sierpinski [START_REF] Sierpinski | Les Ensembles Projectifs et Analytiques[END_REF] : "Par hasard j'étais présent au moment où Michel Souslin communiqua à M. Lusin sa remarque et lui donna le manuscrit de son premier travail". Büchi commented the equivalence of theorem 3 :"What looks like an analytic set (set recognized by a nondeterministic Büchi automaton) is in fact Borel set( a set recognized by a deterministic Müller automaton is a ∆ 0 3 set)" [START_REF] Büchi | Using determinancy of games to eliminate quantifers[END_REF]. An ω-rational relation is an analytic set of A ω × B ω .

Complete sets

Recall the notion of completeness with regard to reduction by continuous functions. Let Γ be a class of sets in P Polish We call C ⊆ P Γ-complete if C ∈ Γ and for any B ∈ Γ there exists a continuous function f :

P -→ P , such that B = f -1 (C).
Finding some simple examples of complete sets is an old tradition in descriptive set theory which goes back to Hurewicz [START_REF] Hurewicz | Relativ perfekte Teile von Punktmengen und Mengen[END_REF] ( see Louveau and Saint Raymond [START_REF] Louveau | Borel classes and closed games Wadge-type and Hurewicztype results[END_REF], Kechris [START_REF] Kechris | Classical Descriptive Set Theory[END_REF]). It turns out that some simple combinatorial examples of complete sets are recognized by automata.

Example 8 We will see that

O = {α ∈ 2 ω | ∃m α(m) = 1} is Σ 0 1 -complete, hence Ǒ = {α ∈ 2 ω | ∀m α(m) = 0} is Π 0 1 -complete. We will see that the set Q = {α ∈ 2 ω | ∃m ∀n ≥ m α(n) = 0} is Σ 0 2 -complete, hence Q = {α ∈ 2 ω | ∀m ∃n > m α(n) = 1} is Π 0 2 -complete.
In fact a countable dense subset of [0, 1] is Σ 0 2 -complete Hurewicz [START_REF] Hurewicz | Relativ perfekte Teile von Punktmengen und Mengen[END_REF], and this true in all uncountable Polish space. Here is some well known examples of coanalytic-complete sets : The set WO, as Well Order, that is the set of E ⊂ ω × ω such that E is the graph of Well ordered linear order, is

Π 1 1 -complete, Lusin Sierpinski (1923). The set K(Q) of compact sets of [0, 1] which are included in Q ⊂ R , is Π 1 1 -complete, Hurewicz [45]. The set DIFF of differentiable functions in C[0, 1] is Π 1 1 -complete, Mazurkievicz (1933)
. The set WF of well founded trees, that is trees on ω which have no infinite branches is Π 1 1complete.

The set NDIFF of continuous functions on [0, 1] which are nowhere differentiable functions in

C[0, 1] is Π 1 1 -complete, Mauldin (1979)
. Finkel showed in [START_REF] Finkel | On the topological complexity of infinitary rational relations[END_REF] that there exists an ω-rational relation which is

Σ 1 1 -complete. Wadge has proved (i) (ii) : For any n , C ⊆ ω ω is Σ 0 n -complete (resp. Π 0 n -complete) set iff C ∈ Σ 0 n \Π 0 n (resp. C ∈ Π 0 n \Σ 0 n ). Definition 6 Let L ⊂ A * we define Lim(L) = {α ∈ A ω | ∀n ∈ ω, ∃m ≥ n such that α[m] ∈ L}.
The following lemma is classical( see [START_REF] Landweber | Decision problem for ω-automata[END_REF], [START_REF] Lindner | Algebraische Codierungstheorie -Theorie der sequentiellen Codierungen[END_REF], [START_REF] Staiger | Sequential mappings of ω-languages[END_REF]).

Lemma 6 Let M ⊂ A ω then M is Π 0 2 if and only if there exists L ⊂ A * so that M = Lim(L). Example 9 Q = {α ∈ 2 ω | ∀m ∃n > m α(n) = 1} is Π 0 2 because Q = Lim(L)
with L a regular set denoted by the regular expression (0 + 1) * 1.

Q is not equal to Lim(L) because Q is not G δ .
This lemma is equivalent to the following. The set {α ∈

2 ω | ∀m, ∃n > m, α(n) = 1} is a Π 0 2
complete set [START_REF] Simonnet | Automate et théorie descriptive[END_REF], [START_REF] Staiger | the Cantor Space and the Baire Space, G δ \F s igma is a Single Wadge-Degree, an effective proof[END_REF] . In fact we have more : this set is strategically complete [START_REF] Louveau | Borel classes and closed games Wadge-type and Hurewicztype results[END_REF]. We will see it in the game section.

Baire's classes

Definition 7 Definition of Baire's classes for functions is recursive. Let X, Y be metrizable spaces and f : X → Y be a function.

i) f is of Baire class 0 if f is continuous.
ii) f is of Baire class (n + 1) if f is the pointwise limit of a sequence of Baire class n functions for each integer n ≥ 0.

The Lebesgue, Hausdorff, Banach theorem makes the connexion with the Borel hierarchy :

Theorem 7 Let X, Y be metrizable spaces with Y separable. Then for all n ≥ 2, f : X → Y is of Baire class n iff for all open V include in Y , f -1 (V ) is in Σ 0 n+1 (X)
. Remark 4 Note that this result holds for n = 1 if in addition X is separable and either X = A ω or Y = R.

Remark 5 If Y = B ω , as {uB ω |u ∈ B * } is a countable basis of clopen sets, it is equivalent to prove that f : X → Y is of Baire class n iff for all finite word u, f -1 (uB ω ) is in ∆ 0 n+1 (X). Lemma 8 An ω-rational function is of Baire class 2.

Proof: We have to shows that for all finite word u,

f -1 (uB ω ) is in ∆ 0 3 . But f -1 (uB ω ) = proj A ω (graph(f ) ∩ (A ω × uB ω )) We see that A ω × uB ω is in Rec((A × B) ω ). The family of ω-rational relation of A ω × B ω is closed by intersection with an ω-regular set of (A × B) ω and if R ⊂ A ω × B ω is an ω-rational relation then proj A ω (R) is an ω-regular set of A ω .
We have seen that an ω-regular set is a boolean combination of Π 0 2 sets, hence is a ∆ 0 3 set.

(i) Jean Saint Raymond has proved, that this valid for any uncountable Polish space.

(ii) See [START_REF] Kechris | Classical Descriptive Set Theory[END_REF] page 205 for a discussion of the statement :

Let C ⊆ ω ω , if C ∈ Π 1 1 \Σ 1 1 then C is Π 1 1 -complete.
Example 10 The characteristic function of Q ⊂ R, 1 Q is a classical example of Baire class two function which is not of Baire class one [START_REF] Baire | Oeuvres scientifiques[END_REF][START_REF] Dugac | [END_REF]. The function 1 Q is the pointwise limit of the sequence (f m ) m∈N where f m (x) = lim n→∞ cos 2m (n!πx). So 1 Q is of Baire class two. If 1 Q was a Baire class one function, then the inverse image of an open set by 1 Q will be a Σ 0 2 (R) set, hence the inverse image of a closed set by 1 Q will be a Π 0 2 (R) set. But as

1 -1 Q ({1}) = Q is not Π 0 2 (R), because Q is a countable dense subset, so 1 Q is not of Baire class one.
Let X and Y be metrizable spaces with Y compact, and f : X → Y , it is well known that f is continuous if and only if its graph is closed.

Proposition 9 Let f : A ω → B ω be a function of Baire class n, then its graph is Π 0 n+1 (A ω ×B ω ). Proof: First notice that if f (α) = β then ∀u ∈ B * , (β ∈ uB ω ⇒ f (α) ∈ uB ω ) and if f (α) = β then ∃u ∈ B * such that β ∈ uB ω and f (α) / ∈ uB ω . Thus : (α, β) ∈ graph(f ) ⇔ f (α) = β ⇔ [∀u ∈ Y * (β ∈ uB ω ⇒ f (α) ∈ uB ω )]
As f is of Baire class n, for any word

u in B * , {α ∈ A ω |f (α) ∈ uB ω } is in ∆ 0 n+1 (A ω ) and {β ∈ B ω |β ∈ uB ω } is in ∆ 0 1 (B ω ). Thus for all fixed u ∈ B * , {(α, β) ∈ A ω × B ω | (β ∈ uB ω ⇒ f (α) ∈ uB ω )} is in ∆ 0 n+1 (A ω × B ω ) and {(α, β) ∈ A ω × B ω | ∀u ∈ B * (β ∈ uB ω ⇒ f (α) ∈ uB ω )} is in Π 0 n+1 (A ω × B ω ).
When A and B are finite alphabets we have :

Proposition 10 Let f be a function f : A ω → B ω . If graph(f ) ∈ ∆ 0 2 (A ω × B ω ) then f is of Baire class 1. Proof: If graph(f ) ∈ ∆ 0 2 (A ω ×B ω ) then for all open U ⊂ B ω , graph(f )∩(A ω ×U ) ∈ ∆ 0 2 (A ω ×B ω ). As A ω and B ω are compact spaces, graph(f ) ∩ (A ω × U ) is K σ (countable unions of compact sets) and then f -1 (U ) is K σ as the continuous projection of graph(f ) ∩ (A ω × U ) on A ω .
Let cont(f ) denote the set of points of continuity of a function f . Proposition 11 Let X and Y be separable metric spaces and f : X → Y . Then cont(f ) is Π 0 2 (X). Proof: We define the oscillation of f at α by :

osc f (α) = inf{diam(f (U ))|U open containing α} where diam(E) is diameter of a set E. It is easy to see that osc f (α) = 0 iff f is continuous at α. Let X ε = {α ∈ X | osc f (α) < ε} we show that it is an open set. Let α be in X ǫ . (osc f (α) < ε) ⇒ (∃U open containing α so that diam(f (U )) < ε). Then ∀β ∈ U osc f (β) ≤ diam(f (U )) < ε. And X ǫ is open. So cont(f ) = {α ∈ X ω | osc f (α) = 0} = ∩ n>0 X 1/n is Π 0 2 (X).

An example

In this section we give an example of a function f such that graph(f ) is definable in S1S hence is of Baire class 2. One can easily see that graph(f ) ∈ Π 0 2 and the set of points of continuity of f is a dense open set (hence dense Π 0 2 ). However, f is not of Baire class 1. This example was constructed in 1996 by Tison and the first author and was unpublished. The idea of A. Louveau (1996), is the following : take the characteristic function of the Cantor set on the interval [0, 1]. The function is continuous on the complement of the triadic Cantor set, which is a dense open set. Since the graph of f is ∆ 0 2 set, it follows from proposition 10 that f is of Baire class 1. So we have to modify our function on the Cantor set to succeed. Now we will work on space

3 ω = {0, 1, 2} ω . The Cantor set is (0 + 2) ω α ∈ (0 + 2) ω ↔ ∀n(α(n) = 0 ∨ α(n) = 2)
and its complement is the dense open set (0 + 2) * 1(0

+ 1 + 2) ω α ∈ (0 + 2) * 1(0 + 1 + 2) ω ↔ ∃n α(n) = 1
First define g : {0, 1} ω -→ {0, 1} ω by : g(α) = α, if α ∈ (0 * 1) ω (α has infinitely many 1's).

If α ∈ (0 + 1) * 10 ω (α has a non zero finite number of 1's) replace each letter of α by 0 except the last 1 which remains the same, this gives g(0 k0 10 k1 . . . 10 kp 10 ω ) = 0 k0+k1+...+kp+p 10 ω .

Finally if α = 0 ω , g(0 ω ) = 1 ω .

Figure 5 shows a deterministic Büchi automaton which recognizes graph(g). This implies that graph(g) ∈ Π 0 2 . We will see that g has no point of continuity and is not of Baire class 1. If α has infinitely many 1's, α = 0 k0 10 k1 10 k2 1 . . . 10 kp . . ., where for each p , k p ≥ 0, sequence α n = 0 k0 10 k1 10 k2 1 . . . 10 kn 10 ω tends to α. But g(0 k0 10 k1 10 k2 1 . . . 10 kn 10 ω ) = 0 k0+k1+...+kn+n 10 ω and sequence g(α n ) converges to 0 ω . Suppose now that α has a non zero finite number of 1's, α = 0 k0 10 k1 . . . 10 kp 10 ω with p ≥ 0. Sequence α n = 0 k0 10 k1 . . . 10 kp 10 n 10 ω tends to α. We have g(α) = 0 k0+k1+...+kp+p 10 ω , g(0 k0 10 k1 . . . 10 kp 10 n 10 ω ) = 0 k0+k1+...+kp+p+n+1 10 ω and sequence g(α n ) converges to 0 ω . If α = 0 ω , α is limit of the sequence α n = 0 n 10 ω . g(0 ω ) = 1 ω , g(0 n 10 ω ) = 0 n 10 ω and the sequence g(α n ) converges to 0 ω . One can also see that g -1 (011(0 + 1) ω ) = 011(0 * 1) ω , which is Π 0 2 but not Σ 0 2 . So g is not of Baire class one. Now we can define our function f : {0, 1, 2} ω -→ {0, 1} ω by : f (α) = 0 ω if α ∈ (0 + 2) * 1(0 + 1 + 2) ω ( α has at least one 1) f (α) = α if α ∈ (0 * 2) ω (α has no 1 and infinitely many 2's) f (α) = 0 n 20 ω if α ∈ (0 + 2) * 20 ω (α has no 1 and a non zero finite number of 2's) and satisfies, α ∈ (0 + 2) n 20 ω f (α) = 1 ω if α = 0 ω . One can see in figure 6 that graph(f ) is recognized by a deterministic Büchi automaton. This implies that graph(g) ∈ Π 0 2 .

✁ ✄✂ ☎ ✆ ✄✂ ☎ ✄✂ ✝✁ ✄✂ ✝✁ ✞ ✄✂ ☎ ✠✟ ✡✆ ☛✂ ☎ ✆ ✝✂ ☎ ✆ ✝✂ ☎ ☞ ✆ ✝✂ ✌✆ ✄✂ ☎ ✍ ✄✂ ☎ ✆ ✝✂ ✌✆ ✆ ✝✂ ✌✆ ✎ ✆ ✝✂ ✌✆ ✆ ✝✂ ✌✆ ✏ ✁ ✌✂ ☎ ✁ ☎✂ ☎ ✁ ☎✂ ☎ ✄✂ ☎ ✠✟ ✁ ✌✂ ☎ ✠✟ ✆ ✝✂ ✑ ✒ ✄✂ ☎ ✆ ✝✂ ✌✆ ✄✂ ☎
Fig. 6: a dense open set of points of continuity

Notice that f is not of Baire class 1 because f -1 (22 (0 + 1 + 2) ω ) = 22(0 * 2) ω which is Π 0 2 but not Σ 0 2 . Moreover f is continuous because it is constant on dense open set (0 + 2) * 1(0 + 1 + 2) ω .
It is easy to see that f has no point of continuity on (0 + 2) ω . The proof is similar to that concerning g, we just have to replace 1 by 2.

In his thesis (1899) Baire has proved that a function is of Baire class 1 if and only if for every non empty closed set F the restriction of this function to F has a point of continuity. Our example is ω-rational function which is not of Baire class 1 and we have found an ω-regular closed set F = (0 + 2) ω such that restriction of f to F has no point of continuity. We will see that our example is generic. If f is an ω-rational function which is not Baire class 1, then there exists a closed F , recognized by a Büchi automaton, such that restriction of f to F has no point of continuity.

The next sections will be devoted to the classical proof of Baire's result.

Differences hierarchy

In this section, we introduce the class of differences. Let ξ be an ordinal. Any ξ can be written in a unique way ξ = λ + n with λ a limit ordinal or 0 and n ∈ ω. Parity of ξ is by definition that of n. Definition 8 Let X be a set, ξ an ordinal and < B η : η < ξ > an increasing sequence of subsets of X :

D ξ (< B η : η < ξ >) = {x ∈ X|∃η < ξ, x ∈ B η and if η 0 = inf({η|x ∈ B η })
the parity of ξ and of η 0 are differents } Then :

D 1 (< B 0 >) =B 0 D 2 (< B 0 , B 1 >) =B 1 \B 0 D 3 (< B 0 , B 1 , B 2 >) =(B 2 \B 1 ) ∪ B 0 . . . D ω (< B n : n ∈ ω >) = ∪ n∈ω (B 2n+1 \B 2n ) D ω+1 (< B n : n ≤ ω >) =(B ω \ ∪ n∈ω B n ) ∪ (∪ n∈ω (B 2n+2 \B 2n+1 )) ∪ B 0
Let Γ be a family of subsets of X, D ξ (Γ) will be the family of all D ξ (< B η : η < ξ >) where < B η : η < ξ > is an increasing sequence of length ξ of elements of Γ. In the sequel we will be particularly interested in the classes D ξ (Σ 0 1 ) and their dual classes Ďξ (Σ 0 1 ) = {B | B ∈ D ξ (Σ 0 1 )}, where ξ is a countable ordinal. 7 gives a deterministic Büchi automaton which recognizes

Example 11 Let O k = {α ∈ 2 ω | ∃n 1 , ∃n 2 , . . . ∃n k , n 1 < n 2 < . . . < n k , α(n 1 ) = α(n 2 ) = . . . = α(n k ) = 1} with k > 0, O k is an ω-regular open set. We have an increasing sequence of dense open sets O n ⊂ O n-1 ⊂ O n-2 . . . O 2 ⊂ O 1 and D n (< O n , . . . , O 1 >) is a D n (Σ 0 1 ) which in fact is a D n (Σ 0 1 )-complete set. Figure
(O 1 \O 2 ) ∪ O 3 .
Example 12 Let G n be the following sequence of decreasing dense G δ sets :

G 1 = ((0 + 1) * 1) ω = (0 * 1) ω α ∈ G 1 ⇔ α has an infinite numbers of 1. G 2 = ((0 + 1) * 11) ω α ∈ G 2 ⇔ α has an infinite numbers of 11. ✁ ✁ ✂ ✁ ✄ ✁ ✆☎ ✁
G 3 = ((0 + 1) * 111) ω α ∈ G 3 ⇔ α has an infinite numbers of 111. . . . G n = ((0 + 1) * 1 n ) ω α ∈ G n ⇔ α has an infinite numbers of 1 n
Taking the complement of these sets we obtain an increasing sequence

F 1 ⊂ F 2 ⊂ . . . F n-1 ⊂ F n of meager F σ sets, D n (< F 1 , . . . , F n >) is a D n (Σ 0 2 ) which in fact is a D n (Σ 0
2 )-complete set. Figure 8 gives a deterministic Müller automaton which recognizes

(F 3 \F 2 ) ∪ F 1 , with F = {{0}, {0, 1, 2}}.
The loops accessible from the initial state are L = {{0}, {0, 1}, {0, 1, 2}, {0, 1, 2, 3}, {3}}, these are essential loops of the automaton [START_REF] Wagner | On ω -regular Sets[END_REF]. Classify these essential loops in It is well known that in an uncountable Polish space hierarchy of D ξ (Σ 0 η ), ξ < ω 1 , η < ω 1 is strict (see [START_REF] Kechris | Classical Descriptive Set Theory[END_REF] ).

L + = {{0}, {0, 1, 2}} and L -= {{0, 1}, {0, 1, 2, 3}, {3}}. We have the inclusion {0} ⊂ {0, 1} ⊂ {0, 1, 2} ⊂ {0, 1, 2, 3}, that is to say {+} ⊂ {-} ⊂ {+} ⊂ {-}. But we have not some {-} ⊂ {+} ⊂ {-} ⊂ {+}
Lemma 12 Inclusion D ξ (Σ 0 1 ) ⊂ ∆ 0 2 holds, for all countable ordinal ξ. Proof: First note that Ďξ (Σ 0 1 ) ⊂ D ξ+1 (Σ 0 1 ). So, we have only to prove that D ξ (Σ 0 1 ) ⊂ Σ 0 2 . This is clear since differences B 1 \B 0 of open sets are Σ 0 2 and Σ 0 2 is closed under countable unions.

Haussdorff's derivation

Recall that A ω has a countable basis for the topology. Thus we can extract countable covering from each open covering. As a consequence, if ω 1 is the first non countable ordinal, and if (F ξ ) ξ<ω1 is a decreasing sequence of closed sets, it is stationary from a certain rank on, i.e., ∃η < ω 1 such that F ξ = F η , ∀ξ ≥ η. For more details we refer to [START_REF] Kechris | Classical Descriptive Set Theory[END_REF].

We now define Hausdorff's derivation (see [START_REF] Kuratowski | Topology[END_REF]).

Definition 9 Let M and N be two subsets of A ω . Sequence of closed sets (F ξ ) ξ<ω1 is defined by transfinite induction.

F 0 = A ω F ξ+1 = F ξ ∩ M ∩ F ξ ∩ N F λ = ∩ ξ<λ F ξ , if λ is a limit ordinal
The sequence (F ξ ) ξ<ω1 is a decreasing sequence of closed sets, so we know that there exists a smaller η < ω 1 such that

F η = F η ∩ M ∩ F η ∩ N . Lemma 13 Let F be a closed set. Then F = F ∩ M ∩F ∩ N if and only if F = F ∩ M = F ∩ N . Proof: Indeed, if F = F ∩ M ∩ F ∩ N then F ⊂ F ∩ M . Moreover F ∩ M ⊂ F and F ∩ M ⊂ F since F is closed. Lemma 14 F η is the largest closed set such that F = F ∩ M ∩ F ∩ N . Proof: Let F be a closed set such that F = F ∩ M ∩ F ∩ N . We will show that F ⊂ F η by transfinite induction. We have F ⊂ F 0 . If F ⊂ F ξ then F ∩ M ⊂ F ξ ∩ M , so F = F ∩ M ⊂ F ξ ∩ M . Similarly F = F ∩ N ⊂ F ξ ∩ N thus F ⊂ F ξ ∩ M ∩ F ξ ∩ N = F ξ+1 . If λ is a limit ordinal, and if ∀ξ < λ, F ⊂ F ξ ∀ξ < λ then F ⊂ ∩ ξ<λ F ξ = F λ .
We define the following sequences (M ξ ) ξ<ω1 and (N ξ ) ξ<ω1 :

M 0 = M N 0 = N M ξ+1 = M ξ ∩ N ξ N ξ+1 = N ξ ∩ M ξ M λ = ∩ ξ<λ M ξ N λ = ∩ ξ<λ N ξ if λ is a limit ordinal. Lemma 15 ∀ξ < ω 1 , M ξ = M ∩F ξ and N ξ = N ∩F ξ . In particular, if η is the smallest countable ordinal such that F η = F η ∩ M = F η ∩ N , then η is also the smallest countable ordinal such that M η = N η .
Proof: We argue again by a transfinite induction.

For η = 0 we have

M 0 = M = M ∩ A ω = M ∩ F 0 , and also N 0 = N ∩ F 0 . If M ξ = M ∩ F ξ and N ξ = N ∩ F ξ , then M ξ+1 = M ξ ∩ N ξ = M ∩ F ξ ∩ N ∩ F ξ = M ∩ F ξ ∩ M ∩ F ξ ∩ N ∩ F ξ .
Corollary 18 Let M and N be two subsets of A ω and let F η be the biggest closed set so that

F η = F η ∩ M = F η ∩ N .
Then M and N can be separated by a ∆ 0 2 set iff F η = ∅. Proof: In the proof of theorem 17 we showed that if Hausdorff's derivation stops to the empty set then M and N are separated by a ∆ 0 2 . Conversely, if M and N are separated by a D ζ (Σ 0 1 ) set C for some ζ < ω 1 , we can operate the Hausdorff derivation on C and Č. As C and Č are disjoint Π 0 2 sets this derivation goes on to the empty set, as the derivation on M and N . Our proof is directly extracted from Kuratowski [START_REF] Kuratowski | Topology[END_REF] and documents of Louveau. The result is true in uncountable Polish spaces. Our originality comes from lemma 16 ; this is in such a form that the first author discovered this problem [START_REF] Arnold | Comportement de Processus[END_REF]. One can see how automata can be used to analyse problems of parallelism in [START_REF] Bergeron | An automated analysis of Ping-Pong Interactions in E-mail Services[END_REF]. Instead of lemma 16, a descriptive set theorist would use there Baire's theorem : a countable intersection of dense open set is dense. If M and N are two disjoints Π 0 2 and if F is a non empty closed set such that F = F ∩ M ∩ F ∩ N , then F is complete as a closed set in complete space A ω . Sets F ∩ M and F ∩ N are G δ in F , so they cannot be both dense since they are disjoint. 9 Baire's theorem Definition 10 A set E is called nowhere dense if its closure E has an empty interior. A set E is called meager if it is included in a countable union of nowhere dense sets.

Baire's theorem asserts that in a polish space [START_REF] Perrin | Infinite words[END_REF] a countable intersection of dense open sets is still dense or equivalently that a countable union of nowhere dense closed sets has empty interior. We have seen that for any function f , the set of discontinuity points of f is in Σ 0 2 (X) set. In the case of a Baire class 1 function, we have more.

Proposition 19 Let X and Y be two separable metric spaces and f : X → Y a Baire class 1 function. The set of discontinuity points of f is a meager set in Σ 0 2 (X). Proof:

Let (V X n ) (resp (V Y n )) be a countable basis of X (resp Y ). A point α ∈ X is a dis- continuity point of f if there exists n such that f (α) ∈ V Y n and f (V X m ) V Y n for each m, i.e. α ∈ f -1 (V Y n ) but not in its interior int(f -1 (V Y n )). Thus the set of discontinuity points of f is ∪ n∈ω f -1 (V Y n )\int(f -1 (V Y n )).
As f is Baire class 1, all these sets are Σ 0 2 (X) and have empty interior : they are all meager and a countable union of meager sets is still meager.

Theorem 20 Let P be a Polish space, Y a separable metric space and f : P → Y . The following statements are equivalent :

(i) f is Baire class 1.
(ii) For all nonempty closed set F ⊂ P , the restriction f |F of f to F has a point of continuity.

Proof: (i) ⇒ (ii) Set F is a closed set of a Polish space so F is Polish too. Since f is Baire class 1, so is f |F , thus, by proposition 19, its discontinuity points form a meager subset of F , hence by Baire category theorem, cannot be equal to

F . (ii) ⇒ (i) Suppose that f is not Baire class 1. There exists an open subset U of Y such that f -1 (U ) / ∈ Σ 0 2 (X).
As Y is a metric space, U can be writen as a countable union of closed sets U = ∪ n≥0 H n . Let H be the complement of U in Y . Suppose that for each n there exists A n ∈ ∆ 0 2 which separates f -1 (H n ) from f -1 (H). Then :

f -1 (U ) = ∪ n≥0 f -1 (H n ) = ∪ n≥0 A n
and f -1 (U ) will be Σ 0 2 . So there exists an n such that f -1 (H n ) and f -1 (H) can't be separated by a ∆ 0 2 set. We now apply Hausdorff's derivation on f -1 (H n ) and f -1 (H). Let F be the biggest closed set such that

F = F ∩ f -1 (H n ) = F ∩ f -1 (H)
. By corollary 18, F is not empty and we will show that f has no point of continuity in

F . Let α ∈ cont(f |F ). If f (α) / ∈ H, as H is closed we can find an open set B α in F containing α such that f (B α ) ∩ H = ∅. This contradicts density of f -1 (H) in F thus f (α) ∈ H. By the same argument f (α) ∈ H n , but H ∩ H n = ∅. So f |F has no point of continuity.
Example [START_REF] Boasson | Adherences of languages[END_REF] We have seen that the characteristic function of

Q ⊂ R, 1 Q is of Baire class two.
Using the previous theorem we can see that 1 Q is not Baire class one since it's nowhere continuous.

Application to automata theory

Lemma 21 Let M and N be two languages in Rec(A ω ). Then Hausdorff 's derivation on M and N stops in a finite number of steps, i.e.

∃n ∈ ω such that F n = F n ∩ M = F n ∩ N.
Proof: Let A (Resp. B) be a deterministic Müller automaton which recognizes M (Resp. N). Construct the cartesian product A × B, this is also a deterministic automaton. Compute the essential loops of the product and classify them in L A , L B , where L A (Resp. L B ) is the set of essential loops such that projection on states of A (Resp. B) is a positive essential loop of A (Resp. B), see example 12. Note that L A , L B are disjoint if and only if M and N are disjoint. Let α in M , then there exists a essential loop F which recognizes α, and one can see that α in M is in the closure of N if and only if a loop of L B is accessible from the loop F in L A . Process as follows : eliminate from L A (Resp. L B ) loops from which every loop in L B (Resp. L A ) is inaccessible, and iterate the work. As there is a finite number of loops, the process will stop in a finite number of steps. At the end, if L A and L B are not empty, then from every loop in L A (Resp. L B ) you can access to some loop in L B (Resp. L A ).

Example 14 Let Q 0 the subset of 2 ω of infinite words with finite even number of 1 and Q 1 the subset of 2 ω of infinite words with finite odd number of 1. This two sets are dense, Σ 0 2 -complete sets. The Hausdorff 's derivation stops after one iteration as Rec(A ω ) are separated by a ∆ 0 2 set. Moreover if they are separated by a ∆ 0 2 set, they are separated by an ω-regular ∆ 0 2 set, i.e., a finite difference of ω-regular open sets.

F 0 = 2 ω and F 1 = Q 0 2 ω = Q 0 2 ω = 2 ω = F 0 .

Corollary 22 One can decide if two langages in

Proof: Let M and N two languages in Rec(A ω ). Using corollary 18, M and N are separated by a ∆ 0 2 set iff Hausdorff's derivation stop to the empty set, and by lemma 21 it comes in a finite number of steps. By closure property of ω-regular sets, the F n which appear in Hausdorff's derivation are ω-regular and emptyness problem is decidable for ω-regular sets.

Corollary 23 Let f : A ω → B ω be an ω-rational function. If f is not Baire class 1 then there exists a nonempty closed set F which is recognizable by a Büchi automaton such that f restricted to F has no point of continuity.

Proof: If f is not Baire class 1 then there exists u ∈ B * such that f -1 (uB ω ) / ∈ ∆ 0 2 (X). So there exists v ∈ B * with |u| = |v| such that f -1 (uB ω ) and f -1 (vB ω ) cannot be separated by a ∆ 0 2 (X) set. Thus, as in the proof of theorem 20, the Hausdorff derivation on f -1 (uB ω ) and f -1 (vB ω ) produces, in finite time, a closed set F such that f |F has no point of continuity. As f -1 (uB ω ) and f -1 (vB ω ) are recognizable by a Büchi automaton so is F by closure properties of the family Rec(A ω ).

Games

For this section we refer the reader to Hurewicz [START_REF] Hurewicz | Relativ perfekte Teile von Punktmengen und Mengen[END_REF], Lusin [START_REF] Lusin | Leçons sur les Ensembles Analytiques et leurs Applications[END_REF], Sierpinski [START_REF] Sierpinski | Les Ensembles Projectifs et Analytiques[END_REF], Büchi [START_REF] Büchi | Solving sequential condition by finite-state strategies[END_REF], Landweber [START_REF] Landweber | Decision problem for ω-automata[END_REF] , Trakhtenbrot Barzdin [100], Wadge [START_REF] Wadge | Degrees of complexity of subsets of the Baire space[END_REF]104,105], Saint Raymond [START_REF] Raymond | Boréliens à coupe K σ[END_REF], Lindner Staiger [START_REF] Lindner | Algebraische Codierungstheorie -Theorie der sequentiellen Codierungen[END_REF], Wagner [START_REF] Wagner | On ω -regular Sets[END_REF], Moschovakis [START_REF] Moschovakis | Descriptive Set Theory[END_REF], Louveau [START_REF] Louveau | Ensemble Analytiques et Boréliens dans les Espaces Produits[END_REF][START_REF] Louveau | A separation theorem for Σ 1 1 sets[END_REF][START_REF] Louveau | Some results in the Wadge Hierarchy of Borel Sets[END_REF], Kechris Louveau [48], Kechris Louveau Woodin [START_REF] Kechris | The Structure of σ-ideals of Compact Sets[END_REF], Louveau Saint Raymond [START_REF] Louveau | Borel classes and closed games Wadge-type and Hurewicztype results[END_REF], Staiger [START_REF] Staiger | Sequential mappings of ω-languages[END_REF], Saint Raymond [START_REF] Raymond | Classification de Wadge. Note d'exposé[END_REF], Barua [START_REF] Barua | Hausdroff-Kuratowski hierarchy of ω -regular languages and a hierarchy of Muller automata[END_REF], Weirauch [START_REF] Weihrauch | The lowest Wadge degrees of subsets of the Cantor space[END_REF], Staiger Weirauch [START_REF] Staiger | the Cantor Space and the Baire Space, G δ \F s igma is a Single Wadge-Degree, an effective proof[END_REF], Simonnet [START_REF] Simonnet | Automate et théorie descriptive[END_REF][START_REF] Simonnet | Un théorème de séparation sur les ensembles rationnels de mots infinis[END_REF], Hertling Weirauch [START_REF] Hertling | On the Topological Classification of Degeneracies[END_REF], Kechris [START_REF] Kechris | Classical Descriptive Set Theory[END_REF], Selivanov [START_REF] Selivanov | Fine hierarchy of regular ω-languages[END_REF], Srivastava [START_REF] Srivastava | A course on Borel Sets[END_REF], Carton Perrin [22], Duparc [START_REF] Duparc | Wadge Hierarchy and Veblen Hierarchy : Part1 : Borels Sets of Finite Rank[END_REF], Duparc Finkel Ressayre [26], Perrin Pin [START_REF] Perrin | Infinite words[END_REF].

Büchi Landweber and Martin

Games are useful in descriptive set theory. They allow to give alternative proofs of some theorems like Cantor Bendixon theorem and Wadge theorem :

For any n , C ⊆ ω ω is Σ 0 n -complete (resp. Π 0 n -complete) set iff C ∈ Σ 0 n \Π 0 n (resp. C ∈ Π 0 n \Σ 0 n ).
Definition 11 A game in A ω × B ω between two players I and II can be defined as follows : Player I plays α(0) ∈ A, then player II plays β(0) ∈ B, I plays α(1) ∈ A, and so on. The result of the game is the couple of infinite words (α, β) of A ω × B ω .

Let G be a subset of A ω × B ω . Player II wins the game if (α, β) is in G.

Definition 12 We have :

-A strategy for player I is an application φ : B * → A. Intuitively I plays following φ :

α(0) = φ(ǫ) =, α(1) = φ(β(0)), α(2) = φ(β(0)β(1)), etc.
The application φ can be extended on infinite words in a continuous application (1-lipschitz) 1)) . . . φ(β(0)β(1) . . . β(n)) . . .

ψ : A ω → B ω by φ(β) = φ(ǫ)φ(β(0))φ(β(0)β(
-A strategy for player II is an application ψ : A + → B. Intuitively II plays following ψ : β(0) = ψ(α(0)), β(1) = ψ(α(0)α( 1)), β(2) = ψ(α(0)α(1)α( 2)), etc. The application ψ can be extended on infinite words in a continuous application (1-lipschitz) ψ : A ω → B ω by : ψ(α) = ψ(α(0))ψ(α(0)α( 1)) . . . ψ(α(0)α(1) . . . α(n)) . . .

A strategy φ for player I is a winning strategy if for any β in B ω (φ(β), β) is not in G. A strategy ψ for player II is a winning strategy if for any α in A ω (α, ψ(α)) is in G.

Definition 13 A game is called determined if one of the two players has a winning strategy.

It is well known that Borel's games are determined : Martin theorem [START_REF] Kechris | Classical Descriptive Set Theory[END_REF]. Sometimes the proofs using games can be adapted to automata theory thanks to Büchi Landweber's theorem [START_REF] Barzdin | Finite Automata, Behaviour and Synthesis[END_REF][START_REF] Perrin | Infinite words[END_REF][START_REF] Simonnet | Un théorème de séparation sur les ensembles rationnels de mots infinis[END_REF][START_REF] Simonnet | Automates d'arbres infinis et choix borélien[END_REF] Theorem 24 [START_REF] Büchi | Solving sequential condition by finite-state strategies[END_REF] If the set G is an ωregular subset of A ω × B ω , one of the players have a winning automaton strategy : either player I has a winning strategy φ such that the tree φ is a rational tree, or either player II has a winning strategy ψ which is a 1-sequential function. There is an algorithm which, given an ωregular set G, (1) determines which player has a winning strategy, and (2) constructs a winning automaton strategy. In particular if one of the players has a winning strategy, he also has a winning automaton strategy [START_REF] Trakhtenbrot | Finite Automata[END_REF][START_REF] Büchi | Solving sequential condition by finite-state strategies[END_REF].

Wadge Game

Let X ⊂ A ω , Y ⊂ A ω , in the Wadge game G(X, Y ) player II wins iff (α ∈ X ⇔ β ∈ Y ), that is to say the winning set for II is G = (X × Y ) ( X × Y ). A winning strategy for II gives a continuous function ( a Lipschitz map) ϕ such that ϕ -1 (Y ) = X. A winning strategy for I gives a continuous function ( a Lipschitz map) ψ such that ψ -1 ( X) = Y . If X and Y are Borel, Wadge game is determined so we have the dichotomy : either there exists ϕ continuous such that ϕ -1 (Y ) = X either there exists ψ continuous such that ψ -1 ( X) = Y .

Wadge's hierarchy, Wagner's Hierarchy, Louveau's hierarchy

Let X ⊂ A ω , Wadge has defined the class of Wadge of X by :

[X] W = {Y ⊂ A ω | ∃ϕ : A ω -→ A ω continuous Y = ϕ -1 (X)}
The notation W on the right gives in French : W A Droite. WADge has given a complete description of all Wadge classes of Borel set. We have

[O] W = Σ 0 1 , [Q] W = Σ 0 2 . Let Γ be a class of Wadge then Γ = { X | X ∈ Γ} is the class dual to Γ, and ∆(Γ) = Γ ∩ Γ, if Γ = Γ then Γ is a selfdual class and if Γ = Γ then Γ is a nonselfdual class. The classes Σ 0 ξ , Π 0 ξ , D η (Σ 0 ξ ), ξ < ω 1 , η < ω 1 are examples of nonselfdual Wadge classes of Borel sets.
Let X ⊂ Rec(A ω ), Wagner has defined the class of Wagner of X by :

n ← 0 φ(u) = 0 if u ∈ T n 1 if u / ∈ T n and n ← n + 1
Let (α, φ(α)) be a result of the game.

-If α is in U , there exists n so that α is in

F n = [T n ].
Then for all m in ω, α[m] is in T n . So there exists m 0 so that for all m ≥ m 0 , φ(α[m]) = 0 and φ(α) is in Q : II wins. -If α is not in U then for all n and m in ω, there exists m ≥ m so that α[ m] is not in T n i.e.

the sequence of finite words (α[m]) m∈ω leaves any tree T n in finite time. Then φ(α) has an infinite number of 1, so φ(α) is not in Q and II wins.

In fact using Martin theorem and Wadge game every F σ set which is not a G δ set is Σ 0 2 (A ω )strategically complete. And using Büchi Landweber theorem we have Σ 0 2 ∩ Auto = Σ 0 2 (Auto).

Separation games

In October 1984 Louveau was presenting joint work of his and Saint Raymond in the seminary of theory of effective borel sets. The title of the talk was "Jeux de Mistigri (Mistigri Games)". This was a sort of Wadge game, a separation game. Let Y and Z be two analytic disjoint subsets of ω ω .

In a first Game Player II wins the game iff (α Note that these theorems hold for all classes of Wagner's hierarchy which is of type order the ordinal of ω ω . These results where presented to Louveau in 1987 and appear in [START_REF] Simonnet | Un théorème de séparation sur les ensembles rationnels de mots infinis[END_REF][START_REF] Simonnet | Automates d'arbres infinis et choix borélien[END_REF]. R. Barua solves the case of the D n (Σ 0

∈ O ⇒ β ∈ Y and α ∈ Ǒ ⇒ β ∈ Z).
2 ) classes with a proof without games [START_REF] Barua | Hausdroff-Kuratowski hierarchy of ω -regular languages and a hierarchy of Muller automata[END_REF]. Separation games appear in Van Wesep [101]. The game where Player II wins if Kechris Louveau Woodin [50,[START_REF] Kechris | Descriptive Set Theory and the Structure of Sets of Uniqueness[END_REF][START_REF] Kechris | Classical Descriptive Set Theory[END_REF] to give new proof of the old Hurewicz's theorem [START_REF] Hurewicz | Relativ perfekte Teile von Punktmengen und Mengen[END_REF] :

(α ∈ Q ⇒ β ∈ Y and α ∈ Q ⇒ β ∈ Z) is used in

Mistigri Couleur

Van Wesep and Steel Games [START_REF] Van | Wesep Separation principes and the axiom of determinateness[END_REF][START_REF] Steel | Determinatenes and the separation property[END_REF] were used to study structural properties of Wadge classes of Borel sets like separation property. A Wadge class Γ has the separation property if for any pair X, Y of disjoints sets in Γ there exists Z in ∆(Γ) which separate X from Y . In fact for each pair of nonselfdual Γ, Γ Wadgeclass of Borel sets then exactly one of the classes has the separation property. And if Γ doesn't have the separation property then one can find a simple pair X, Y of disjoints sets in Γ such that X can't be separated from Y by a set in ∆(Γ). Another very interesting property is the norm property, in [START_REF] Louveau | Les propriétés de réduction et de norme pour les classes de Boreliens[END_REF] Louveau and Saint Raymond study norm property of Borel Wadge classes. The classes Σ 0 ξ , D η (Σ 0 ξ ) , ξ < ω 1 , η < ω 1 , and Π 1 1 have the norm property, and the D n (Σ 0 1 (Auto)), D n (Σ 0 2 (Auto)) have the norm property [START_REF] Simonnet | Automate et théorie descriptive[END_REF]. If a class Γ has a norm property then Γ has the reduction property [START_REF] Louveau | Les propriétés de réduction et de norme pour les classes de Boreliens[END_REF] that is to say for all X, Y in Γ one can find

X ′ , Y ′ in Γ such that X ∪ Y = X ′ ∪ Y ′ and X ′ ∩ Y ′ = ∅.
Moreover if Γ has the reduction property then Γ has the separation property. For example we have seen that the classes Π 0 2 , Π 0 2 (Auto) have the separation property ; in fact this is true because the classes Σ 0 2 , Σ 0 2 (Auto) have the reduction property. The reduction property of classes Σ 0 ξ is used to prove the Lebesgue, Hausdorff, Banach's theorem :

Theorem 30 Let X, Y be metrizable spaces with Y separable. Then for all ξ ≥ 2, f : X → Y is of Baire class ξ iff for all open V include in Y , f -1 (V ) is in Σ 0 1+ξ (
X). Remark 6 Note another time that this result holds for n = 1 if in addition X is separable and either

X = A ω or Y = R.
The proof use finite valued Borel functions, finite Borel partition. We know four descriptions of Borel Wadge classes : The one of Wadge(Descriptive Set Theorist) [104] is useful for a Computer Scientist (DST : Hello this set is Γ-complete and we give you a proof of that. Do you know countable choice and fundamental sequences ? CS : Thank you, I will try to find some device to recognize this Γ-complete set. Is this the simplest one ? What is countable choice ? Do I use it ? Do you think I can recognize this Γ-complete set with a Muller tree automaton ? DST : what is a Muller tree automaton ?). The one of Louveau [START_REF] Louveau | Some results in the Wadge Hierarchy of Borel Sets[END_REF] is useful to study structural properties of classes, Selivanov [START_REF] Selivanov | Fine hierarchy of regular ω-languages[END_REF] uses this description and describes the topological invariants of Wagner classes by finite trees. The one of Saint Raymond [START_REF] Raymond | Classification de Wadge. Note d'exposé[END_REF] uses Borel functions of class ξ (ξ < ω 1 ). This description has the advantage to extend immediately to the case of finite Borel coloring of A ω (Wadge case is Black and White, X ⊂ A ω , X 0 = X, X 1 = X, A ω = X 0 ∪ X 1 ). The one of Duparc [START_REF] Duparc | Wadge Hierarchy and Veblen Hierarchy : Part1 : Borels Sets of Finite Rank[END_REF] follows the Cantor normal form of ordinals. This description has been used by Finkel [START_REF] Finkel | Wadge Hierarchy of Omega Context Free Languages[END_REF][START_REF] Finkel | Borel Ranks and Wadge Degrees of Context Free omega-Languages[END_REF] to study the order type of the Wadge hierarchy restricted to ω-context-free languages.

In [START_REF] Raymond | Classification de Wadge. Note d'exposé[END_REF] it is quoted that games used by Van Wesep, Steel, Louveau Saint Raymond are particular case of elementary games with winning set G = ∪ n i=0 X i × Y i , where the X i , Y i are Borel subsets of A ω . Let (X 0 , . . . , X n ) and (Y 0 , . . . , Y n ) be two Borel partitions of A ω . Define the game G(X 0 , . . . , X n ; Y 0 , . . . , Y n ) where I plays α, II plays β and where II wins the game if ∀iα ∈ X i ⇒ Y i . This game enable us to compare finite Borel partitions. This gives for all n the Wadge n + 1 colors hierarchy. If the X i , Y i are Auto this gives for all n the Wagner n + 1 colors hierarchy. Then you can use Büchi Landweber and this certainly has to do with the algebra of finite monoïds (see Carton Michel [START_REF] Carton | Unambiguous Büchi automata[END_REF], Carton Perrin [22], Perrin Pin [START_REF] Perrin | Infinite words[END_REF], Wilk [START_REF] Wilke | An algebraic theory for regular languages of finite and infinite words[END_REF]).

In [START_REF] Hertling | On the Topological Classification of Degeneracies[END_REF] Hertling and Weihrauch study discontinuity of finite valued Borel functions, for understanding degeneracy in computational geometry. Here is their abstract : "We introduce levels of discontinuity and prove that they correspond to the number of tests in "continuous computation trees". We illustrate the concept of level by various simple examples from computational geometry. For a finer comparison of kinds of discontinuity we introduce a continuous reducibility relation for finite valued functions. We show that each of the resulting degrees (of finite level) can be characterized by a finite set of finite trees which describes the type of discontinuity of its functions. The ordering of the degrees is decidable in the tree sets and each level consists only of finitely many degrees". The description of Saint Raymond may have very interesting applications in computational geometry.

Here is an example of Hertling Weirauch [START_REF] Hertling | On the Topological Classification of Degeneracies[END_REF]. Let f : {0, 1} ω -→ {2, 3, 7} defined by

f (α) =      7 if α = 0 ω 3 if α ∈ 0 * 1 ω 2 else
This is a Baire class 1 function. We conclude this section by another example coming from the representation of reals in base of the golden mean. Let g : {0, 1} ω -→ {2, 3, 7} defined by

g(α) =     
7 if α ∈ (0 + 1) * 11(0 + 1) ω 3 if α ∈ (0 + 10) ω and α ∈ (0 + 1) * 0 ω 2 if α ∈ (0 + 10) ω and α ∈ ((0 + 1) * 1) ω This is not a Baire class 1 function

Conclusion

12.1 Π 1 1 sets and ω 1 , the boundedness theorem of Lusin

There is a lot of to say about the story of transfinite. For example Borel did not believe in ω 1 ("cette totalité illégitime"), Lusin seems to refuse the Third Middle excluded for projective sets. It is well known that Baire, Borel, Lebesgue, did not believe in the axiom of choice. Zermelo has proven with the axiom of choice that you can put a well order on every set. Sierpinski believed in the axiom choice, but has shown which theorems need the axiom of choice. In general, there is no need of axiom of choice when you dispose of a well order. Do you believe in ω 1 ? Do we need countable ordinals in computer science ? It is an old result of Lusin and Sierpinski that WO (as Well Order), the code of countable ordinals, is The Example of a coanalytic set. It is a coanalytic complete set. The first examples of coanalytic-complete sets in analysis are due to Hurewicz [START_REF] Hurewicz | Relativ perfekte Teile von Punktmengen und Mengen[END_REF][START_REF] Kechris | Classical Descriptive Set Theory[END_REF][START_REF] Simonnet | Automate et théorie descriptive[END_REF]. These are the set K(Q) of compacts subsets of the rationals of the interval [0, 1] and the set K ω of countable compacts subsets of the interval [0, 1]. Consider the stupid game in 2 ω × 2 ω where Player I wins the game if α ∈ Q and β ∈ 2 ω . Player I has a simple automaton strategy : always play 0. Call, by analogy with K(Q), KQ the set of winning strategies of player I, this set is Π 1 1 and extending ϕ : ω * -→ 2 * of remark 3 in ϕ : 2 ω * -→ 2 2 * one has that ϕ -1 (KQ) = WF, hence KQ is a Π 1 1 -complete set. This was first observed by Niwinski in 1986 [START_REF] Niwinski | An Example of Non Borel Set of infinite Trees Recognizable by a Rabin Automaton[END_REF]. This set is recognized by a deterministic Muller infinite tree automaton. In fact a set is recognized by deterministic Muller infinite tree automaton if and only if it is the set of winning strategies of player I in an ω-regular game, and a set is recognized by a nondeterministic Muller infinite tree automaton if it is the projection of a set recognized by a deterministic Muller infinite tree automaton. Infinite tree automaton where used by Rabin [START_REF] Rabin | Decidability of Second Order Theories and Automata on Infinite Tree[END_REF] to show the decidability of the monadic second order theory of the tree 2 * , S2S. Rabin shows that a set is recognized by a nondeterministic Muller infinite tree automaton if and only if it is definable in S2S. Note that it is quite clear when you read the first pages of Rabin that the set K(Q) of compacts subsets of Q = {α ∈ 2 ω | ∃m ∀n ≥ m α(n) = 0} is definable in S2S and we know since Hurewicz that this set is Π 1 1 -complete (see [START_REF] Hurewicz | Relativ perfekte Teile von Punktmengen und Mengen[END_REF][START_REF] Kechris | Descriptive Set Theory and the Structure of Sets of Uniqueness[END_REF][START_REF] Kechris | The Structure of σ-ideals of Compact Sets[END_REF][START_REF] Kechris | Classical Descriptive Set Theory[END_REF]). Rabin shows by transfinite induction on countable ordinals that if a set is recognized by a nondeterministic Muller infinite tree automaton then its complements is also recognized by a nondeterministic Muller infinite tree automaton. The complement of KQ is recognized by a nondeterministic Büchi infinite tree automaton but KQ is not recognized by a nondeterministic Büchi infinite tree automaton ( otherwise KQ will be Borel, see also Rabin [START_REF] Rabin | Weakly Definable Relations and Special Automata[END_REF] for a combinatorial proof of that, the paper of Rabin [START_REF] Rabin | Weakly Definable Relations and Special Automata[END_REF] is a kind of Suslin Kleene Automata theorem [START_REF] Simonnet | Automate et théorie descriptive[END_REF]). Finkel codes the complement of KQ to obtain an ω-context free set which is analytic complete. This led to undecidability results :

The problem of knowing whether an ω-context free languages is Borel is undecidable, the problem of knowing whether an ω-context free languages is Σ 0 ξ is undecidable. ω-context free languages are Σ Later on, Finkel, with the same kind of coding, obtained an ω-rational relation which is analytic complete. This gave other undecidability results : The problem of knowing whether an ω-rational relation is Borel is undecidable, the problem of knowing whether an ω-rational relation is Σ 0 ξ is undecidable. Finally we can remark that simple models of asynchronous parallelism on infinite words gives analytic complete sets [START_REF] Finkel | On Infinite Real Trace Rational Languages of Maximum Topological Complexity[END_REF]. Note that Kuratowski shows how to eliminate transfinite numbers in mathematical proofs [START_REF] Kuratowski | Une méthode d'élimination des nombres transfinis des raisonnements mathématiques[END_REF]. He takes as examples the Cantor Bendixon theorem and the derivation of Felix Hausdorff. For example, in games, ordinals are hidden in the construction of strategies. One can say : don't hide countable ordinals and you will see some true coanalytic sets. This has to do with the boundedness theorem of Lusin [START_REF] Lusin | Leçons sur les Ensembles Analytiques et leurs Applications[END_REF][START_REF] Moschovakis | Descriptive Set Theory[END_REF][START_REF] Kechris | Classical Descriptive Set Theory[END_REF]. If a set X is a coanalytic set then for all α ∈ X one can associate a countable ordinal ϕ(α). And X is borel if and only if there exists ξ < ω 1 such that for all α ∈ X, ϕ(α) < ξ. Note that Lusin don't think that such a procedure can be effective to decide if a Π 1 1 set is a true (not Borel) Π 1 1 set, and the undecidability results of Finkel shows that he was right. We think that countable ordinals are inherently hidden in models of parallelism, verification and XM L.

Baire class 1 functions

In conclusion, let us say that other properties of ω-rational function which are Baire class 1 can be derived from work by Kechris and Louveau [START_REF] Kechris | A Classification of Baire class 1 functions[END_REF]. One can find concrete examples of ω-rational Baire class 1 functions in [START_REF] Frougny | On-the-Fly algorithms and sequential machines[END_REF][START_REF] Frougny | Numeration Systems. Chapter 8 of M. Lothaire, Algebraic Combinatorics on Words[END_REF][START_REF] Kornerup | Digit-set convertions : Generalizations and applications[END_REF][START_REF] Muller | Arithmétique des ordinateurs[END_REF] and one can even define Baire class 1 functions on real numbers by using representation of real numbers in Pisot Basis [START_REF] Cagnard | Automata Borel functions and real numbers in Pisot basis[END_REF].

Finally we remark that Baire has introduced semi continuity, oscillation and the space ω ω . The bibliography is big but still incomplete. We have certainly forgotten some work, especially work of Schupp on alternating automata and work on fixed point theory of Arnold, Niwinski, Kozen, Bradfield, Walukiewicz, Wilke.

Fig. 1 :Fig. 2 :

 12 Fig. 1: The open set

Fig. 4 :

 4 Fig. 4: Normalization in base 2

Fig. 5 :

 5 Fig. 5: a totally discontinuous synchronous function

Fig. 7 :

 7 Fig. 7: A deterministic Büchi automaton which recognizes a D3(Σ 0 1 )-complete set.

Fig. 8 :

 8 Fig. 8: A deterministic Müller automaton which recognizes a D3(Σ 0 2 )-complete set.

  A winning strategy for II gives a continuous function ( a Lipschitz map) ϕ such that ϕ -1 (Y ) = O. A winning strategy for I gives a continuous function ( a Lipschitz map) ψ such that : ψ(Y ) ⊂ Ǒ, ψ(Z) ⊂ O. That is to say ψ -1 ( Ǒ) separate Y from Z. It is easy to see that there is a closed set which separates Y from Z if and only if player I has a winning strategy in the first separation game. If Y and Z are ω-regular sets one can deduce from Büchi Landweber's theorem that one can decide if two ω-regular disjoint sets are separated by a closed set. Moreover if they are separated by a closed set, they are separated by a Π 0 1 (Auto). In a second game, Player II wins the game iff (α ∈ Q ⇒ β ∈ Y and α ∈ Q ⇒ β ∈ Z). A winning strategy for II gives a continuous function (a Lipschitz map) ϕ such that ϕ -1 (Y ) = Q. A winning strategy for I gives a continuous function (a Lipschitz map) ψ such that :ψ(Y ) ⊂ Q, ψ(Z) ⊂ Q. That is to say ψ -1 ( Q) separate Y from Z.It is easy to see that there is a Π 0 2 set which separates Y from Z if and only if player I has a winning strategy in the first separation game. If Y and Z are ω-regular sets, one can deduce from Büchi Landweber's theorem that one can decide if two ω-regular disjoint sets are separated by a Π 0 2 set. Moreover if they are separated by a Π 0 2 set, they are separated by a Π 0 2 (Auto), that is to say, they are separated by a set recognized by deterministic Büchi automaton.

1 1 .

 1 And one can play separation games where Player II wins the game iff (α∈ O ⇒ β ∈ Y and α ∈ Ǒ ⇒ β ∈ Z) (Resp. Player II wins the game iff (α ∈ Q ⇒ β ∈ Y and α ∈ Q ⇒ β ∈ Z))with Y and Z ω-context free languages. Probably these games are undecidable, probably one can't decide if two ω-context free languages are separated by a Σ 0 ξ set. But Louveau's theorem is true if they are separated by a Σ 0 ξ set ( ξ < ω 1 ), then they are separated by a Σ 0 ξ (∆ 1 1 ) set.

W [X] = {Y ⊂ A ω | ∃ϕ : A ω -→ A ω sequential Y = ϕ -1 (X)}

Acknowledgements

Acknowledgements of the first author : I began to learn automata theory in the DEA of Maurice Nivat (my adviser) in the year 1983-1984 at LITP. In particular I learned first Büchi's theory with Dominique Perrin, and ω-

So

M ξ+1 = M ∩ F ξ ∩ F ξ+1 = M ∩ F ξ+1 .

For λ limit, if M ξ = M ∩ F ξ for ξ < λ, then :

Lemma 16 Let M and N be two Π 0 2 subsets of A ω and F η the largest closed set such that

2 sets. So, by lemma 6, there exists U ⊂ A * et V ⊂ A * so that : Lim(U ) = M η and Lim(V ) = N η . If F η = ∅, as F η = M η = N η , we can find α 1 ∈ M η and u 1 ∈ U such that u 1 is a prefix of α 1 . Since every open ball containing α 1 meets N η , we can find β 1 ∈ N η so that u 1 is a prefix of β 1 . But N η = Lim(V ), thus we can find v 1 ∈ V such that v 1 is a prefix of β 1 and u 1 is a strict prefix of v 1 . Finally since every ball containing β 1 meet M η we can find α 2 ∈ M η so that v 1 is a prefix of α 2 , and since M η = Lim(U ) we can find u 2 ∈ U prefix of α 2 so that v 1 is a strict prefix of u 2 . Then u 1 < v 1 < u 2 . Iterating this process, we construct two sequences (u i ), (v i ) such that

Theorem 17 (Hausdorff ) Let M and N be two disjoint Π 0 2 subsets of A ω . Then : (i) There exists ζ < ω 1 and a set in D ζ (Σ 0 1 ) which separates M from N . (ii) In particular, ∆ 0 2 = ∪ ξ<ω1 D ξ (Σ 0 1 ). Proof: Let P ξ = F ξ \M ∩ F ξ , R ξ = F ξ \N ∩ F ξ . We have :

Let η be the smallest ordinal such that F η = F η+1 . We have :

) and the opposite inclusion has been proved in lemma 12.

Pierre Simonnet and Benoit Cagnard

The notation W on the left gives in French : W A Gauche. WAGner has given a complete description of all Wagner classes of Rec(A ω ). One can also defined selfdual and non selfdual Wagner classes. Wagner proves (in fact maybe he didn't know Wadge at this time) that Wagde's hierarchy restricted to ω-regular set is Wagner's hierarchy : Γ W ∩ Auto = W Γ. The first normal form's theorems of this type for ω-regular sets are from Landweber [START_REF] Landweber | Decision problem for ω-automata[END_REF] :

An ω-regular set X which is open is the inverse image of O by a 1-sequential function. An ωregular set X which is closed is the inverse image of Ǒ by a 1-sequential function or equivalently X is the set of infinite branches of a rational tree of A * . From this one can deduce that synchronous continuous are exactly the sequential function with bounded delay, Trakhtenbrot [START_REF] Trakhtenbrot | Finite Automata and the Monadique Predicare Calculus[END_REF][START_REF] Trakhtenbrot | Finite Automata[END_REF]. If an ω-rational function is not of Baire class 1, one can find a rational tree (tree with a finite number of subtrees) whose set of infinite branches is a Perfect set P (closed set without isolated points [START_REF] Kuratowski | Topology[END_REF]) and the restriction of f to P has no point of continuity.

An ω-regular set which is F σ is the inverse image of Q by a 1-sequential function. An ωregular set X which is G δ is the inverse image of Q by a 1-sequential function, or equivalently X is recognized by a deterministic Büchi automaton, X = Lim(L) with L a regular set. If f is synchronous then Cont(f ) is definable in S1S so one can't constructs a deterministic Büchi automaton which recognizes Cont(f ).

In February 1987 Louveau used the following formalism to denote Landweber's theorems. Call

Auto) If an ω-rational function is not of Baire class 1, one can find a a Perfect set P which is Π 0 1 (Auto) such that the restriction of f to P has no point of continuity. If f is synchronous then Cont(f ) is Π 0 2 (Auto). Louveau was working in effective set theory (see Moschovakis [START_REF] Moschovakis | Descriptive Set Theory[END_REF]). He has defined a hierarchy of effective Borel sets of ω ω , the ∆ 1 1 sets of ω ω . Louveau proves that Wagde's hierarchy restricted to ∆ 1 1 sets is Louveau's hierarchy. His theorem gives for example [START_REF] Louveau | A separation theorem for Σ 1 1 sets[END_REF][START_REF] Louveau | Some results in the Wadge Hierarchy of Borel Sets[END_REF] :

And the same definition for Σ 0 n (∆ 1 1 ) with a very simple set in 2 ω n recognized by a finite automaton which reads words of length ω n (see Büchi [START_REF] Büchi | The Monadic Theory of ω 1 . in The Monadic Second Order Theory of All Countable Ordinals[END_REF], Shelah [START_REF] Shelah | The Monadic Theory of order[END_REF], Bedon [START_REF] Bedon | Finite automata and ordinals[END_REF], Choffrut Grigoriev [START_REF] Choffrut | Uniformization of Rational Relations[END_REF] for finite automata reading transfinite words). From this effective results Louveau deduces classical results in the plane : If X ⊂ ω ω ×ω ω is a Borel set with Σ 0 n+1 sections then X is a countable union of Borel sets in ω ω × ω ω with Π 0 n sections. The first example of this kind of results is the case of Borel sets in the plane with countable sections studied by Lusin [START_REF] Lusin | Leçons sur les Ensembles Analytiques et leurs Applications[END_REF]. This result was extended by Novikov Arsenin and Kunugui to the case of Borel sets in the plane with compact sections or K σ sections(see Sierpinski [START_REF] Sierpinski | Les Ensembles Projectifs et Analytiques[END_REF], Saint Raymond [START_REF] Raymond | Classification de Wadge. Note d'exposé[END_REF], Louveau Saint Raymond [START_REF] Louveau | Borel classes and closed games Wadge-type and Hurewicztype results[END_REF], Kechris [START_REF] Kechris | Classical Descriptive Set Theory[END_REF], Srivastava [START_REF] Srivastava | A course on Borel Sets[END_REF]).

O and Q

For all Wadge classes of Borel sets Γ, Wadge gives an example of a Γ-complete set in ω ω . As remarked by Professor Jean Saint Raymond "il suffit de le faire pour les ouverts." We will do it for open sets and F σ sets.

Let T be a tree of A * , we denote by [T ] the set of the infinite branches of T :

Proposition 25 Let F be a subset of A ω . The set F is closed iff there exists a tree

Proof: Let U be in Σ 0 1 (A ω ). The complement of U is closed, so by proposition 25, there exists a tree T so that T = Ǔ . The winning strategy φ : A + → {0, 1} for II is the following :

In fact using Martin theorem and Wadge game every open non closed set is Σ 0 1 (A ω )-strategically complete. And using Büchi Landweber theorem we have

Proof: Let U be in Σ 0 2 (A ω ). Then there exists a family (F n ) n∈ω of closed sets so that U = n∈ω F n . By proposition 25, for any integer n, there exists a tree T n so that F n = [T n ]. The winning strategy φ : A + → {0, 1} for II is given by the following induction : Any Π 1 1 set X in a compact metrizable space E which is not Π 0 2 contains a closed subset homeomorphic to Q. In fact, one can also construct a homeomorphic copy F of 2 ω inside E such that F ∩ X is (through the homemorphism) identified with Q. The set Q is a Hurewicz-witness for non Π 0 2 -ness, Q is a Hurewicz-test. And we have in the ω-regular case. If an ω-regular set X is not Π 0 2 then every deterministic Muller automaton which recognizes X contains a chain {+} ⊂ {-}. This was generalized to all Wagner classes by Wagner [START_REF] Wagner | On ω -regular Sets[END_REF].

Effective results of Louveau were first proved in [START_REF] Louveau | A separation theorem for Σ 1 1 sets[END_REF]. Let Σ 1 1 (resp. Π 1 1 ) be the class of effective analytic sets (resp. coanalytic sets) and ∆ 1 1 = Π 1 1 ∩ Σ 1 1 be the class effective Borel sets (bold-face=classical, ligthface=effective see Moschovakis [START_REF] Moschovakis | Descriptive Set Theory[END_REF]). Let Y and Z be two disjoint Σ 1 1 subsets of ω ω . Louveau has shown that if there is a Σ 0 n which separates Y from Z then there is a Σ 0

) and by relativisation the theorem on Borel sets of the plane with Σ 0 n sections. He used the good properties of the Gandy Harrington's topology of ω ω , the topology generated by the Σ 1 1 subsets of ω ω . Then in [START_REF] Louveau | Some results in the Wadge Hierarchy of Borel Sets[END_REF] Louveau has extended this separation theorem to all effective Wadge classes. In [START_REF] Louveau | Borel classes and closed games Wadge-type and Hurewicztype results[END_REF] Louveau and Saint Raymond use separation games to give another proof of these results [START_REF] Louveau | Borel classes and closed games Wadge-type and Hurewicztype results[END_REF]. They use the basic strategic theorem : if G ⊂ ω ω × ω ω , the winning set for II, is a Σ 0 1 set then if player II has a strategy then he have a ∆ 1 1 strategy. They also give an Hurewicz's theorems for all Wadge classes.

Steel's game and separation by ∆ 0 2 sets

Let Q 0 , the subset of 2 ω of infinite words with finite even number of 1 and Q 1 the subset of 2 ω of infinite words with finite odd number of 1. We have seen that Q 0 and Q 1 are not separate by a ∆ 0 2 set. Let X and Y be disjoint sets. In the Steel's game, player II wins the game iff ((α

Proposition 28 If the sets Y and Z are borel sets, then player II has a winning strategy iff there is a ∆ 0 2 set which separates Y from Z. Proof: A winning strategy for II gives a continuous function (a Lipschitz map) ϕ :

A winning strategy for I gives a continuous function (a Lipschitz map) ψ : 2 ω → A ω such that : Proof: If Y and Z are ω-regular sets then the Steel's game is ω-regular. So by the Büchi Landweber's theorem, we can decide if player II has a winning strategy. Moreover if player II has a winning strategy he has a sequential letter to letter strategy ϕ. This implies that ϕ(Q 0 ) = ϕ( Q1 ) is an ω-regular ∆ 0 2 set which separates Y from Z.

Hausdorff and automata

We have seen Hausdorff's theorem

and we have seen that in the ω-regular case we have [106]

in the case of effective Borel sets we have [60]

where ω CK 1 is the Church Kleene ordinal, the least nonrecursive ordinal. Let us give another example of the utility of Hausdorff's derivation. In [START_REF] Lecomte | ω-powers and descriptive set theory[END_REF] Lecomte studies from a descriptive set theory point of view L ω , the ω-power of L ⊂ A * . Lecomte answers to questions ask by Staiger in [START_REF] Staiger | ω-languages[END_REF]. Among the very interesting results of Lecomte, there is a surprising fact which links combinatorics on words and the Hausdorff derivation. Let

is the set of languages such that their ω-powers are generated by two words. The set of languages 2 A * is a compact metric space, and one can ask the question of the topological complexity of G 2 . Lecomte's result is the following

). This is an example of a concrete Ďω (Σ 0 1 ) coming from the real world. In his proof Lecomte uses Hausdorff's derivation and the default theorem (see Bruyère [START_REF] Bruyère | Codes. Chapter 7 of M. Lothaire[END_REF]). In the same context, another result of Duparc [START_REF] Duparc | A Hierarchy of Deterministic Context-Free ω-languages[END_REF] is relevant. The order type of the difference hierarchy of open set restricted to deterministic ω-context free languages is ω ω . The order type of difference hierarchy of open set restricted to one counter language is at least ω ω [START_REF] Finkel | Wadge Hierarchy of Omega Context Free Languages[END_REF]. It seems that Finkel shows in [START_REF] Finkel | Borel Ranks and Wadge Degrees of Context Free omega-Languages[END_REF] that the order type of difference hierarchy of open set restricted to ω-context free languages is at least ω CK 1 and that the Wadge hierarchy of Borel sets restricted to ω-context free languages has the same order type that Louveau's hierarchy. In a paper of the sixties [START_REF] Skurczynski | The Borel Hierarchy is Infinite in the Class of Regular Sets of Trees[END_REF], Skurczynski finds examples of sets of trees in 2 2 * which are Σ 0 n complete and he remarks that they are recognized by Muller tree automata. An examination of these examples and a careful reading of the construction of D ξ (Σ 0 1 )-strategically complete in [START_REF] Louveau | Borel classes and closed games Wadge-type and Hurewicztype results[END_REF] shows that you can define with tree automata a set which is D ω n (Σ 0 1 ) complete for all n ∈ ω [START_REF] Simonnet | Automate et théorie descriptive[END_REF]. The same construction gives sets recognized by nondeterministic Muller infinite tree automaton which are D ω n (Σ 0 n ) complete and sets recognized by nondeterministic Muller tree automaton which are D ω n (Π 1 1 ) complete [START_REF] Simonnet | Automate et théorie descriptive[END_REF]. In particular the family of sets recognized by nondeterministic Muller infinite tree automaton is not the boolean algebra generated by the family of sets recognized by nondeterministic Büchi tree automaton. This last statement was first proved by Hafer [START_REF] Hafer | On the Boolean Closure of Buchi Tree Automaton Definable Set of ω-trees[END_REF]. Finite automata read also transfinite words (see Büchi [START_REF] Büchi | The Monadic Theory of ω 1 . in The Monadic Second Order Theory of All Countable Ordinals[END_REF], Shelah [START_REF] Shelah | The Monadic Theory of order[END_REF], Bedon [START_REF] Bedon | Finite automata and ordinals[END_REF], Choffrut Grigoriev [START_REF] Choffrut | Uniformization of Rational Relations[END_REF]), what are the degrees of the difference hierarchy of open set restricted to sets of words of length ω n recognized by finite automata ? What are the degrees of the difference hierarchy of open set restricted to sets definable in S2S ?

Game quantifier and tree automata

Descriptive set theory is the study of definable sets in Polish spaces and will we be very happy to know the exact topological complexity of sets definable in S2S. Does the good hierarchies of sets definable in S2S are the restrictions of the good old hierarchies of descriptive set theory ?

These classes are very interesting because if Γ has the norm property then (Γ) has the norm property (see Moschovakis [START_REF] Moschovakis | Descriptive Set Theory[END_REF]). Determination of the games in Γ implies that ( (Γ)) = ( Γ). For example :

. By the Tarski Kuratowski algorithm we have (Π 0 1 ) = Σ 1 1 so, by determination of closed games in ω ω × ω ω , (Σ 0 1 ) = Π 1 1 . Another way to see this is to use the basis strategic theorem (see Kechris [START_REF] Kechris | Classical Descriptive Set Theory[END_REF], Moschovakis [START_REF] Moschovakis | Descriptive Set Theory[END_REF]) : If the winning set for I, is a Σ 0 1 set then if player I has a strategy then he have a ∆ 1 1 strategy, if Y is open then if player I has a strategy in the game Y α then he have a ∆ 1 1 (α) strategy, that is I can choose ϕ in a borel way from α ∈ X, ϕ is borel in α and the class Π 1 1 is closed by substitution by Borel function. The class (Σ 0 2 ) is a quite complicate object linked to inductive definitions (see Moschovakis [START_REF] Moschovakis | Descriptive Set Theory[END_REF] ). It easy to see that sets definable in S2S are in the classes (D n (Σ 0 2 )) ( see Gurevitch Harrington [START_REF] Gurevitch | Trees Automata and Games[END_REF]). But we are working in compacts spaces and the continuous image of a compact space is compact. The projection of a K σ is a

) so, by determination of closed games in 2 ω × 2 ω , (Σ 0 2 )(2 ω ) = Π 1 1 (2 ω ). From the existence of Π 0 1 set of ω ω which do not contain a ∆ 1 1 point, one can deduce that there exists Π 0 1 game in ω ω such that the closed Player wins the game but have no ∆ 1 1 strategy (see Moschovakis [START_REF] Moschovakis | Descriptive Set Theory[END_REF]). And from the existence of Π 0 2 set of 2 ω which do not contain a ∆ 1 1 point, one can deduce that there exists Π 0 2 game in 2 ω such that the Π 0 2 Player wins the game but have no ∆ 1 1 strategy (see [START_REF] Thomas | On the Synthesis of Strategies in Infinite Game[END_REF]). A direct computation of the complexity of (Σ 0 2 )(2 ω ) by the Tarski Kuratowski algorithm gives a Σ 1 2 set, that is to say a projection of a coanalytic set. In a Σ 0 2 (2 ω × 2 ω ) game, if the Σ 0 2 player has a winning strategy does he has a ∆ 1 1 strategy ? If Y ⊂ 2 ω × 2 ω × 2 ω is Σ 0 2 and if α ∈ X ↔ I has winning strategy in the game Y α , does I can choose ϕ in a borel way from α ∈ X ? There exists another old hierarchy in ∆ 1 2 the hierarchy of C of Selivanowski starting from Σ 1 1 sets we alternate complement and Suslin scheme (see Kuratowski [START_REF] Kuratowski | Une méthode d'élimination des nombres transfinis des raisonnements mathématiques[END_REF]), it turns out that the hierarchy of Selivanowski is the hierarchy of the (D ξ (Σ 0 1 )) for ξ < ω 1 (see Moschovakis [START_REF] Moschovakis | Descriptive Set Theory[END_REF], Louveau [START_REF] Louveau | Quantificateur de jeu et σ-ideal of compacts[END_REF]) Does there is a a difference between the classes (D 2 (Σ 0 2 ))(ω ω ) and (D 2 (Σ 0 2 ))(2 ω ) ? Does the hierarchies of game quantifier has to do with set definable in S2S. One can see presentation of Niwinski [START_REF] Niwinski | On the complexity of infinite computations[END_REF] to have an account of recent work and problems in S2S. context free languages with Françoise Gire. In 1984 my friend Vincent Schoen brought up to me a course from Saint Raymond. In the beginning of this course was presented ordinals and Cantor's derivation and it looked like a problem on process in [START_REF] Arnold | Comportement de Processus[END_REF]. Then I saw on the program of Louveau's seminary a title : "Mistigri Games". Before this seminary, there was another seminary about σ-ideal of compact sets. There was the compact of a set recognized by automata, then Mistigry seminary and a game played against a set recognized by automata. Then I began to learn classical descriptive theory and effective descriptive set theory in Louveau's documents. I thank Professor Jean Saint Raymond who recognized Hausdorff's theorem in a theoretical computer science problem in 1986. I also thank Alain Louveau for his help. Alain Louveau recognized Wadge's hierarchy in Wagner's hierarchy in 1987 and he invited me in his seminary to give a talk on Wagner in 1987 and on KQ in 1988. He introduced old results of Hurewicz [START_REF] Hurewicz | Relativ perfekte Teile von Punktmengen und Mengen[END_REF] and effective set theory to the first author. We use Louveau documents for the topological sections. I also thank Jean Pierre Ressayre who accepted to organize a workshop in 1988 about Wadge's hierarchy and Wagner's hierarchy. This is where I met Olivier Finkel and Jacques Duparc. I learned tree alternating automata with Paul Schupp and I am indebted to him for his help. Many thanks to jean claude Dumoncel for historical discussions on Borel. Finally I thank Professor Serge Grigorieff who accepted to advise my thesis.

The authors thank Dominique Lecomte who kindly accepted that we present his result. Gabriel Debs and Dominique lecomte proved in 2006 that in a Σ 0 2 (2 ω × 2 ω ) game, the Σ 0 2 player has a ∆ 1 1 winning strategy whenever he has a winning strategy. Let f : ω ω -→ ω ω be an effective borel function, that is to say its graph is a ∆ 1 1 set. If f is not Baire class one, does there exists a closed nonempty set F which is ∆ 1 1 (and so by Louveau theorem F is Π 0 1 (∆ 1 1 ) ) such that the restriction of f to F has no point of continuity ?