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

Topological Complexity of Context-Free ω-Languages : A Survey

Keywords: Infinite words, pushdown automata, context-free (ω)-languages, ω-powers, Cantor topology, topological complexity, Borel hierarchy, Wadge hierarchy, complete sets, decision problems

We survey recent results on the topological complexity of context-free ω-languages which form the second level of the Chomsky hierarchy of languages of infinite words. In particular, we consider the Borel hierarchy and the Wadge hierarchy of non-deterministic or deterministic context-free ω-languages. We study also decision problems, the links with the notions of ambiguity and of degrees of ambiguity, and the special case of ω-powers.

Introduction

The Chomsky hierarchy of formal languages of finite words over a finite alphabet is now well known, [START_REF] Hopcroft | Introduction to automata theory, languages, and computation[END_REF]. The class of regular languages accepted by finite automata forms the first level of this hierarchy and the class of context-free languages accepted by pushdown automata or generated by context-free grammars forms its second level [START_REF] Autebert | Context free languages and pushdown automata[END_REF]. The third and the fourth levels are formed by the class of context-sensitive languages accepted by linear-bounded automata or generated by Type-1 grammars and the class of recursively enumerable languages accepted by Turing machines or generated by Type-0 grammars [START_REF] Chomshy | Three models for the description of language[END_REF]. In particular, context-free languages, firstly introduced by Chomsky to analyse the syntax of natural languages, have been very useful in Computer Science, in particular in the domain of programming languages, for the construction of compilers used to verify correctness of programs, [START_REF] Hopcroft | Introduction to automata theory, languages, and computation[END_REF].

There is a hierarchy of languages of infinite words which is analogous to the Chomsky hierarchy but where the languages are formed by infinite words over a finite alphabet. The first level of this hierarchy is formed by the class of regular ω-languages accepted by finite automata. They were first studied by Büchi in order to study decision problems for logical theories. In particular, Büchi proved that the monadic second order theory of one successor over the integers is decidable, using finite automata equipped with a certain acceptance condition for infinite words, now called the Büchi acceptance condition. Well known pioneers in this research area are named Muller, Mc Naughton, Rabin, Landweber, Choueka, [START_REF] Muller | Infinite sequences and finite machines[END_REF][START_REF] Naughton | Testing and generating infinite sequences by a finite automaton[END_REF][START_REF] Rabin | Decidability of second-order theories and automata on infinite trees[END_REF][START_REF] Landweber | Decision problems for ω-automata[END_REF][START_REF] Choueka | Theories of automata on omega-tapes: A simplified approach[END_REF]. The theory of regular ω-languages is now well established and has found many applications for specification and verification of non-terminating systems; see [START_REF] Thomas | Automata on infinite objects[END_REF][START_REF] Staiger | ω-languages[END_REF][START_REF] Perrin | Infinite words, automata, semigroups, logic and games[END_REF] for many results and references. The second level of the hierarchy is formed by the class of context-free ω-languages. As in the case of languages of finite words it turned out that an ω-language is accepted by a (non-deterministic) pushdown automaton (with Büchi acceptance condition) if and only if it is generated by a context-free grammar where infinite derivations are considered. Context-free languages of infinite words were first studied by Cohen and Gold, [START_REF] Cohen | Theory of ω-languages, parts one and two[END_REF][START_REF] Cohen | ω-computations on deterministic pushdown machines[END_REF], Linna, [START_REF] Linna | On ω-words and ω-computations[END_REF][START_REF] Linna | On omega-sets associated with context-free languages[END_REF][START_REF] Linna | A decidability result for deterministic ω-context-free languages[END_REF], Boasson,Nivat,[START_REF] Nivat | Sur les ensembles de mots infinis engendrés par une grammaire algébrique[END_REF][START_REF] Nivat | Mots infinis engendrés par une grammaire algébrique[END_REF][START_REF] Boasson | Context-free sets of infinite words[END_REF][START_REF] Boasson | Adherences of languages[END_REF], Beauquier, [START_REF] Beauquier | Some results about finite and infinite behaviours of a pushdown automaton[END_REF], see the survey [START_REF] Staiger | ω-languages[END_REF]. Notice that in the case of infinite words Type-1 grammars and Type-0 grammars accept the same ω-languages which are also the ω-languages accepted by Turing machines with a Büchi acceptance condition [START_REF] Cohen | ω-computations on Turing machines[END_REF][START_REF] Staiger | ω-languages[END_REF], see also the fundamental study of Engelfriet and Hoogeboom on X-automata, i.e. finite automata equipped with a storage type X, accepting infinite words, [START_REF] Engelfriet | X-automata on ω-words[END_REF]. Context-free ω-languages have occurred recently in the works on games played on infinite pushdown graphs, following the fundamental study of Walukiewicz, [START_REF] Walukiewicz | Pushdown processes: games and model checking[END_REF][START_REF] Thomas | Infinite games and verification (extended abstract of a tutorial)[END_REF] [START_REF] Serre | Games with winning conditions of high Borel complexity[END_REF][START_REF] Finkel | On winning conditions of high Borel complexity in pushdown games[END_REF].

Since the set X ω of infinite words over a finite alphabet X is naturally equipped with the Cantor topology, a way to study the complexity of ω-languages is to study their topological complexity. The first task is to locate ω-languages with regard to the Borel and the projective hierarchies, and next to the Wadge hierarchy which is a great refinement of the Borel hierarchy. It is then natural to ask for decidability properties and to study decision problems like : is there an effective procedure to determine the Borel rank or the Wadge degree of any context-free ω-language ? Such questions were asked by Lescow and Thomas in [START_REF] Lescow | Logical specifications of infinite computations[END_REF]. In this paper we survey some recent results on the topological complexity of context-free ω-languages. Some of them were very surprising as the two following ones:

1. there is a 1-counter finitary language L such that L ω is analytic but not Borel, [START_REF] Finkel | Borel hierarchy and omega context free languages[END_REF]. 2. The Wadge hierarchy, hence also the Borel hierarchy, of ω-languages accepted by real time 1-counter Büchi automata is the same as the Wadge hierarchy of ωlanguages accepted by Büchi Turing machines, [START_REF] Finkel | Borel ranks and Wadge degrees of omega context free languages[END_REF].

The Borel and Wadge hierarchies of non deterministic context-free ω-languages are not effective. One can neither decide whether a given context-free ω-language is a Borel set nor whether it is in a given Borel class Σ 0 α or Π 0 α . On the other hand deterministic context-free ω-languages are located at a low level of the Borel hierarchy: they are all ∆ 0 3 -sets. They enjoy some decidability properties although some important questions in this area are still open. We consider also the links with the notions of ambiguity and of degrees of ambiguity, and the special case of ω-powers, i.e. of ω-languages in the form V ω , where V is a (context-free) finitary language. Finally we state some perspectives and give a list of some questions which remain open for further study.

The paper is organized as follows. In Section 2 we recall the notions of context-free ω-languages accepted by Büchi or Muller pushdown automata. Topological notions and Borel and Wadge hierarchies are recalled in Section 3. In Section 4 is studied the case of non-deterministic context-free ω-languages while deterministic context-free ωlanguages are considered in Section 5. Links with notions of ambiguity in context free languages are studied in Section 6. Section 7 is devoted to the special case of ω-powers.

Perspectives and some open questions are presented in last Section 8.

Context-free ω-languages

We assume the reader to be familiar with the theory of formal (ω)-languages [START_REF] Thomas | Automata on infinite objects[END_REF][START_REF] Staiger | ω-languages[END_REF]. We shall use usual notations of formal language theory. When X is a finite alphabet, a non-empty finite word over X is any sequence x = a 1 . . . a k , where a i ∈ X for i = 1, . . . , k , and k is an integer ≥ 1. The length of x is k, denoted by |x|. The empty word has no letters and is denoted by λ; its length is 0. For x = a 1 . . . a k , we write x(i) = a i and x[i] = x(1) . . . x(i) for i ≤ k and x[0] = λ. X ⋆ is the set of finite words (including the empty word) over X.

For V ⊆ X ⋆ , the complement of V (in X ⋆ ) is X ⋆ -V denoted V -.
The first infinite ordinal is ω. An ω-word over X is an ω -sequence a 1 . . . a n . . ., where for all integers i ≥ 1, a i ∈ X. When σ is an ω-word over X, we write σ = σ(1)σ(2) . . . σ(n) . . ., where for all i, σ(i) ∈ X, and σ

[n] = σ(1)σ(2) . . . σ(n) for all n ≥ 1 and σ[0] = λ.
The usual concatenation product of two finite words u and v is denoted u.v (and sometimes just uv). This product is extended to the product of a finite word u and an ω-word v: the infinite word u.v is then the ω-word such that:

(u.v)(k) = u(k) if k ≤ |u|, and (u.v)(k) = v(k -|u|) if k > |u|.
The prefix relation is denoted ⊑: a finite word u is a prefix of a finite word v (respectively, an infinite word v), denoted u ⊑ v, if and only if there exists a finite word w (respectively, an infinite word w), such that v = u.w. The set of ω-words over the alphabet X is denoted by X ω . An ω-language over an alphabet X is a subset of X ω . The complement (in X ω ) of an ω-language V ⊆ X ω is X ω -V , denoted V -. For V ⊆ X ⋆ , the ω-power of V is :

V ω = {σ = u 1 . . . u n . . . ∈ X ω | ∀i ≥ 1 u i ∈ V }.
We now define pushdown machines and the class of ω-context-free languages. Definition 1. A pushdown machine (PDM) is a 6-tuple M = (K, X, Γ, δ, q 0 , Z 0 ), where K is a finite set of states, X is a finite input alphabet, Γ is a finite pushdown alphabet, q 0 ∈ K is the initial state, Z 0 ∈ Γ is the start symbol, and δ is a mapping from K × (X ∪ {λ}) × Γ to finite subsets of K × Γ ⋆ . If γ ∈ Γ + describes the pushdown store content, the leftmost symbol will be assumed to be on "top" of the store. A configuration of a PDM is a pair (q, γ) where q ∈ K and γ ∈ Γ ⋆ . For a ∈ X ∪ {λ}, β, γ ∈ Γ ⋆ and Z ∈ Γ , if (p, β) is in δ(q, a, Z), then we write a : (q, Zγ) → M (p, βγ).

→ ⋆

M is the transitive and reflexive closure of → M . (The subscript M will be omitted whenever the meaning remains clear). Let σ = a 1 a 2 . . . a n . . . be an ω-word over X. An infinite sequence of configurations r = (q i , γ i ) i≥1 is called a complete run of M on σ, starting in configuration (p, γ), iff:

1. (q 1 , γ 1 ) = (p, γ) 2. for each i ≥ 1, there exists b i ∈ X ∪ {λ} satisfying b i : (q i , γ i ) → M (q i+1 , γ i+1 ) such that a 1 a 2 . . . a n . . . = b 1 b 2 . . . b n . . .
For every such run, In(r) is the set of all states entered infinitely often during run r.

A complete run r of M on σ , starting in configuration (q 0 , Z 0 ), will be simply called "a run of M on σ".

Definition 2. A Büchi pushdown automaton is a 7-tuple M = (K, X, Γ, δ, q 0 , Z 0 , F ) where M ′ = (K, X, Γ, δ, q 0 , Z 0 ) is a PDM and F ⊆ K is the set of final states. The ω-language accepted by M is

L(M ) = {σ ∈ X ω |
there exists a complete run r of M on σ such that In(r)∩F = ∅} Definition 3. A Muller pushdown automaton is a 7-tuple M = (K, X, Γ, δ, q 0 , Z 0 , F ) where M ′ = (K, X, Γ, δ, q 0 , Z 0 ) is a PDM and F ⊆ 2 K is the collection of designated state sets. The ω-language accepted by M is

L(M ) = {σ ∈ X ω | there exists a complete run r of M on σ such that In(r) ∈ F } Remark 4.
We consider here two acceptance conditions for ω-words, the Büchi and the Muller acceptance conditions, respectively denoted 2-acceptance and 3-acceptance in [START_REF] Landweber | Decision problems for ω-automata[END_REF] and in [START_REF] Cohen | ω-computations on deterministic pushdown machines[END_REF] and (inf, ⊓) and (inf, =) in [START_REF] Staiger | ω-languages[END_REF]. We refer the reader to [START_REF] Cohen | Theory of ω-languages, parts one and two[END_REF][START_REF] Cohen | ω-computations on deterministic pushdown machines[END_REF][START_REF] Staiger | ω-languages[END_REF][START_REF] Engelfriet | X-automata on ω-words[END_REF] for consideration of weaker acceptance conditions, and to [START_REF] Grädel | Automata, Logics, and Infinite Games: A Guide to Current Research [outcome of a Dagstuhl seminar[END_REF][START_REF] Perrin | Infinite words, automata, semigroups, logic and games[END_REF] for the definitions of other usual ones like Rabin, Street, or parity acceptance conditions. Notice however that it seems that the latter ones have not been much considered in the study of context-free ω-languages but they are often involved in constructions concerning finite automata reading infinite words.

Notation. In the sequel we shall often abbreviate "Muller pushdown automaton" by MPDA and "Büchi pushdown automaton" by BPDA.

Cohen and Gold and independently Linna established a characterization theorem for ωlanguages accepted by Büchi or Muller pushdown automata. We shall need the notion of "ω-Kleene closure" which we now firstly define:

Definition 5. For any family L of finitary languages, the ω-Kleene closure of L is :

ω-KC(L) = {∪ n i=1 U i .V ω i | ∀i ∈ [1, n] U i , V i ∈ L}
Theorem 6 (Linna [START_REF] Linna | On ω-words and ω-computations[END_REF], Cohen and Gold [START_REF] Cohen | Theory of ω-languages, parts one and two[END_REF]). Let CF L be the class of context-free (finitary) languages. Then for any ω-language L the following three conditions are equivalent:

1. L ∈ ω-KC(CF L).

2. There exists a BP DA that accepts L.

3. There exists a M P DA that accepts L.

In [START_REF] Cohen | Theory of ω-languages, parts one and two[END_REF] are also studied ω-languages generated by ω-context-free grammars and it is shown that each of the conditions 1), 2), and 3) of the above Theorem is also equivalent to: 4) L is generated by a context-free grammar G by leftmost derivations. These grammars are also studied by Nivat in [START_REF] Nivat | Mots infinis engendrés par une grammaire algébrique[END_REF][START_REF] Nivat | Sur les ensembles de mots infinis engendrés par une grammaire algébrique[END_REF]. Then we can let the following definition:

Definition 7.
An ω-language is a context-free ω-language iff it satisfies one of the conditions of the above Theorem. The class of context-free ω-languages will be denoted by CF L ω .

If we omit the pushdown store in the above Theorem we obtain the characterization of languages accepted by classical Muller automata (MA) or Büchi automata (BA) :

Theorem 8. For any ω-language L, the following conditions are equivalent:

1. L belongs to ω-KC(REG),
where REG is the class of finitary regular languages. 2. There exists a MA that accepts L. 3. There exists a BA that accepts L.

An ω-language L satisfying one of the conditions of the above Theorem is called a regular ω-language. The class of regular ω-languages will be denoted by REG ω .

It follows from Mc Naughton's Theorem that the expressive power of deterministic MA (DMA) is equal to the expressive power of non deterministic MA, i.e. that every regular ω-language is accepted by a deterministic Muller automaton, [START_REF] Naughton | Testing and generating infinite sequences by a finite automaton[END_REF][START_REF] Perrin | Infinite words, automata, semigroups, logic and games[END_REF]. Notice that Choueka gave a simplified proof of Mc Naughton's Theorem in [START_REF] Choueka | Theories of automata on omega-tapes: A simplified approach[END_REF]. Another variant was given by Rabin in [START_REF] Rabin | Decidability of second-order theories and automata on infinite trees[END_REF]. Unlike the case of finite automata, deterministic M P DA do not define the same class of ω-languages as non deterministic M P DA. Let us now define deterministic pushdown machines. Definition 9. A P DM M = (K, X, Γ, δ, q 0 , Z 0 ) is said to be deterministic iff for each q ∈ K, Z ∈ Γ , and a ∈ X:

1. δ(q, a, Z) contains at most one element, 2. δ(q, λ, Z) contains at most one element, and 3. if δ(q, λ, Z) is non empty, then δ(q, a, Z) is empty for all a ∈ X.

It turned out that the class of ω-languages accepted by deterministic BP DA is strictly included into the class of ω-languages accepted by deterministic M P DA. This latest class is the class DCF L ω of deterministic context-free ω-languages. We denote DCF L the class of deterministic context-free (finitary) languages.

Proposition 10 ([20]).

1. DCF L ω is closed under complementation, but is neither closed under union, nor under intersection. 2. DCF L ω ω-KC(DCF L) CF L ω (these inclusions are strict).

3 Topology

Borel hierarchy and analytic sets

We assume the reader to be familiar with basic notions of topology which may be found in [START_REF] Moschovakis | Descriptive set theory[END_REF][START_REF] Lescow | Logical specifications of infinite computations[END_REF][START_REF] Kechris | Classical descriptive set theory[END_REF][START_REF] Staiger | ω-languages[END_REF][START_REF] Perrin | Infinite words, automata, semigroups, logic and games[END_REF]. There is a natural metric on the set X ω of infinite words over a finite alphabet X containing at least two letters which is called the prefix metric and defined as follows. For u, v ∈ X ω and u = v let δ(u, v) = 2 -l pref(u,v) where l pref(u,v) is the first integer n such that u(n + 1) is different from v(n + 1). This metric induces on X ω the usual Cantor topology for which open subsets of X ω are in the form W.X ω , where W ⊆ X ⋆ . A set L ⊆ X ω is a closed set iff its complement X ω -L is an open set. Define now the Borel Hierarchy of subsets of X ω :

Definition 11. For a non-null countable ordinal α, the classes Σ 0 α and Π 0 α of the Borel Hierarchy on the topological space X ω are defined as follows: Σ 0 1 is the class of open subsets of X ω , Π 0 1 is the class of closed subsets of X ω , and for any countable ordinal α ≥ 2:

Σ 0 α is the class of countable unions of subsets of X ω in γ<α Π 0 γ . Π 0 α is the class of countable intersections of subsets of X ω in γ<α Σ 0 γ .
Recall some basic results about these classes :

Proposition 12. (a) Σ 0 α ∪ Π 0 α Σ 0 α+1 ∩ Π 0 α+1 , for each countable ordinal α ≥ 1. (b) ∪ γ<α Σ 0 γ = ∪ γ<α Π 0 γ Σ 0 α ∩ Π 0 α , for each countable limit ordinal α. (c) A set W ⊆ X ω is in the class Σ 0 α iff its complement is in the class Π 0 α . (d) Σ 0 α -Π 0 α = ∅ and Π 0 α -Σ 0 α = ∅ hold for every countable ordinal α ≥ 1.
For a countable ordinal α, a subset of X ω is a Borel set of rank α iff it is in

Σ 0 α ∪ Π 0 α but not in γ<α (Σ 0 γ ∪ Π 0 γ ).
There are also some subsets of X ω which are not Borel. Indeed there exists another hierarchy beyond the Borel hierarchy, which is called the projective hierarchy and which is obtained from the Borel hierarchy by successive applications of operations of projection and complementation. The first level of the projective hierarchy is formed by the class of analytic sets and the class of co-analytic sets which are complements of analytic sets. In particular the class of Borel subsets of X ω is strictly included into the class Σ 1 1 of analytic sets which are obtained by projection of Borel sets.

Definition 13. A subset A of X ω is in the class Σ 1 1 of analytic sets iff there exist a finite alphabet Y and a Borel subset B of (X × Y ) ω such that x ∈ A ↔ ∃y ∈ Y ω such that (x, y) ∈ B, where (x, y) is the infinite word over the alphabet X × Y such that (x, y)(i) = (x(i), y(i)) for each integer i ≥ 1. Remark 14. In the above definition we could take B in the class Π 0 2 . Moreover analytic subsets of X ω are the projections of Π 0 1 -subsets of X ω × ω ω , where ω ω is the Baire space, [START_REF] Moschovakis | Descriptive set theory[END_REF].

We now define completeness with regard to reduction by continuous functions. For a countable ordinal α ≥ 1, a set F ⊆ X ω is said to be a Σ 0 α (respectively, Π 0 α , Σ 1 1 )complete set iff for any set E ⊆ Y ω (with Y a finite alphabet):

E ∈ Σ 0 α (respectively, E ∈ Π 0 α , E ∈ Σ 1 1
) iff there exists a continuous function f : Y ω → X ω such that E = f -1 (F ). Σ 0 n (respectively Π 0 n )-complete sets, with n an integer ≥ 1, are thoroughly characterized in [START_REF] Staiger | Hierarchies of recursive ω-languages[END_REF].

In particular R = (0 ⋆ .1) ω is a well known example of Π 0 2 -complete subset of {0, 1} ω . It is the set of ω-words over {0, 1} having infinitely many occurrences of the letter 1.

Its complement {0, 1} ω -(0 ⋆ .1) ω is a Σ 0 2 -complete subset of {0, 1} ω .
We recall now the definition of the arithmetical hierarchy of ω-languages which form the effective analogue to the hierarchy of Borel sets of finite rank. Let X be a finite alphabet. An ω-language L ⊆ X ω belongs to the class Σ n if and only if there exists a recursive relation

R L ⊆ (N) n-1 × X ⋆ such that L = {σ ∈ X ω | Q 1 a 1 Q 2 a 2 . . . Q n a n (a 1 , . . . , a n-1 , σ[a n + 1]) ∈ R L }
where Q 1 is the existential quantifier ∃, and every other Q i , for 2 ≤ i ≤ n, is one of the quantifiers ∀ or ∃ (not necessarily in an alternating order). An ω-language L ⊆ X ω belongs to the class Π n if and only if its complement X ω -L belongs to the class Σ n .

The inclusion relations that hold between the classes Σ n and Π n are the same as for the corresponding classes of the Borel hierarchy. The classes Σ n and Π n are included in the respective classes Σ 0 n and Σ 0 n of the Borel hierarchy, and cardinality arguments suffice to show that these inclusions are strict.

As in the case of the Borel hierarchy, projections of arithmetical sets (of the second Π-class) lead beyond the arithmetical hierarchy, to the analytical hierarchy of ωlanguages. The first class of this hierarchy is the class Σ 1 1 of effective analytic sets which are obtained by projection of arithmetical sets. An ω-language L ⊆ X ω belongs to the class Σ 1 1 if and only if there exists a recursive relation

R L ⊆ N × {0, 1} ⋆ × X ⋆ such that: L = {σ ∈ X ω | ∃τ (τ ∈ {0, 1} ω ∧ ∀n∃m((n, τ [m], σ[m]) ∈ R L ))} Then an ω-language L ⊆ X ω is in the class Σ 1
1 iff it is the projection of an ωlanguage over the alphabet X × {0, 1} which is in the class Π 2 . The class Π 1 1 of effective co-analytic sets is simply the class of complements of effective analytic sets. We denote as usual

∆ 1 1 = Σ 1 1 ∩ Π 1 1 . Recall that an ω-language L ⊆ X ω is in the class Σ 1
1 iff it is accepted by a non deterministic Turing machine (reading ω-words) with a Büchi or Muller acceptance condition [START_REF] Staiger | ω-languages[END_REF].

The Borel ranks of ∆ 1 1 sets are the (recursive) ordinals γ < ω CK 1 , where ω CK 1 is the first non-recursive ordinal, usually called the Church-Kleene ordinal. Moreover, for every non null ordinal α < ω CK 1 , there exist some Σ 0 α -complete and some Π 0 α -complete sets in the class ∆ 1 1 .

On the other hand, Kechris, Marker and Sami proved in [START_REF] Kechris | Π 1 1 Borel sets[END_REF] that the supremum of the set of Borel ranks of (effective) Σ 1 1 -sets is the ordinal γ 1 2 . This ordinal is proved to be strictly greater than the ordinal δ 1 2 which is the first non ∆ 1 2 ordinal. In particular, the ordinal γ 1 2 is strictly greater than the ordinal ω CK 1 . Remark that the exact value of the ordinal γ 1 2 may depend on axioms of set theory, see [START_REF] Kechris | Π 1 1 Borel sets[END_REF][START_REF] Finkel | Borel ranks and Wadge degrees of omega context free languages[END_REF] for more details. Notice also that it seems still unknown whether every non null ordinal γ < γ 1 2 is the Borel rank of a Σ 1 1 -set.

Wadge hierarchy

We now introduce the Wadge hierarchy, which is a great refinement of the Borel hierarchy defined via reductions by continuous functions, [START_REF] Duparc | Wadge hierarchy and Veblen hierarchy: Part 1: Borel sets of finite rank[END_REF][START_REF] Wadge | Reducibility and determinateness in the Baire space[END_REF].

Definition 15 (Wadge [83]). Let X, Y be two finite alphabets. For L ⊆ X ω and

L ′ ⊆ Y ω , L is said to be Wadge reducible to L ′ (L ≤ W L ′ ) iff there exists a continuous function f : X ω → Y ω , such that L = f -1 (L ′ ).
L and L ′ are Wadge equivalent iff L ≤ W L ′ and L ′ ≤ W L. This will be denoted by

L ≡ W L ′ . And we shall say that L < W L ′ iff L ≤ W L ′ but not L ′ ≤ W L. A set L ⊆ X ω is said to be self dual iff L ≡ W L -,
. For L ⊆ X ω and L ′ ⊆ Y ω , if L ≤ W L ′ and L = f -1 (L ′ ) where f is a continuous function from X ω into Y ω , then f is called a continuous reduction of L to L ′ .
Intuitively it means that L is less complicated than L ′ because to check whether x ∈ L it suffices to check whether f (x) ∈ L ′ where f is a continuous function. Hence the Wadge degree of an ω-language is a measure of its topological complexity.

Notice that in the above definition, we consider that a subset L ⊆ X ω is given together with the alphabet X. This is important as it is shown by the following simple example.

Let

L 1 = {0, 1} ω ⊆ {0, 1} ω and L 2 = {0, 1} ω ⊆ {0, 1, 2} ω . So the languages L 1 and L 2 are equal but considered over the different alphabets X 1 = {0, 1} and X 2 = {0, 1, 2}. It turns out that L 1 < W L 2 . In fact L 1 is open and closed in X ω 1 while L 2 is closed but non open in X ω 2 .
We can now define the Wadge class of a set L:

Definition 16. Let L be a subset of X ω . The Wadge class of L is : [L] = {L ′ | L ′ ⊆ Y ω for a finite alphabet Y and L ′ ≤ W L}. Recall that each Borel class Σ 0 α and Π 0 α is a Wadge class. A set L ⊆ X ω is a Σ 0 α (respectively Π 0 α )-complete set iff for any set L ′ ⊆ Y ω , L ′ is in Σ 0 α (respectively Π 0 α ) iff L ′ ≤ W L . It follows from the study of the Wadge hierarchy that a set L ⊆ X ω is a Σ 0 α (respectively, Π 0 α )-complete set iff it is in Σ 0 α but not in Π 0 α (respectively, in Π 0 α but not in Σ 0 α ).
There is a close relationship between Wadge reducibility and games which we now introduce.

Definition 17. Let L ⊆ X ω and L ′ ⊆ Y ω . The Wadge game W (L, L ′
) is a game with perfect information between two players, player 1 who is in charge of L and player 2 who is in charge of L ′ . Player 1 first writes a letter a 1 ∈ X, then player 2 writes a letter b 1 ∈ Y , then player 1 writes a letter a 2 ∈ X, and so on.

The two players alternatively write letters a n of X for player 1 and b n of Y for player 2.

After ω steps, player 1 has written an ω-word a ∈ X ω and player 2 has written an ω-word b ∈ Y ω . Player 2 is allowed to skip, even infinitely often, provided he really writes an ω-word in ω steps. Player 2 wins the play iff

[a ∈ L ↔ b ∈ L ′ ], i.e. iff : [(a ∈ L and b ∈ L ′ ) or (a / ∈ L and b / ∈ L ′ and b is infinite)].
Recall that a strategy for player 1 is a function σ : (Y ∪ {s}) ⋆ → X. And a strategy for player 2 is a function f :

X + → Y ∪ {s}.
σ is a winning stategy for player 1 iff he always wins a play when he uses the strategy σ, i.e. when the n th letter he writes is given by

a n = σ(b 1 . . . b n-1 )
, where b i is the letter written by player 2 at step i and b i = s if player 2 skips at step i.

A winning strategy for player 2 is defined in a similar manner.

Martin's Theorem states that every Gale-Stewart Game G(B), with B a Borel set, is determined, i.e. that one of the two players has a winning strategy in the game G(B), see [START_REF] Kechris | Classical descriptive set theory[END_REF]. This implies the following determinacy result :

Theorem 18 (Wadge). Let L ⊆ X ω and L ′ ⊆ Y ω be two Borel sets, where X and Y are finite alphabets. Then the Wadge game W (L, L ′ ) is determined : one of the two players has a winning strategy. And L ≤ W L ′ iff player 2 has a winning strategy in the game W (L, L ′ ).

Theorem 19 (Wadge). Up to the complement and ≡ W , the class of Borel subsets of X ω , for a finite alphabet X, is a well ordered hierarchy. There is an ordinal |W H|, called the length of the hierarchy, and a map

d 0 W from W H onto |W H| -{0}, such that for all L, L ′ ⊆ X ω : d 0 W L < d 0 W L ′ ↔ L < W L ′ and d 0 W L = d 0 W L ′ ↔ [L ≡ W L ′ or L ≡ W L ′-].
The Wadge hierarchy of Borel sets of finite rank has length 1 ε 0 where 1 ε 0 is the limit of the ordinals α n defined by α 1 = ω 1 and α n+1 = ω αn 1 for n a non negative integer, ω 1 being the first non countable ordinal. Then 1 ε 0 is the first fixed point of the ordinal exponentiation of base ω 1 . The length of the Wadge hierarchy of Borel sets in ∆ 0 ω = Σ 0 ω ∩ Π 0 ω is the ω th 1 fixed point of the ordinal exponentiation of base ω 1 , which is a much larger ordinal. The length of the whole Wadge hierarchy of Borel sets is a huge ordinal, with regard to the ω th 1 fixed point of the ordinal exponentiation of base ω 1 . It is described in [START_REF] Wadge | Reducibility and determinateness in the Baire space[END_REF][START_REF] Duparc | Wadge hierarchy and Veblen hierarchy: Part 1: Borel sets of finite rank[END_REF] by the use of the Veblen functions.

Topological complexity of context-free ω-languages

We recall first results about the topological complexity of regular ω-languages. Topological properties of regular ω-languages were first studied by L. H. Landweber in [START_REF] Landweber | Decision problems for ω-automata[END_REF] where he characterized regular ω-languages in a given Borel class. It turned out that a regular ω-language is a Π 0 2 -set iff it is accepted by a deterministic Büchi automaton. On the other hand Mc Naughton's Theorem implies that regular ω-languages, accepted by deterministic Muller automata, are boolean combinations of regular ω-languages accepted by deterministic Büchi automata. Thus they are boolean combinations of Π 0 2sets hence ∆ 0 3 -sets. Moreover Landweber proved that one can effectively determine the exact level of a given regular ω-language with regard to the Borel hierarchy. A great improvement of these results was obtained by Wagner who determined in an effective way, using the notions of chains and superchains, the Wadge hierarchy of the class REG ω , [START_REF] Wagner | On ω-regular sets[END_REF]. This hierarchy has length ω ω and is now called the Wagner hierarchy, [START_REF] Selivanov | Fine hierarchy of regular ω-languages[END_REF][START_REF] Selivanov | Wadge degrees of ω-languages of deterministic Turing machines[END_REF][START_REF] Selivanov | Wadge degrees of ω-languages of deterministic Turing machines[END_REF][START_REF] Selivanov | Fine hierarchy of regular ω-languages[END_REF][START_REF] Staiger | ω-languages[END_REF]. Wilke and Yoo proved in [START_REF] Wilke | Computing the Wadge degree, the Lifschitz degree, and the Rabin index of a regular language of infinite words in polynomial time[END_REF] that one can compute in polynomial time the Wadge degree of a regular ω-language. Later Carton and Perrin gave a presentation of the Wagner hierarchy using algebraic notions of ω-semigroups, [START_REF] Carton | The Wagner hierarchy of ω-rational sets[END_REF][START_REF] Carton | Chains and superchains for ω-rational sets, automata and semigroups[END_REF][START_REF] Perrin | Infinite words, automata, semigroups, logic and games[END_REF]. This work was completed by Duparc and Riss in [START_REF] Duparc | The missing link for ω-rational sets, automata, and semigroups[END_REF].

Context-free ω-languages beyond the class ∆ 0 3 have been constructed for the first time in [START_REF] Finkel | Topological properties of omega context free languages[END_REF]. The construction used an operation of exponentiation of sets of finite or infinite words introduced by Duparc in his study of the Wadge hierarchy [START_REF] Duparc | Wadge hierarchy and Veblen hierarchy: Part 1: Borel sets of finite rank[END_REF]. We are going now to recall these constructions although some stronger results on the topological complexity of context-free ω-languages were obtained later in [START_REF] Finkel | Borel ranks and Wadge degrees of context free ω-languages[END_REF][START_REF] Finkel | Borel ranks and Wadge degrees of omega context free languages[END_REF] by other methods. However the methods of [START_REF] Finkel | Topological properties of omega context free languages[END_REF] using Duparc's operation of exponentiation are also interesting and it gave other results on ambiguity and on ω-powers of context-free languages we can not (yet ?) get by other methods, see Sections 6 and 7 below.

Wadge gave a description of the Wadge hierarchy of Borel sets in [START_REF] Wadge | Reducibility and determinateness in the Baire space[END_REF]. Duparc recently got a new proof of Wadge's results and gave in [START_REF] Duparc | La forme Normale des Boréliens de rang finis[END_REF][START_REF] Duparc | Wadge hierarchy and Veblen hierarchy: Part 1: Borel sets of finite rank[END_REF] a normal form of Borel sets in the class ∆ 0 ω , i.e. an inductive construction of a Borel set of every given degree smaller than the ω th 1 fixed point of the ordinal exponentiation of base ω 1 . The construction relies on set theoretic operations which are the counterpart of arithmetical operations over ordinals needed to compute the Wadge degrees. Actually Duparc studied the Wadge hierarchy via the study of the conciliating hierarchy. Conciliating sets are sets of finite or infinite words over an alphabet X, i.e. subsets of X ⋆ ∪ X ω = X ≤ω . It turned out that the conciliating hierarchy is isomorphic to the Wadge hierarchy of non-self-dual Borel sets, via the correspondence A → A d we recall now:

For a word x ∈ (X ∪ {d}) ≤ω we denote by x(/d) the sequence obtained from x by removing every occurrence of the letter d. Then for A ⊆ X ≤ω and d a letter not in X, A d is the ω-language over X ∪ {d} which is defined by :

A d = {x ∈ (X ∪ {d}) ω | x(/d) ∈ A}.
We are going now to introduce the operation of exponentiation of conciliating sets.

Definition 20 (Duparc [23]). Let X be a finite alphabet, և / ∈ X, and let x be a finite or infinite word over the alphabet Y = X ∪ {և}. Then x և is inductively defined by: λ և = λ, and for a finite word u ∈ (X ∪ {և}) ⋆ :

(u.a) և = u և .a, if a ∈ X, (u. և) և = u և (1).u և (2) . . . u և (|u և | -1) if |u և | > 0, (u. և) և = λ if |u և | = 0,
and for u infinite:

(u) և = lim n∈ω (u[n]) և , where, given β n and v in X ⋆ , v ⊑ lim n∈ω β n ↔ ∃n∀p ≥ n β p [|v|] = v.
(The finite or infinite word lim n∈ω β n is determined by the set of its (finite) prefixes).

Remark 21. For x ∈ Y ≤ω , x և denotes the string x, once every և occuring in x has been "evaluated" to the back space operation, proceeding from left to right inside x. In other words x և = x from which every interval of the form "a և " (a ∈ X) is removed.

For example if u = (a և) n , for n an integer ≥ 1, or u = (a և) ω , or u = (a ևև) ω , then (u) և = λ. If u = (ab և) ω then (u) և = a ω and if u = bb(և a) ω then (u) և = b.
Let us notice that in Definition 20 the limit is not defined in the usual way: We can now define the operation A → A ∼ of exponentiation of conciliating sets: Definition 22 (Duparc [23]). For A ⊆ X ≤ω and և / ∈ X, let

A ∼ = df {x ∈ (X ∪ {և}) ≤ω | x և ∈ A}.
The operation ∼ is monotone with regard to the Wadge ordering and produces some sets of higher complexity.

Theorem 23 (Duparc [23] ).

Let A ⊆ X ≤ω and n ≥ 1. if A d ⊆ (X ∪ {d}) ω is a Σ 0 n -complete (respectively, Π 0 n -complete) set, then (A ∼ ) d is a Σ 0 n+1 -complete (re- spectively, Π 0 n+1 -complete) set.
It was proved in [START_REF] Finkel | Topological properties of omega context free languages[END_REF] that the class of context-free infinitary languages (which are unions of a context-free finitary language and of a context-free ω-language) is closed under the operation A → A ∼ . On the other hand A → A d is an operation from the class of context-free infinitary languages into the class of context-free ω-languages. This implies that, for each integer n ≥ 1, there exist some context-free ω-languages which are Σ 0 n -complete and some others which are Π 0 n -complete.

Theorem 24 ([32]). For each non negative integer n ≥ 1, there exist Σ 0 n -complete context-free ω-languages A n and Π 0 n -complete context-free ω-languages B n .

Proof. For n = 1 consider the Σ 0 1 -complete regular ω-language A 1 = {α ∈ {0, 1} ω | ∃i α(i) = 1} and the Π 0 1 -complete regular ω-language B 1 = {α ∈ {0, 1} ω | ∀i α(i) = 0}. These languages are context-free ω-languages because REG ω ⊆ CF L ω . Now consider the Σ 0 2 -complete regular ω-language A 2 = {α ∈ {0, 1} ω | ∃ <ω i α(i) = 1} and the Π 0 2 -complete regular ω-language B 2 = {α ∈ {0, 1} ω | ∃ ω i α(i) = 0},
where ∃ <ω i means: " there exist only finitely many i such that . . ." , and ∃ ω i means: " there exist infinitely many i such that . . .". A 2 and B 2 are context-free ω-languages because they are regular ω-languages.

To obtain context-free ω-languages of greater Borel ranks, consider now O 1 (respectively, C 1 ) subsets of {0, 1} ≤ω such that

(O 1 ) d (respectively, (C 1 ) d ) are Σ 0 1 -complete ( respectively Π 0 1 -complete ) . For example O 1 = {x ∈ {0, 1} ≤ω | ∃ i x(i) = 1} and C 1 = {λ}.
We can apply n ≥ 1 times the operation of exponentiation of sets. More precisely, we define, for a set A ⊆ X ≤ω :

A ∼.0 = A A ∼.1 = A ∼ and A ∼.(n+1) = (A ∼.n ) ∼ .
Now apply n times (for an integer n ≥ 1) the operation ∼ (with different new letters

և 1 , և 2 , և 3 , . . . , և n ) to O 1 and C 1 .
By Theorem 23, it holds that for an integer n ≥ 1:

(O ∼.n 1 ) d is a Σ 0 n+1 -complete subset of {0, 1, և 1 , . . . , և n , d} ω . (C ∼.n 1 ) d is a Π 0 n+1 -complete subset of {0, 1, և 1 , . . . , և n , d} ω .
And it is easy to see that O This gave a partial answer to questions of Thomas and Lescow [START_REF] Lescow | Logical specifications of infinite computations[END_REF] about the hierarchy of context-free ω-languages. A natural question now arose: Do the decidability results of [START_REF] Landweber | Decision problems for ω-automata[END_REF] extend to context-free ω-languages? Unfortunately the answer is no. Cohen and Gold proved that one cannot decide whether a given context-free ω-language is in the class Π 0 1 , Σ 0 1 , or Π 0 2 , [START_REF] Cohen | Theory of ω-languages, parts one and two[END_REF]. This result was first extended to all classes Σ 0 n and Π 0 n , for n an integer ≥ 1, using the undecidability of the Post Correspondence Problem, [START_REF] Finkel | Topological properties of omega context free languages[END_REF].

Later, the coding of an infinite number of erasers և n , n ≥ 1, and an iteration of the operation of exponentiation were used to prove that there exist some context-free ωlanguages which are Borel of infinite rank, [START_REF] Finkel | On omega context free languages which are Borel sets of infinite rank[END_REF].

Using the correspondences between the operation of exponentiation of sets and the ordinal exponentiation of base ω 1 , and between the Wadge's operation of sum of sets, [START_REF] Wadge | Reducibility and determinateness in the Baire space[END_REF][START_REF] Duparc | Wadge hierarchy and Veblen hierarchy: Part 1: Borel sets of finite rank[END_REF], and the ordinal sum, it was proved in [START_REF] Finkel | Wadge hierarchy of omega context free languages[END_REF] that the length of the Wadge hierarchy of the class CF L ω is at least ε 0 , the first fixed point of the ordinal exponentiation of base ω. Next were constructed some ∆ 0 ω context-free ω-languages in ε ω Wadge degrees, where ε ω is the ω th fixed point of the ordinal exponentiation of base ω, and also some Σ 0 ω -complete context-free ω-languages, [START_REF] Finkel | On the Wadge hierarchy of omega context free languages[END_REF][START_REF] Finkel | On the length of the Wadge hierarchy of ω-context free languages[END_REF]. Notice that the Wadge hierarchy of non-deterministic context-free ω-languages is not effective, [START_REF] Finkel | Wadge hierarchy of omega context free languages[END_REF].

The question of the existence of non-Borel context-free ω-languages was solved by Finkel and Ressayre. Using a coding of infinite binary trees labeled in a finite alphabet X, it was proved that there exist some non-Borel, and even Σ 1 1 -complete, context-free ω-languages, and that one cannot decide whether a given context-free ω-language is a Borel set, [START_REF] Finkel | Borel hierarchy and omega context free languages[END_REF]. Amazingly there is a simple finitary language V accepted by a 1counter automaton such that V ω is Σ 1 1 -complete; we shall recall it in Section 7 below on ω-powers.

But a complete and very surprising result was obtained in [START_REF] Finkel | Borel ranks and Wadge degrees of context free ω-languages[END_REF][START_REF] Finkel | Borel ranks and Wadge degrees of omega context free languages[END_REF], which extended previous results. A simulation of multicounter automata by 1-counter automata was used in [START_REF] Finkel | Borel ranks and Wadge degrees of context free ω-languages[END_REF][START_REF] Finkel | Borel ranks and Wadge degrees of omega context free languages[END_REF]. We firstly recall now the definition of these automata, in order to sketch the constructions involved in these simulations. Definition 25. Let k be an integer ≥ 1. A k-counter machine (k-CM) is a 4-tuple M=(K, X, ∆, q 0 ), where K is a finite set of states, X is a finite input alphabet, q 0 ∈ K is the initial state, and ∆ ⊆ K ×(X ∪{λ})×{0, 1} k ×K ×{0, 1, -1} k is the transition relation. The k-counter machine M is said to be real time iff:

∆ ⊆ K × X × {0, 1} k × K × {0, 1, -1} k , i.e.

iff there are not any λ-transitions.

If the machine M is in state q and c i ∈ N is the content of the i th counter C i then the configuration (or global state) of M is the (k + 1)-tuple (q, c 1 , . . . , c k ).

For a ∈ X ∪ {λ}, q, q ′ ∈ K and (c 1 , . . . , c k ) ∈ N k such that c j = 0 for j ∈ E ⊆ {1, . . . , k} and c j > 0 for j / ∈ E, if (q, a, i 1 , . . . , i k , q ′ , j 1 , . . . , j k ) ∈ ∆ where i j = 0 for j ∈ E and i j = 1 for j / ∈ E, then we write:

a : (q, c 1 , . . . , c k ) → M (q ′ , c 1 + j 1 , . . . , c k + j k )
Thus we see that the transition relation must satisfy: if (q, a, i 1 , . . . , i k , q ′ , j 1 , . . . , j k ) ∈ ∆ and i m = 0 for some m ∈ {1, . . . , k}, then j m = 0 or j m = 1 (but j m cannot be equal to -1).

Let σ = a 1 a 2 . . . a n . . . be an ω-word over X. An ω-sequence of configurations r = (q i , c i 1 , . . . c i k ) i≥1 is called a run of M on σ, starting in configuration (p, c 1 , . . . , c k ), iff:

(1) (q 1 , c 1 1 , . . . c 1 k ) = (p, c 1 , . . . , c k ) (2) for each i ≥ 1, there exists b i ∈ X ∪ {λ} such that b i : (q i , c i 1 , . . . c i k ) → M (q i+1 , c i+1 1 , . . . c i+1 k ) such that either a 1 a 2 . . . a n . . . = b 1 b 2 . . . b n . . . or b 1 b 2 . . . b n . . . is a finite prefix of a 1 a 2 . . . a n . . .
The run r is said to be complete when a 1 a 2 . . . a n . . . = b 1 b 2 . . . b n . . . For every such run, In(r) is the set of all states entered infinitely often during run r. A complete run r of M on σ, starting in configuration (q 0 , 0, . . . , 0), will be simply called "a run of M on σ". Definition 26. A Büchi k-counter automaton is a 5-tuple M=(K, X, ∆, q 0 , F ), where M ′ =(K, X, ∆, q 0 ) is a k-counter machine and F ⊆ K is the set of accepting states. The ω-language accepted by M is

L(M)= {σ ∈ X ω | there exists a run r of M on σ such that In(r) ∩ F = ∅}
The notion of Muller k-counter automaton is defined in a similar way. One can see that an ω-language is accepted by a (real time) Büchi k-counter automaton iff it is accepted by a (real time) Muller k-counter automaton [START_REF] Engelfriet | X-automata on ω-words[END_REF]. Notice that this result is no longer true in the deterministic case. We denote BC(k) (respectively, r-BC(k)) the class of Büchi k-counter automata (respectively, of real time Büchi k-counter automata. We denote BCL(k) ω (respectively, r-BCL(k) ω ) the class of ω-languages accepted by Büchi k-counter automata (respectively, by real time Büchi k-counter automata).

Remark that 1-counter automata introduced above are equivalent to pushdown automata whose stack alphabet is in the form {Z 0 , A} where Z 0 is the bottom symbol which always remains at the bottom of the stack and appears only there and A is another stack symbol. The pushdown stack may be seen like a counter whose content is the integer N if the stack content is the word A N .Z 0 . In the model introduced here the counter value cannot be increased by more than 1 during a single transition. However this does not change the class of ω-languages accepted by such automata. So the class BCL(1) ω is equal to the class 1-ICL ω , introduced in [START_REF] Finkel | Wadge hierarchy of omega context free languages[END_REF], and it is a strict subclass of the class CFL ω of context-free ω-languages accepted by Büchi pushdown automata.

We state now the surprising result proved in [START_REF] Finkel | Borel ranks and Wadge degrees of omega context free languages[END_REF], using multicounter-automata.

Theorem 27 ([41]). The Wadge hierarchy of the class r-BCL(1) ω , hence also of the class CFL ω , or of every class C such that r-BCL(1) ω ⊆ C⊆ Σ 1 1 , is the Wadge hierarchy of the class Σ 1 1 of ω-languages accepted by Turing machines with a Büchi acceptance condition.

We now sketch the proof of this result. It is well known that every Turing machine can be simulated by a (non real time) 2-counter automaton, see [START_REF] Hopcroft | Introduction to automata theory, languages, and computation[END_REF]. Thus the Wadge hierarchy of the class BCL(2) ω is also the Wadge hierarchy of the class of ω-languages accepted by Büchi Turing machines. One can then find, from an ω-language L ⊆ X ω in BCL(2) ω , another ω-language θ S (L) which will be of the same topological complexity but accepted by a real-time 8-counter Büchi automaton. The idea is to add firstly a storage type called a queue to a 2-counter Büchi automaton in order to read ω-words in real-time. Then the queue can be simulated by two pushdown stacks or by four counters. This simulation is not done in real-time but a crucial fact is that one can bound the number of transitions needed to simulate the queue. This allows to pad the strings in L with enough extra letters so that the new words will be read in real-time by a 8-counter Büchi automaton. The padding is obtained via the function θ S which we define now.

Let X be an alphabet having at least two letters, E be a new letter not in X, S be an integer ≥ 1, and θ S : X ω → (X ∪ {E}) ω be the function defined, for all x ∈ X ω , by: 2) ω then there exists an integer S ≥ 1 such that θ S (L) is in the class r-BCL( 8) ω , and, except for some special few cases, θ S (L) ≡ W L. The next step is to simulate a real-time 8-counter Büchi automaton, using only a realtime 1-counter Büchi automaton.

θ S (x) = x(1).E S .x(2).E S 2 .x(3).E S 3 .x(4) . . . x(n).E S n .x(n + 1).E S n+1 . . . It turns out that if L ⊆ X ω is in BCL(
Consider the product of the eight first prime numbers:

K = 2 × 3 × 5 × 7 × 11 × 13 × 17 × 19 = 9699690
Then an ω-word x ∈ X ω can be coded by the ω-word

h(x) = A.0 K .x(1).B.0 K 2 .A.0 K 2 .x(2).B.0 K 3 .A.0 K 3 .x(3).B . . . B.0 K n .A.0 K n .x(n).B . . .
where A, B and 0 are new letters not in X. The mapping h : X ω → (X ∪ {A, B, 0}) ω is continuous. It is easy to see that the ω-language h(X ω ) -is an open subset of (X ∪ {A, B, 0}) ω and that it is in the class r-BCL(1) ω .

If L(A) ⊆ X ω is accepted by a real time 8-counter Büchi automaton A, then one can construct effectively from A a 1-counter Büchi automaton B, reading words over the alphabet X ∪ {A, B, 0}, such that

L(A)= h -1 (L(B)), i.e. ∀x ∈ X ω h(x) ∈ L(B) ←→ x ∈ L(A)
In fact, the simulation, during the reading of h(x) by the 1-counter Büchi automaton B, of the behaviour of the real time 8-counter Büchi automaton A reading x, can be achieved, using the coding of the content (c 1 , c 2 , . . . , c 8 ) of eight counters by the product 2 c1 × 3 c2 × . . . × (17) c7 × (19) c8 , and the special shape of ω-words in h(X ω ) which allows the propagation of the value of the counters of A. A crucial fact here is that h(X ω ) -is in the class r-BCL(1) ω . Thus the ω-language

h(L(A)) ∪ h(X ω ) -= L(B) ∪ h(X ω ) -
is in the class BCL [START_REF] Andretta | The use of complexity hierarchies in descriptive set theory and automata theory[END_REF] ω and it has the same topological complexity as the ω-language L(A), (except the special few cases where d W (L(A)) ≤ ω).

One can see, from the construction of B, that at most (K -1) consecutive λ-transitions can occur during the reading of an ω-word x by B. It is then easy to see that the ωlanguage φ(h(L(A))∪h(X ω ) -) is an ω-language in the class r-BCL( 1) ω which has the same topological complexity as the ω-language L(A), where φ is the mapping from (X ∪ {A, B, 0}) ω into (X ∪ {A, B, F, 0}) ω , with F a new letter, which is defined by:

φ(x) = F K-1 .x(1).F K-1 .x(2).F K-1 .x(3) . . . F K-1 .x(n).F K-1 .x(n+1).F K-1 . . .
Altogether these constructions are used in [START_REF] Finkel | Borel ranks and Wadge degrees of omega context free languages[END_REF] to prove Theorem 27. As the Wadge hierarchy is a refinement of the Borel hierarchy and, for any countable ordinal α, Σ 0 αcomplete sets (respectively, Π 0 α -complete sets) form a single Wadge degree, this implies also the following result. Notice that similar methods have next be used to get another surprising result: the Wadge hierarchy, hence also the Borel hierarchy, of infinitary rational relations accepted by 2-tape Büchi automata is equal to the Wadge hierarchy of the class r-BCL(1) ω or of the class Σ 1 1 , [START_REF] Finkel | On the accepting power of two-tape Büchi automata[END_REF][START_REF] Finkel | Special Issue on Intensional Programming and Semantics in honour of Bill Wadge on the occasion of his 60th cycle[END_REF].

Topological complexity of deterministic context-free ω-languages

We have seen in the previous section that all non-deterministic finite machines accept ω-languages of the same topological complexity, as soon as they can simulate a real time 1-counter automaton. This result is still true in the deterministic case if we consider only the Borel hierarchy. Recall that regular ω-languages accepted by Büchi automata are Π 0 2 -sets and ω-languages accepted by Muller automata are boolean combinations of Π 0 2 -sets hence ∆ 0 3 -sets. Engelfriet and Hoogeboom proved that this result holds also for all ω-languages accepted by deterministic X-automata, i.e. automata equipped with a storage type X, including the cases of k-counter automata, pushdown automata, Petri nets, Turing machines. In particular, ω-languages accepted by deterministic Büchi Turing machines are Π 0 2 -sets and ω-languages accepted by deterministic Muller Turing machines are ∆ 0 3sets.

It turned out that this is no longer true if we consider the much finer Wadge hierarchy to measure the complexity of ω-languages. The Wadge hierarchy is suitable to distinguish the accepting power of deterministic finite machines reading infinite words. Recall that the Wadge hierarchy of regular ω-languages, now called the Wagner hierarchy, has been effectively determined by Wagner; it has length ω ω [START_REF] Wagner | On ω-regular sets[END_REF][START_REF] Selivanov | Fine hierarchy of regular ω-languages[END_REF][START_REF] Selivanov | Fine hierarchy of regular ω-languages[END_REF].

Its extension to deterministic context-free ω-languages has been determined by Duparc, its length is ω (ω 2 ) [START_REF] Duparc | Computer science and the fine structure of Borel sets[END_REF][START_REF] Duparc | A hierarchy of deterministic context free ω-languages[END_REF]. To determine the Wadge hierarchy of the class DCF L ω , Duparc first defined operations on DMPDA which correspond to ordinal operations of sum, multiplication by ω, and multiplication by ω 1 , over Wadge degrees. In this way are constructed some DMPDA accepting ω-languages of every Wadge degree in the form :

d 0 W (A) = ω nj 1 .δ j + ω nj-1 1 .δ j-1 + . . . + ω n1
1 .δ 1 where j > 0 is an integer, n j > n j-1 > . . . > n 1 are integers ≥ 0, and δ j , δ j-1 , . . . , δ 1 are non null ordinals < ω ω .

On the other hand it is known that the Wadge degree α of a boolean combination of Π 0 2 -sets is smaller than the ordinal ω ω 1 thus it has a Cantor normal form :

α = ω nj 1 .δ j + ω nj-1 1 .δ j-1 + . . . + ω n1 1 .δ 1
where j > 0 is an integer, n j > n j-1 > . . . > n 1 are integers ≥ 0, and δ j , δ j-1 , . . . , δ 1 are non null ordinals < ω 1 , i.e. non null countable ordinals. In a second step it is proved in [START_REF] Duparc | A hierarchy of deterministic context free ω-languages[END_REF], using infinite multi-player games, that if such an ordinal α is the Wadge degree of a deterministic context-free ω-language, then all the ordinals δ j , δ j-1 , . . . , δ 1 appearing in its Cantor normal form are smaller than the ordinal < ω ω . Thus the Wadge hierarchy of the class DCF L ω is completely determined.

Theorem 29 (Duparc [24]). The Wadge degrees of deterministic context-free ω-languages are exactly the ordinals in the form :

α = ω nj 1 .δ j + ω nj-1 1 .δ j-1 + . . . + ω n1 1 .δ 1
where j > 0 is an integer, n j > n j-1 > . . . > n 1 are integers ≥ 0, and δ j , δ j-1 , . . . , δ 1 are non null ordinals < ω ω . The length of the Wadge hierarchy of the class DCF L ω is the ordinal

(ω ω ) ω = ω (ω 2 ) .
Notice that theWadge hierarchy of DCF L ω is not determined in an effective way in [START_REF] Duparc | A hierarchy of deterministic context free ω-languages[END_REF]. The question of the decidability of problems like: "given two DMPDA A and B, does L(A) ≤ W L(B) hold ?" or "given a DMPDA A can we compute d 0 W (L(A))?" naturally arises. Cohen and Gold proved that one can decide whether an effectively given ω-language in DCF L ω is an open or a closed set [START_REF] Cohen | Theory of ω-languages, parts one and two[END_REF]. Linna characterized the ω-languages accepted by DBPDA as the Π 0 2 -sets in DCF L ω and proved in [START_REF] Linna | A decidability result for deterministic ω-context-free languages[END_REF] that one can decide whether an effectively given ω-language accepted by a DMPDA is a Π 0 2 -set or a Σ 0 2 -set. Using a recent result of Walukiewicz on infinite games played on pushdown graphs, [START_REF] Walukiewicz | Pushdown processes: games and model checking[END_REF], these decidability results were extended in [START_REF] Finkel | Topological properties of omega context free languages[END_REF] where it was proved that one can decide whether a deterministic context-free ω-language accepted by a given DMPDA is in a given Borel class Σ 0 1 , Π 0 1 , Σ 0 2 , or Π 0 2 or even in the wadge class [L] given by any regular ω-language L.

An effective extension of the Wagner hierarchy to ω-languages accepted by Muller deterministic real time blind (i. e. without zero-test) 1-counter automata has been determined in [START_REF] Finkel | An effective extension of the Wagner hierarchy to blind counter automata[END_REF]. Recall that blind 1-counter automata form a subclass of 1-counter automata hence also of pushdown automata. A blind 1-counter Muller automaton is just a Muller pushdown automaton M = (K, X, Γ, δ, q 0 , Z 0 , F ) such that Γ = {Z 0 , I} where Z 0 is the bottom symbol and always remains at the bottom of the store. Moreover every transition which is enabled at zero level is also enabled at non zero level, i.e. if δ(q, a, Z 0 ) = (p, I n Z 0 ), for some p, q ∈ K, a ∈ X and n ≥ 0, then δ(q, a, I) = (p, I n+1 ). But the converse may not be true, i.e. some transition may be enabled at non zero level but not at zero level. Notice that blind 1-counter automata are sometimes called partially blind 1-counter automata as in [START_REF] Greibach | Remarks on blind and partially blind one way multicounter machines[END_REF]. The Wadge hierarchy of blind counter ω-languages, accepted by deterministic Muller real time blind 1-counter automata (MBCA), is studied in [START_REF] Finkel | An effective extension of the Wagner hierarchy to blind counter automata[END_REF] in a similar way as Wagner studied the Wadge hierarchy of regular ω-languages in [START_REF] Wagner | On ω-regular sets[END_REF]. Chains and superchains for MBCA are defined as Wagner did for Muller automata. The essential difference between the two hierarchies relies on the existence of superchains of transfinite length α < ω 2 for MBCA when in the case of Muller automata the superchains have only finite lengths. The hierarchy of ω-languages accepted by MBCA is effective and leads to effective winning strategies in Wadge games between two players in charge of ω-languages accepted by MBCA. Concerning the length of the Wadge hierarchy of MBCA the following result is proved : Theorem 30 (Finkel [30]).

(a) The length of the Wadge hierarchy of blind counter

ω-languages in ∆ 0 2 is ω 2 . (b)
The length of the Wadge hierarchy of blind counter ω-languages is the ordinal ω ω (hence it is equal to the length of the Wagner hierarchy).

Notice that the length of the Wadge hierarchy of blind counter ω-languages is equal to the length of the Wagner hierarchy although it is actually a strict extension of the Wagner hierarchy, as shown already in item (a) of the above theorem. The Wadge degrees of blind counter ω-languages are the ordinals in the form :

α = ω nj 1 .δ j + ω nj-1 1 .δ j-1 + . . . + ω n1 1 .δ 1
where j > 0 is an integer, n j > n j-1 > . . . > n 1 are integers ≥ 0, and δ j , δ j-1 , . . . , δ 1 are non null ordinals < ω 2 . Recall that in the case of Muller automata, the ordinals δ j , δ j-1 , . . . , δ 1 are non-negative integers, i.e. non null ordinals < ω.

Notice that Selivanov has recently determined the Wadge hierarchy of ω-languages accepted by deterministic Turing machines; its length is (ω CK 1 ) ω [START_REF] Selivanov | Wadge degrees of ω-languages of deterministic Turing machines[END_REF][START_REF] Selivanov | Wadge degrees of ω-languages of deterministic Turing machines[END_REF]. The ω-languages accepted by deterministic Muller Turing machines or equivalently which are boolean combinations of arithmetical Π 0 2 -sets have Wadge degrees in the form :

α = ω nj 1 .δ j + ω nj-1 1
.δ j-1 + . . . + ω n1 1 .δ 1 where j > 0 is an integer, n j > n j-1 > . . . > n 1 are integers ≥ 0, and δ j , δ j-1 , . . . , δ 1 are non null ordinals < ω CK 1 .

6 Topology and ambiguity in context-free ω-languages

The notions of ambiguity and of degrees of ambiguity are well known and important in the study of context-free languages. These notions have been extended to context-free ω-languages accepted by Büchi or Muller pushdown automata in [START_REF] Finkel | Ambiguity in omega context free languages[END_REF]. Notice that it is proved in [START_REF] Finkel | Ambiguity in omega context free languages[END_REF] that these notions are independent of the Büchi or Muller acceptance condition. So in the sequel we shall only consider the Büchi acceptance condition.

We now firstly introduce a slight modification in the definition of a run of a Büchi pushdown automaton, which will be used in this section.

Definition 31. Let A = (K, X, Γ, δ, q 0 , Z 0 , F ) be a Büchi pushdown automaton. Let σ = a 1 a 2 . . . a n . . . be an ω-word over X. A run of A on σ is an infinite sequence r = (q i , γ i , ε i ) i≥1 where (q i , γ i ) i≥1 is an infinite sequence of configurations of A and, for all i ≥ 1, ε i ∈ {0, 1} and:

1. (q 1 , γ 1 ) = (q 0 , Z 0 ) 2. for each i ≥ 1, there exists b i ∈ X ∪ {λ} satisfying b i : (q i , γ i ) → A (q i+1 , γ i+1 ) and ( ε i = 0 iff b i = λ ) and such that a 1 a 2 . . . a n . . . = b 1 b 2 . . . b n . . .

As before the ω-language accepted by A is

L(A) = {σ ∈ X ω | there exists a run r of A on σ such that In(r) ∩ F = ∅}
Notice that the numbers ε i ∈ {0, 1} are introduced in the above definition in order to distinguish runs of a BPDA which go through the same infinite sequence of configurations but for which λ-transitions do not occur at the same steps of the computations.

As usual the cardinal of ω is denoted ℵ 0 and the cardinal of the continuum is denoted 2 ℵ0 . The latter is also the cardinal of the set of real numbers or of the set X ω for every finite alphabet X having at least two letters.

We are now ready to define degrees of ambiguity for BPDA and for context-free ωlanguages.

Definition 32. Let A be a BPDA reading infinite words over the alphabet X. For x ∈ X ω let α A (x) be the cardinal of the set of accepting runs of A on x.

Lemma 33 ([34]). Let A be a BPDA reading infinite words over the alphabet X. Then for all x ∈ X ω it holds that α A (x) ∈ N ∪ {ℵ 0 , 2 ℵ0 }.

Definition 34. Let A be a BPDA reading infinite words over the alphabet X.

(a) If sup{α A (x) | x ∈ X ω } ∈ N ∪ {2 ℵ0 }, then α A = sup{α A (x) | x ∈ X ω }. (b) If sup{α A (x) | x ∈ X ω } = ℵ 0 and there is no word x ∈ X ω such that α A (x) = ℵ 0 , then α A = ℵ - 0 . (ℵ -
0 does not represent a cardinal but is a new symbol that is introduced here to conveniently speak of this situation). (c) If sup{α A (x) | x ∈ X ω } = ℵ 0 and there exists (at least) one word x ∈ X ω such that α A (x) = ℵ 0 , then α A = ℵ 0

Notice that for a BPDA A, α A = 0 iff A does not accept any ω-word.

We shall consider below that N ∪ {ℵ - 0 , ℵ 0 , 2 ℵ0 } is linearly ordered by the relation <, which is defined by : ∀k

∈ N, k < k + 1 < ℵ - 0 < ℵ 0 < 2 ℵ0 . Definition 35. For k ∈ N ∪ {ℵ - 0 , ℵ 0 , 2 ℵ0 } let CF L ω (α ≤ k) = {L(A) | A is a BP DA with α A ≤ k} CF L ω (α < k) = {L(A) | A is a BP DA with α A < k} N A-CF L ω = CF L ω (α ≤ 1)
is the class of non ambiguous context-free ω-languages. For every integer k such that k ≥ 2, or k ∈ {ℵ - 0 , ℵ 0 , 2 ℵ0 },

A(k) -CF L ω = CF L ω (α ≤ k) -CF L ω (α < k) If L ∈ A(k) -CF L ω with k ∈ N, k ≥ 2, or k ∈ {ℵ - 0 , ℵ 0 , 2 ℵ0
}, then L is said to be inherently ambiguous of degree k.

Notice that one can define in a similar way the degree of ambiguity of a finitary contextfree language. If M is a pushdown automaton accepting finite words by final states (or by final states and topmost stack letter) then α M ∈ N or α M = ℵ - 0 or α M = ℵ 0 . However every context-free language is accepted by a pushdown automaton M with α M ≤ ℵ - 0 , [START_REF] Autebert | Context free languages and pushdown automata[END_REF]. We denote the class of non ambiguous context-free languages by N A-CF L and the class of inherently ambiguous context-free languages by A-CF L. Then one can state the following result.

Theorem 36 ([34]).

N A-CF L ω ω-KC(N A-CF L) A-CF L ω ω-KC(A-CF L)
We now come to the study of links between topology and ambiguity in context-free ω-languages [START_REF] Finkel | Ambiguity in omega context free languages[END_REF][START_REF] Finkel | Topology and ambiguity in omega context free languages[END_REF]. Using a Theorem of Lusin and Novikov, and another theorem of descriptive set theory, see [50, page 123], Simonnet proved the following strong result which shows that non-Borel context-free ω-languages have a maximum degree of ambiguity.

Theorem 37 (Simonnet [45]). Let L(A) be a context-free ω-language accepted by a BPDA A such that L(A) is an analytic but non Borel set. The set of ω-words, which have 2 ℵ0 accepting runs by A, has cardinality 2 ℵ0 .

On the other hand, it turned out that, informally speaking, the operation A → A ∼ conserves globally the degrees of ambiguity of infinitary context-free languages (which are unions of a finitary context-free language and of a context-free ω-language). Then, starting from known examples of finitary context-free languages of a given degree of ambiguity, are constructed in [START_REF] Finkel | Ambiguity in omega context free languages[END_REF] some context-free ω-languages of any finite Borel rank and which are non-ambiguous or of any finite degree of ambiguity or of degree ℵ - 0 .

Theorem 38.

1. For each non negative integer n ≥ 1, there exist Σ 0 n -complete non ambiguous context-free ω-languages A n and Π 0 n -complete non ambiguous context-free ωlanguages B n . 2. Let k be an integer ≥ 2 or k = ℵ - 0 . Then for each integer n ≥ 1, there exist Σ 0 n -complete context-free ω-languages E n (k) and Π 0 n -complete context-free ωlanguages F n (k) which are in A(k) -CF L ω , i.e. which are inherently ambiguous of degree k.

Notice that the ω-languages A n and B n are simply those which were constructed in the proof of Theorem 24. On the other hand it is easy to see that the BPDA accepting the context-free ω-language which is Borel of infinite rank, constructed in [START_REF] Finkel | On omega context free languages which are Borel sets of infinite rank[END_REF] using an iteration of the operation A → A ∼ , has an infinite degree of ambiguity. And 1-counter Büchi automata accepting context-free ω-languages of any Borel rank of an effective analytic set, constructed via simulation of multicounter automata, may also have a great degree of ambiguity. So this left open some questions we shall detail in the last section.

We indicate now a new result which follows easily from the proof of Theorem 27 sketched in Section 4 above, see [START_REF] Finkel | Borel ranks and Wadge degrees of omega context free languages[END_REF]. Consider an ω-language L accepted by a deterministic Muller Turing machine or equivalently by a deterministic 2-counter Muller automaton. We get first an ω-language θ S (L) ⊆ X ω which has the same topological complexity (except for finite Wadge degrees), and which is accepted by a deterministic real time 8-counter Muller automaton A. Then one can construct from A a 1-counter Muller automaton B, reading words over the alphabet X ∪ {A, B, 0}, such that h(L(A)) ∪ h(X ω ) -= L(B) ∪ h(X ω ) -, where h : X ω → (X ∪ {A, B, 0}) ω is the mapping defined in Section 4. Notice that the 1counter Muller automaton B which is constructed is now also deterministic. On the other hand it is easy to see, from the decomposition given in [41, Proof of Lemma 5.3], that the ω-language h(X ω ) -is accepted by a 1-counter Büchi automaton which has degree of ambiguity 2 and the ω-language L(B) is in N A -CF L ω = CF L ω (α ≤ 1) because it is accepted by a deterministic 1-counter Muller automaton. Then we can easily infer, using [START_REF] Finkel | Ambiguity in omega context free languages[END_REF]Theorem 5.16 (c)] that the ω-language h(L(A)) ∪ h(X ω ) -= L(B) ∪ h(X ω ) -is in CF L ω (α ≤ 3). And this ω-language has the same complexity as L(A) Thus we can state the following result.

Theorem 39. For each ω-language L accepted by a deterministic Muller Turing machine there is an ω-language L ′ ∈ CF L ω (α ≤ 3), accepted by a 1-counter Muller automaton D with α D ≤ 3, such that L ≡ W L ′ .

ω-Powers of context-free languages

The ω-powers of finitary languages are ω-languages in the form V ω , where V is a finitary language over a finite alphabet X. They appear very naturally in the characterization of the class REG ω of regular ω-languages (respectively, of the class CF L ω of context-free ω-languages) as the ω-Kleene closure of the family REG of regular finitary languages (respectively, of the family CF of context-free finitary languages) . The question of the topological complexity of ω-powers naturally arises and was raised by Niwinski [START_REF] Niwinski | A problem on ω-powers[END_REF], Simonnet [START_REF] Simonnet | Automates et théorie descriptive[END_REF], and Staiger [START_REF] Staiger | On ω-power languages[END_REF].

An ω-power of a finitary language is always an analytic set because it is either the continuous image of a compact set {0, 1, . . . , n} ω for n ≥ 0 or of the Baire space ω ω . The first example of finitary language L such that L ω is analytic but not Borel, and even Σ 1 1 -complete, was obtained in [START_REF] Finkel | Borel hierarchy and omega context free languages[END_REF]. Amazingly the language L was very simple and even accepted by a 1-counter automaton. It was obtained via a coding of infinite labelled binary trees.

We now give a simple construction of this language L using the notion of substitution which we now recall. A substitution is defined by a mapping f : X → P(Γ ⋆ ), where X = {a 1 , . . . , a n } and Γ are two finite alphabets, f : a i → L i where for all integers i ∈ [1; n], f (a i ) = L i is a finitary language over the alphabet Γ . Now this mapping is extended in the usual manner to finite words: f (a i1 . . . a in ) = L i1 . . . L in , and to finitary languages L ⊆ X ⋆ : f (L) = ∪ x∈L f (x). If for each integer i ∈ [1; n] the language L i does not contain the empty word, then the mapping f may be extended to ω-words: f (x(1) . . . x(n) . .

.) = {u 1 . . . u n . . . | ∀i ≥ 1 u i ∈ f (x(i))} and to ω-languages L ⊆ X ω by setting f (L) = ∪ x∈L f (x).
Let now X = {0, 1} and d be a new letter not in X and

D = {u.d.v | u, v ∈ X ⋆ and (|v| = 2|u|) or (|v| = 2|u| + 1) } D ⊆ (X ∪ {d}) ⋆ is
a context-free language accepted by a 1-counter automaton. Let g : X → P((X ∪ {d}) ⋆ ) be the substitution defined by g(a) = a.D. As W = 0 ⋆ 1 is regular, L = g(W ) is a context-free language and it is accepted by a 1-counter automaton. Moreover one can prove that (g(W )) ω is Σ 1 1 -complete, hence a non Borel set. This is done by reducing to this ω-language a well-known example of Σ 1 1 -complete set : the set of infinite binary trees labelled in the alphabet {0, 1} which have an infinite branch in the Π 0 2 -complete set (0 ⋆ .1) ω , see [START_REF] Finkel | Borel hierarchy and omega context free languages[END_REF] for more details. Remark 40. The ω-language (g(W )) ω is context-free. By Theorem 37 every BPDA accepting (g(W )) ω has the maximum ambiguity and (g(W )) ω ∈ A(2 ℵ0 ) -CF L ω . On the other hand we can prove that g(W ) is a non ambiguous context-free language. This is used in [START_REF] Finkel | Topology and ambiguity in omega context free languages[END_REF] to prove that neither unambiguity nor ambiguity of context-free languages are preserved under the operation V → V ω .

Concerning Borel ω-powers, it has been proved in [START_REF] Finkel | Topological properties of omega context free languages[END_REF] that for each integer n ≥ 1, there exist some ω-powers of context-free languages which are Π 0 n -complete Borel sets. These results were obtained by the use of a new operation V → V ≈ over ω-languages, which is a slight modification of the operation V → V ∼ . The new operation V → V ≈ preserves ω-powers and context-freeness. More precisely if V = W ω for some contextfree language W , then V ≈ = T ω for some context-free language T which is obtained from W by application of a given context-free substitution. And it follows easily from [START_REF] Duparc | Wadge hierarchy and Veblen hierarchy: Part 1: Borel sets of finite rank[END_REF] that if V ⊆ X ω is a Π 0 n -complete set, for some integer n ≥ 2, then V ≈ is a Π 0 n+1 -complete set. Then, starting from the Π 0 2 -complete set (0 ⋆ .1) ω , we get some Π 0 n -complete ω-powers of context-free languages for each integer n ≥ 3.

An iteration of the operation V → V ≈ was used in [START_REF] Finkel | An omega-power of a finitary language which is a Borel set of infinite rank[END_REF] to prove that there exists a finitary language V such that V ω is a Borel set of infinite rank. The language V was a simple recursive language but it was not context-free. Later, with a modification of the construction, using a coding of an infinity of erasers previously defined in [START_REF] Finkel | On omega context free languages which are Borel sets of infinite rank[END_REF], Finkel and Duparc got a context-free language V such that V ω is a Borel set above the class ∆ 0 ω , [START_REF] Duparc | An ω-power of a context free language which is Borel above ∆ 0 ω[END_REF].

The question of the Borel hierarchy of ω-powers of finitary languages has been solved very recently by Finkel and Lecomte in [START_REF] Finkel | There exist some ω-powers of any Borel rank[END_REF], where a very surprising result is proved, showing that actually ω-powers exhibit a great topological complexity. For every nonnull countable ordinal α there exist some Σ 0 α -complete ω-powers and also some Π 0 αcomplete ω-powers. But the ω-powers constructed in [START_REF] Finkel | There exist some ω-powers of any Borel rank[END_REF] are not ω-powers of contextfree languages, except for the case of a Σ 0 2 -complete set. Notice also that an example of a regular language L such that L ω is Σ 0 1 -complete was given by Simonnet in [START_REF] Simonnet | Automates et théorie descriptive[END_REF], see also [START_REF] Lecomte | Omega-powers and descriptive set theory[END_REF] .

Perspectives and open questions

We give below a list of some open questions which arise naturally. The problems listed here seem important for a better comprehension of context-free ω-languages but the list is not exhaustive.

Effective results

In the non-deterministic case, the Borel and Wadge hierarchies of context-free ω-langua ges are not effective, [START_REF] Finkel | Topological properties of omega context free languages[END_REF][START_REF] Finkel | Borel hierarchy and omega context free languages[END_REF][START_REF] Finkel | Wadge hierarchy of omega context free languages[END_REF]. This is not surprising since most decision problems on context-free languages are undecidable. On the other hand we can expect some decidability results in the case of deterministic context-free ω-languages. We have already cited some of them : we can decide whether a deterministic context-free ω-language is in a given Borel class or even in the Wadge class [L] of a given regular ω-language L. The most challenging question in this area would be to find an effecive procedure to determine the Wadge degree of an ω-language in the class DCF L ω . Recall that the Wadge hierarchy of the class DCF L ω is determined in a non-effective way in [START_REF] Duparc | A hierarchy of deterministic context free ω-languages[END_REF]. On the other hand the Wadge hierarchy of the class of blind counter ωlanguages is determined in an effective way, using notions of chains and superchains, in [START_REF] Finkel | An effective extension of the Wagner hierarchy to blind counter automata[END_REF]. There is a gap between the two hierarchies because (blind) 1-counter automata are much less expressive than pushdown automata. One could try to extend the methods of [START_REF] Finkel | An effective extension of the Wagner hierarchy to blind counter automata[END_REF] to the study of deterministic pushdown automata. Another question concerns the complexity of decidable problems. A first question would be the following one. Could we extend the results of Wilke and Yoo to the class of blind counter ω-languages, i.e. is the Wadge degree of a blind counter ω-language computable in polynomial time ? Otherwise what is the complexity of this problem ? Of course the question may be further asked for classes of ω-languages which are located between the classes of blind counter ω-languages and of deterministic context-free ω-languages. Another interesting question would be to determine the Wadge hierarchy of ω-languages accepted by deterministic higher order pushdown automata (even firstly in a non effective way), [START_REF] Engelfriet | Iterated pushdown automata and complexity classes[END_REF][START_REF] Cachat | The complexity of games on higher order pushdown automata[END_REF].

Topology and ambiguity

Simonnet's Theorem 37 states that non-Borel context-free ω-languages have a maximum degree of ambiguity, i.e. are in the class A(2 ℵ0 ) -CF L ω . On the other hand, there exist some non-ambiguous context-free ω-languages of every finite Borel rank. The question naturally arises whether there exist some non-ambiguous context-free ωlanguages which are Wadge equivalent to any given Borel context-free ω-language (or equivalently to any Borel Σ 1 1 -set, by Theorem 28). This may be connected to a result of Arnold who proved in [START_REF] Arnold | Topological characterizations of infinite behaviours of transition systems[END_REF] that every Borel subset of X ω , for a finite alphabet X, is accepted by a non-ambiguous finitely branching transition system with Büchi acceptance condition. By Theorem 38, if k is an integer ≥ 2 or k = ℵ - 0 , then for each integer n ≥ 1, there exist Σ 0 n -complete context-free ω-languages E n (k) and Π 0 n -complete context-free ω-languages F n (k) which are in A(k) -CF L ω , i.e. which are inherently ambiguous of degree k. More generally the question arises : determine the Borel ranks and the Wadge degrees of context-free ω-languages in classes CF L ω (α ≤ k) or A(k) -CF L ω where k ∈ N ∪ {ℵ - 0 , ℵ 0 , 2 ℵ0 } ( k ≥ 2 in the case of A(k) -CF L ω ). A first result in this direction is Theorem 39 stated in Section 6.

ω-Powers

The results of [START_REF] Finkel | Topological properties of omega context free languages[END_REF][START_REF] Finkel | Borel hierarchy and omega context free languages[END_REF][START_REF] Finkel | An omega-power of a finitary language which is a Borel set of infinite rank[END_REF][START_REF] Finkel | There exist some ω-powers of any Borel rank[END_REF] show that ω-powers of finitary languages have actually a great topological complexity. Concerning ω-powers of context-free languages we do not know yet what are all their infinite Borel ranks. However the results of [START_REF] Finkel | Borel ranks and Wadge degrees of omega context free languages[END_REF] suggest that ω-powers of context-free languages or even of languages accepted by 1-counter automata exhibit also a great topological complexity. Indeed Theorem 28 states that there are ω-languages accepted by Büchi 1-counter automata of every Borel rank (and even of every Wadge degree) of an effective analytic set. On the other hand each ω-language accepted by a Büchi 1-counter automaton can be written as a finite union L = 1≤i≤n U i .V ω i , where for each integer i, U i and V i are finitary languages accepted by 1-counter automata. Then we can conjecture that there exist some ω-powers of languages accepted by 1-counter automata which have Borel ranks up to the ordinal γ 1 2 , although these languages are located at the very low level in the complexity hierarchy of finitary languages. Recall that a finitary language L is a code (respectively, an ω-code) if every word of L + (respectively, every ω-word of L ω ) has a unique decomposition in words of L, [START_REF] Berstel | Theory of codes[END_REF]. It is proved in [START_REF] Finkel | Topology and ambiguity in omega context free languages[END_REF] that if V is a context-free language such that V ω is a non Borel set then there are 2 ℵ0 ω-words of V ω which have 2 ℵ0 decompositions in words of V ; in particular, V is really not an ω-code although it is proved in [START_REF] Finkel | Topology and ambiguity in omega context free languages[END_REF] that V may be a code (see the example V=g(W) given in Section 7). The following question about Borel ω-powers now arises : are there some context-free codes (respectively, ω-codes) V such that V ω is Σ 0 α -complete or Π 0 α -complete for a given countable ordinal α < γ 1 2 ?

  for example if u = bb(և a) ω the finite word u[n] և is alternatively equal to b or to ba: more precisely u[2n + 1] և = b and u[2n + 2] և = ba for every integer n ≥ 1 (it holds also that u[1] և = b and u[2] և = bb). Thus Definition 20 implies that lim n∈ω (u[n]) և = b so u և = b.

1 and C 1 1 ) 1 )

 111 are in the form E ∪ F where E is a finitary contextfree language and F is a context-free ω-language. Then the ω-languages (O ∼.n 1 ) d and (C ∼.n d are context-free. Hence the class CF L ω exhausts the finite ranks of the Borel hierarchy: we obtain the context-free ω-languages A n = (O ∼.(n-1) d and B n = (C ∼.(n-1) 1) d , for n ≥ 3.

Theorem 28 . 2 =

 282 Let C be a class of ω-languages such that: r-BCL(1) ω ⊆ C⊆ Σ 1 1 . (a) The Borel hierarchy of the class C is equal to the Borel hierarchy of the class Σ 1 1 . (b) γ 1 Sup {α | ∃L ∈ C such that L is a Borel set of rank α}. (c) For every non null ordinal α < ω CK 1 , there exists some Σ 0 α -complete and some Π 0 α -complete ω-languages in the class C.