Olivier Finkel
email: finkel@logique.jussieu.fr.

Borel ranks and Wadge degrees of context free ω-languages

Keywords: 1-counter Büchi automata, context free ω-languages, Cantor topology, topological properties, Borel hierarchy, Borel ranks, Wadge hierarchy, Wadge degrees

We show that the Borel hierarchy of the class of context free ω-languages, or even of the class of ω-languages accepted by Büchi 1-counter automata, is the same as the Borel hierarchy of the class of ω-languages accepted by Turing machines with a Büchi acceptance condition. In particular, for each recursive non null ordinal α, there exist some Σ 0 α -complete and some Π 0 α -complete ω-languages accepted by Büchi 1counter automata. And the supremum of the set of Borel ranks of context free ω-languages is an ordinal γ 1 2 which is strictly greater than the first non recursive ordinal ω CK 1 . We then extend this result, proving that the Wadge hierarchy of context free ω-languages, or even of ω-languages accepted by Büchi 1-counter automata, is the same as the Wadge hierarchy of ω-languages accepted by Turing machines with a Büchi or a Muller acceptance condition.

Introduction

Languages of infinite words accepted by finite automata were first studied by Büchi to prove the decidability of the monadic second order theory of one successor over the integers. The theory of the so called regular ω-languages is now well established and has found many applications for specification and verification of non-terminating systems; see [Tho90,Sta97,PP04] for many results and references. More powerful machines, like pushdown automata, Turing machines, have also been considered for the reading of infinite words, see Staiger's survey [Sta97] and the fundamental study [EH93] of Engelfriet and Hoogeboom on X-automata, i.e. finite automata equipped with a storage type X. A way to study the complexity of ω-languages is to study their topological complexity, and particularly to locate them with regard to the Borel and the projective hierarchies. On one side all ω-languages accepted by deterministic X-automata with a Muller acceptance condition are Boolean combinations of Π 0 2 -sets hence ∆ 0 3 -sets, [Sta97,EH93]. This implies, from Mc Naughton's Theorem, that all regular ω-languages, which are accepted by deterministic Muller automata, are also ∆ 0 3 -sets. On the other side, for non deterministic finite machines, the question, posed by Lescow and Thomas in [LT94], naturally arises: what is the topological complexity of ω-languages accepted by automata equipped with a given storage type X? It is well known that every ω-language accepted by a Turing machine (hence also by a X-automaton) with a Muller acceptance condition is an analytic set. In previous papers, we proved that there are context free ω-languages, accepted by Büchi or Muller pushdown automata, of every finite Borel rank, of infinite Borel rank, or even being analytic but non Borel sets, [DFR01,Fin01c,Fin03a,Fin03b]. In this paper we show that the Borel hierarchy of ω-languages accepted by X-automata, for every storage type X such that 1-counter automata can be simulated by X-automata, is the same as the Borel hierarchy of ω-languages accepted by Turing machines with a Büchi acceptance condition. In particular, for each recursive non null ordinal α, there exist some Σ 0 α -complete and some Π 0 α -complete ω-languages accepted by Büchi 1-counter automata, hence also in the class CFL ω of context free ω-languages. We have to indicate here a mistake in the conference paper [Fin05]. We wrote in that paper that it is well known that if L ⊆ Σ ω is a (lightface) Σ 1 1 set, i.e. accepted by a Turing machine with a Büchi acceptance condition, and is a Borel set of rank α, then α is smaller than the Church Kleene ordinal ω CK 1 , which is the first non recursive ordinal. This fact, which is true if we replace the (lightface) class Σ 1 1 by the (lightface) class ∆ 1 1 , is actually not true. Kechris, Marker and Sami proved in [KMS89] that the supremum of the set of Borel ranks of (lightface) Π 1 1 , so also of (lightface) Σ 1 1 , sets is the ordinal γ 1 2 . This ordinal is precisely defined in [KMS89] and it is strictly greater than the ordinal ω CK 1 . The proofs we give in this paper show that the ordinal γ 1 2 is also the supremum of the set of Borel ranks of ω-languages accepted by Büchi 1-counter automata, or of context free ω-languages. By considering the Wadge hierarchy which is a great refinement of the Borel hierarchy, [Wad83,Dup01], we show the following strengthening of the preceding result. The Wadge hierarchy of the class r-BCL(1) ω of ω-languages accepted by real time 1-counter Büchi automata, hence also of the class CFL ω , is the Wadge hierarchy of the class of ω-languages accepted by Turing machines with a Büchi acceptance condition. We think that the surprising result obtained in this paper is of interest for both logicians working on hierarchies arising in recursion theory or in descriptive set theory, and also for computer scientists working on questions connected with non-terminating systems, like the construction of effective strategies in infinite games, [Wal00,Tho02,Cac02,Ser04b]. The paper is organized as follows. In Section 2 we define multicounter automata which will be a useful tool in the sequel. Recall on Borel hierarchy is given in Section 3. In Section 4 is studied the Borel hierarchy of ω-languages accepted by real time 8-counter automata. The Borel hierarchy of the class r-BCL(1) ω is studied in Section 5. Results about the Wadge hierarchy of the class r-BCL(1) ω are given in Section 6.

We assume the reader to be familiar with the theory of formal (ω)-languages [Tho90,Sta97]. We shall use usual notations of formal language theory. When Σ is a finite alphabet, a non-empty finite word over Σ is any sequence x = a 1 . . . a k , where a i ∈ Σ for i = 1, . . . , k , and k is an integer ≥ 1. The length of x is k, denoted by |x|. The empty word has no letter 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] = λ. Σ ⋆ is the set of finite words (including the empty word) over Σ. The first infinite ordinal is ω. An ω-word over Σ is an ω -sequence a 1 . . . a n . . ., where for all integers i ≥ 1, a i ∈ Σ. When σ is an ω-word over Σ, we write σ = σ(1)σ(2) . . . σ(n) . . ., where for all i, σ(i) ∈ Σ, and σ[n] = σ(1)σ(2) . . . σ(n) for all n ≥ 1 and σ[0] = λ. 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 Σ is denoted by Σ ω . An ω-language over an alphabet Σ is a subset of Σ ω . The complement (in Σ ω ) of an ω-language V ⊆ Σ ω is Σ ω -V , denoted V -. Definition 1. Let k be an integer ≥ 1. A k-counter machine (k-CM) is a 4-tuple M=(K, Σ, ∆, q 0 ), where K is a finite set of states, Σ is a finite input alphabet, q 0 ∈ K is the initial state, and

∆ ⊆ K × (Σ ∪ {λ}) × {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 × Σ × {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 ∈ Σ ∪ {λ}, 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 )
→ ⋆ M is the transitive and reflexive closure of → M . (The subscript M will be omitted whenever the meaning remains clear). 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 may not be equal to -1).

Let σ = a 1 a 2 . . . a n be a finite word over Σ. An sequence of configurations

r = (q i , c i 1 , . . . c i k ) 1≤i≤p , for p ≥ n + 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 ∈ Σ ∪ {λ} such that b i : (q i , c i 1 , . . . c i k ) → M (q i+1 , c i+1 1 , . . . c i+1 k ) (3) a 1 .a 2 .a 3 . . . a n = b 1 .b 2 .b 3 . . . b p Let σ = a 1 a 2 . . . a n . . . be an ω-word over Σ. 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 ∈ Σ ∪ {λ} 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 2. A Büchi k-counter automaton is a 5-tuple M=(K, Σ, ∆, q 0 , F ), where M ′ =(K, Σ, ∆, q 0 ) is a k-counter machine and F ⊆ K is the set of accepting states. The ω-language accepted by M is

L(M)= {σ ∈ Σ ω | there exists a run r of M on σ such that In(r) ∩ F = ∅} Definition 3. A Muller k-counter automaton is a 5-tuple M=(K, Σ, ∆, q 0 , F ), where M ′ =(K, Σ, ∆, q 0 ) is a k-counter machine and F ⊆ 2 K is the set of accept- ing sets of states. The ω-language accepted by M is L(M)={σ ∈ Σ ω | there exists a run r of M on σ such that ∃F ∈ F In(r) = F }
The class of Büchi k-counter automata will be denoted BC(k).

The class of real time Büchi k-counter automata will be denoted r-BC(k).

The class of ω-languages accepted by Büchi k-counter automata will be denoted BCL(k) ω .

The class of ω-languages accepted by real time Büchi k-counter automata will be denoted r-BCL(k) ω .

It is well known 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 [EH93].

Notice that it cannot be shown without using the non determinism of automata and this result is no longer true in the deterministic case.

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 Z 0 .A N .

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 [Fin01d], and it is a strict subclass of the class CFL ω of context free ω-languages accepted by Büchi pushdown automata.

We assume the reader to be familiar with basic notions of topology which may be found in [Mos80,LT94,Kec95,Sta97,PP04]. There is a natural metric on the set Σ ω of infinite words over a finite alphabet Σ which is called the prefix metric and defined as follows. For u, v ∈ Σ ω and u = v let δ(u, v) = 2 -l pref (u,v) where l pref(u,v) is the first integer n such that the (n + 1) st letter of u is different from the (n+1) st letter of v. This metric induces on Σ ω the usual Cantor topology for which open subsets of Σ ω are in the form W.Σ ω , where

W ⊆ Σ ⋆ . A set L ⊆ Σ ω is a closed set iff its complement Σ ω -L is an open set.
Define now the Borel Hierarchy of subsets of Σ ω :

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

Σ 0 α is the class of countable unions of subsets of Σ ω in γ<α Π 0 γ . Π 0 α is the class of countable intersections of subsets of Σ ω in γ<α Σ 0 γ . For a countable ordinal α, a subset of Σ ω is a Borel set of rank α iff it is in Σ 0 α ∪ Π 0 α but not in γ<α (Σ 0 γ ∪ Π 0 γ ).
There are also some subsets of Σ ω which are not Borel. In particular the class of Borel subsets of Σ ω is strictly included into the class Σ 1 1 of analytic sets which are obtained by projection of Borel sets, see for example [Sta97,LT94,PP04,Kec95] for more details. We now define completeness with regard to reduction by continuous functions. For a countable ordinal α ≥ 1, a set F ⊆ Σ ω is said to be a Σ 0 α (respectively, Π 0 α , Σ 1 1 )-complete set iff for any set E ⊆ Y ω (with Y a finite alphabet): As indicated in the introduction, we made a mistake in the conference paper [Fin05]. We wrote there that it is well known that if L ⊆ Σ ω is a (lightface) Σ 1 1 set, and is a Borel set of rank α, then α is smaller than ω CK 1 . This fact, which is true if we replace the (lightface) class Σ 1 1 by the (lightface) class ∆ 1 1 , is actually not true. Kechris, Marker and Sami proved in [KMS89] that the supremum of the set of Borel ranks of (lightface) Π 1 1 , so also of (lightface) Σ 1 1 , sets is the ordinal γ 1 2 . This ordinal is precisely defined in [KMS89]. Kechris, Marker and Sami proved that the ordinal γ 1 2 is strictly greater than the ordinal δ 1 2 which is the first non ∆ 1 2 ordinal. Thus in particular it holds that ω CK 1 < γ 1 2 . The exact value of the ordinal γ 1 2 may depend on axioms of set theory [KMS89]. It is consistent with the axiomatic system ZFC that γ 1 2 is equal to the ordinal δ 1 3 which is the first non ∆ 1 3 ordinal (because γ 1 2 = δ 1 3 in ZFC + (V=L)). On the other hand the axiom of Π 1 1 -determinacy implies that γ 1 2 < δ 1 3 . For more details, the reader is referred to [KMS89] and to a textbook of set theory like [Jec02].

E ∈ Σ 0 α (respectively, E ∈ Π 0 α , E ∈ Σ 1 1 ) iff there exists a continuous function f : Y ω → Σ ω such that E = f -1 (F ). Σ 0 n (respectively Π 0 n )-complete
Notice however that it seems still unknown whether every non null ordinal γ < γ 1 2 is the Borel rank of a (lightface) Π 1 1 (or Σ 1 1 ) set. On the other hand it is known that every ordinal γ < ω CK 1 is the Borel rank of a (lightface) ∆ 1 1 set. Moreover, for every non null ordinal α < ω CK 1 , there exist some Σ 0 α -complete and some Π 0 α -complete sets in the class ∆ 1 1 . Louveau gives the following argument: the natural universal set for the class Σ 0 α (respectively, Π 0 α ), where

α < ω CK 1 , is a Σ 0 α -complete (respectively, Π 0 α -complete) set and it is in the class ∆ 1 1 , [Lou05]
. The definition and the construction of a universal set for a given Borel class may be found in [Mos80].

4 Borel hierarchy of ω-languages in r-BCL(8) ω It is well known that every Turing machine can be simulated by a (non real time) 2-counter automaton, see [HU79]. Thus the Borel hierarchy of the class BCL(2) ω is also the Borel hierarchy of the class of ω-languages accepted by Büchi Turing machines. We shall prove the following proposition.

Proposition 5. The Borel hierarchy of the class r-BCL(8) ω is equal to the Borel hierarchy of the class BCL(2) ω .

We first sketch the proof of this result. We are going to find, from an ω-language L ⊆ Σ ω in BCL(2) ω , another ω-language θ S (L) which will be of the same Borel 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 we shall see that a 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 we 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 (two counters are used to check that an ω-word is really obtained with the good padding which is made in a regular way). The padding is obtained via the function θ S which we define now.

Let Σ be an alphabet having at least two letters, E be a new letter not in Σ, S be an integer ≥ 1, and θ S : Σ ω → (Σ ∪ {E}) ω be the function defined, for all x ∈ Σ ω , by: θ 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 . . . We now state the two following lemmas. Lemma 6. Let Σ be an alphabet having at least two letters and let L ⊆ Σ ω be a subset of Σ ω which is Σ 0 α -complete (respectively, Π 0 α -complete, Σ 0 α of rank α, Π 0 α of rank α) for some ordinal α ≥ 2. Then the ω-language θ S (L) is a subset of (Σ ∪ {E}) ω which is Σ 0 α -complete (respectively, Π 0 α -complete, Σ 0 α of rank α, Π 0 α of rank α).

Proof. Let Σ be an alphabet having at least two letters. It is easy to see that the function θ S is continuous because if two ω-words x and y of Σ ω have a common initial segment of length n then the two ω-words θ S (x) and θ S (y) have a common initial segment of length greater than n.

Let ϕ : (Σ ∪{E}) ω → (Σ ∪{E}) ω be the mapping defined, for all y ∈ (Σ ∪{E}) ω , by: ϕ(y) = y(1).y(S + 2).y(S + S 2 + 3) . . . y(S + S 2 + . . . + S n + (n + 1)) . . . It is easy to see that the function ϕ is also continuous and that, for any

L ⊆ Σ ω , θ S (L) = ϕ -1 (L) ∩ θ S (Σ ω ). Let now L ⊆ Σ ω be a Σ 0 α (respectively, Π 0 α ) subset of Σ ω , hence also of (Σ ∪ {E}) ω , for some ordinal α ≥ 2. Then ϕ -1 (L) is a Σ 0 α (respectively, Π 0 α ) subset of (Σ ∪ {E}) ω because the class Σ 0 α (respectively, Π 0 α ) is closed under inverse images by continuous functions. On the other hand θ S (Σ ω ) is a closed set thus θ S (L) = ϕ -1 (L) ∩ θ S (Σ ω ) is a Σ 0 α (respectively, Π 0 α ) subset of (Σ ∪ {E}) ω because the class Σ 0 α (respectively, Π 0 α ) is closed under finite intersection. Moreover it holds that L = θ -1 S (θ S (L)). Thus if L is assumed to be Σ 0 α -complete (respectively, Π 0 α -complete) then θ S (L) is a Σ 0 α -complete (respectively, Π 0 α - complete ) subset of (Σ ∪ {E}) ω because it is a Σ 0 α (respectively, Π 0 α ) set, the function θ S is continuous, and L is Σ 0 α -complete (respectively, Π 0 α -complete). Assume now that L is a Σ 0 α -set of rank α, (respectively, Π 0 α -set of rank α).
We have already seen that θ S (L) is a Σ 0 α (respectively, Π 0 α ) subset of (Σ∪{E}) ω . The Borel rank of θ S (L) cannot be smaller than α because otherwise L = θ -1 S (θ S (L)) would be also of Borel rank smaller than α.

Lemma 7. Let Σ be an alphabet having at least two letters and let L ⊆ Σ ω be an ω-language in the class BCL(2) ω . Then there exists an integer S ≥ 1 such that θ S (L) is in the class r-BCL(8) ω .

Proof. Let Σ be an alphabet having at least two letters and let L ⊆ Σ ω be an ω-language accepted by a Büchi 2-counter automaton A.

A way to construct a finite machine accepting the same ω-language but being real time would be to add a storage type called a queue [EH93].

Configurations of a queue are finite words over a finite alphabet Σ; a letter of Σ may be added to the rear of the queue or removed from the front; moreover there are tests to determine the first letter of the queue.

The new machine will read words in real time. At every transition a letter of the input ω-word is read, is added to the rear of the queue, waiting to be read (and then removed from the front of the queue) for the simulation of the reading of the input ω-word by the 2-counter automaton A.

We are going to see that one can simulate a queue with four counters. This simulation will not be a real time simulation but we shall be able to get an upper bound on the number of transitions of the four counters which are necessary for the simulation of one transition of the queue. This upper bound will be useful in the sequel for our purpose.

Claim 8. A queue can be simulated by two pushdown stacks.

Proof. Assume that the queue alphabet is Σ = {Z 2 , Z 3 , . . . , Z k-1 }, for some integer k ≥ 3. The content of the queue can be represented by a finite word Z i1 Z i2 Z i3 . . . Z im , where the letter Z im is the first letter of the queue and Z i1 is the last letter of the queue (the last added to the rear). This content can be stored in a pushdown stack whose alphabet is Γ = Σ ∪{Z 1 }, where Z 1 is the bottom symbol which appears only at the bottom of the stack and always remains there. The stack content representing the queue content

Z i1 Z i2 Z i3 . . . Z im will be simply Z 1 Z i1 Z i2 Z i3 . . . Z im ,
where Z 1 is at the bottom of the stack and Z im is at the top of the stack. If the letter Z im of the front of the queue is removed from the queue, it suffices to pop the same letter from the top of the stack. To simulate the addition of a new letter Z r to the rear of the queue we can use a second pushdown stack whose alphabet is also Γ . we have in fact to add the letter Z r between the letters Z 1 and Z i1 of the first pushdown stack. To achieve this, we successively pop letters from the top of the first stack, pushing them in the second stack containing only at the beginning the bottom symbol Z 1 . After having done this operation for letters Z im , Z im-1 , . . . Z i2 , Z i1 , the content of the first stack is Z 1 and the content of the second stack is Z 1 Z im Z im-1 . . . Z i2 Z i1 . We can then push the letter Z r at the top of the first stack. Then we successively pop letters Z i1 , Z i2 , Z i3 . . . , Z im from the top of the second stack, pushing them in the first stack. At the end of this operation the content of the first stack is Z 0 Z r Z i1 Z i2 Z i3 . . . Z im and it represents the new content of the queue.

We recall now the following well known property.

Claim 9 ([HU79]

). A pushdown stack can be simulated by two counters.

Proof. Consider a stack having

k-1 symbols Z 1 , Z 2 , . . . , Z k-1 . The stack content Z i1 Z i2 Z i3 . . . Z im
can be represented by the integer j which is given in base k by:

j = i m + k.i m-1 + k 2 .i m-2 + . . . + k m-1 .i 1
Notice that, as remarked in [HU79], not every integer represents a stack content.

In particular an integer whose representation in base k contains the digit 0 does not represent any stack content.

We are going to see how to use a second counter to determine which is the letter at the top of the stack, and to simulate the operations of pushing a letter in the stack or of popping a letter from the top of the stack.

Assume that the integer j representing the stack content Z i1 Z i2 Z i3 . . . Z im is stored in one of the two counters.

In order to determine which is the letter at the top of the stack, we can copy the content j in the second counter, using the finite control of the finite machine to compute j modulo k.

The integer j modulo k is equal to the integer i m which characterizes the letter Z im hence the letter at the top of the stack.

It would be possible to transfer again the integer j in the first counter, but one can also leave it in the second counter and use the finite control to know in which counter is stored the integer j.

Notice that this operation needs only j steps (and 2j steps if we transfer again j in the first counter).

If a letter Z r is pushed into the stack, the content of the stack is now

Z i1 Z i2 Z i3 . . . Z im Z r
and the integer associated with that content is j.k + r.

It is easy to store the integer j.k in the second counter, by adding k to this counter each time the first counter is decreased by 1. When the content of the first counter is equal to zero then the content of the second counter is equal to j.k. One can then add r to the second counter by using the finite control of the machine. Again we can use the finite control to know that now the content of the stack is coded by the integer which is in the second counter.

Notice that the whole operation needs only j.k + r steps.

If instead the symbol Z im is popped from the top of the stack, then the new content of the stack is Z i1 Z i2 Z i3 . . . Z im-1 and it is represented by the integer

[ j k ] = i m-1 + k.i m-2 + . . . + k m-2
.i 1 which is the integer part of j k . To get the integer [ j k ] as content of the second counter, we can decrease the first counter from j to zero, adding 1 to the second counter each time the first one is decreased by k. Notice that this operation needs only j steps. Remark also that we can achieve this operation in a non deterministic way, checking at the end of it which was the letter at the top of the stack.

We have seen above that a queue can be simulated with two pushdown stacks hence also with four counters. This simulation is not done in real time but we shall see that we can get an upper bound on the number of transitions of the four counters simulating one transition of the queue. This upper bound will be crucial in view of Lemma 7.

Claim 10. Assume as above that the queue alphabet is Σ = {Z 2 , Z 3 , . . . , Z k-1 }, for some integer k ≥ 3 and that at some time the content of the queue is a finite word Z i1 Z i2 Z i3 . . . Z im . Then the number of transitions of four counters which are needed to simulate the addition of a letter Z r to the rear of the queue is smaller than (2.k) m+2 .

Proof. Recall that the content of the queue can be stored in a pushdown stack whose alphabet is Γ = Σ ∪ {Z 1 }, where Z 1 is the bottom symbol. The stack content representing the queue content

Z i1 Z i2 Z i3 . . . Z im is simply Z 1 Z i1 Z i2 Z i3 . . . Z im ,
where Z 1 is at the bottom of the stack and Z im is at the top of the stack. This stack content Z 1 Z i1 Z i2 Z i3 . . . Z im can itself be represented by the integer j which is given in base k by:

j = i m + k.i m-1 + k 2 .i m-2 + . . . + k m-1 .i 1 + k m .1 ≤ k m+1
We have seen that, considering the simulation of the addition of Z r to the rear of a queue with two pushdown stacks, the first stack containing Z 1 Z i1 Z i2 Z i3 . . . Z im , we have first to successively pop letters Z im , . . . , Z i3 , Z i2 , Z i1 , from the top of the first stack and push them in the second stack. We have also seen above that popping a letter from the stack whose content is represented by the integer j needs only j transitions of two counters and that we can know at the end of this popping simulation which letter has just been popped. Moreover to push a letter Z s in the stack whose content is represented by an integer j ′ needs only j ′ .k + s transitions of two counters. Thus at most 2.m.k m+1 transitions of four counters are necessary to simulate the operation of successively popping letters Z im , . . . , Z i3 , Z i2 , Z i1 , from the top of the first stack and then pushing them in the second stack. Two transitions of the counters are needed to check that the content of the first stack is now reduced to Z 1 , which is simply represented by the integer 1, without changing this content; in one step the counter is reduced from one to zero then in a second step the counter is increased from zero to one. To simulate the addition of the letter Z r to the rear of the queue, we now push the letter Z r in the first stack; this is simulated by k + r transitions of two counters. Now we have to successively pop letters Z i1 , Z i2 , Z i3 , . . . , Z im , from the top of the second stack and push them again in the first stack. This whole operation needs less than m.k m+1 + m.k m+2 transitions of the four counters.

Finally, to simulate the addition of a letter Z r to the rear of the queue, we need only 2.m.

k m+1 + 2 + k + r + m.k m+1 + m.k m+2
transitions of four counters. This number is smaller than

4.m.k m+2 + 3.k ≤ (2.k) m+2 .
Claim 11. Assume as above that the queue alphabet is Σ = {Z 2 , Z 3 , . . . , Z k-1 }, for some integer k ≥ 3 and that at some time the content of the queue is a finite word Z i1 Z i2 Z i3 . . . Z im . Then the number of transitions of four counters which are needed to determine the letter Z im which is at the front of the queue is smaller than k m+1 . And the number of transitions of four counters which are needed to simulate the operation of removing the letter Z im from the front of the queue is smaller than k m+1 .

Proof. The content

Z i1 Z i2 Z i3 . . . Z im of the queue is represented by a stack con- tent Z 1 Z i1 Z i2 Z i3 . . . Z im ,
where Z 1 is at the bottom of the stack and Z im is at the top of the stack. This stack content is itself represented by the integer

j = i m + k.i m-1 + k 2 .i m-2 + . . . + k m-1 .i 1 + k m .1 ≤ k m+1
By the proof of Claim 9, j ≤ k m+1 transitions of four counters (and even of only two counters) suffice to determine the letter Z im which is at the top of the stack or to pop it from the top of the stack.

Claim 12. The ω-language θ S (Σ ω ) is in the class r-BCL(2) ω .

Proof. Recall that if Σ is an alphabet having at least two letters, E is a new letter not in Σ, S is an integer ≥ 1, then an ω-word y

∈ (Σ ∪ {E}) ω is in θ S (Σ ω ) iff it is in the form: θ 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 . . . for some x ∈ Σ ω .
It is easy to construct a real time Büchi 2-counter automaton B accepting θ S (Σ ω ). We describe now the behaviour of B when reading an ω-word y ∈ (Σ ∪ {E}) ω . After the reading of the first letter y(1) ∈ Σ, the automaton B adds one to the first counter for each letter E read, checking with the finite control that there are S letters E following y(1). Then B reads a second letter of Σ and next it adds S to the second counter and decreases the first counter by one each time it reads S letters E. When the first counter content is equal to zero, the second counter content is equal to S 2 and B has read S 2 letters E. It then reads a third letter of Σ, and next it adds S to the first counter and decreases the second counter by one each time it reads S letters E. When the second counter content is equal to zero, the first counter content is equal to S 3 and B has read S 3 letters E. Then B reads a fourth letter of Σ, and so on. The Büchi acceptance condition is used to check that the content of the first (and also of the second) counter takes infinitely many times the value zero.

End of Proof of Lemma 7. Let L ⊆ Σ ω be an ω-language accepted by a Büchi 2-counter automaton A. We are going to explain the behaviour of a real time Büchi 8-counter automaton A 1 accepting θ S (L) where S = (3k) 3 and k = cardinal(Σ) + 2. As explained in the proof of preceding Claim 12, two counters of A 1 will be used, independently of the other six ones, to check that the input ω-word y ∈ (Σ ∪ {E}) ω is in θ S (Σ ω ). Consider now the reading by A 1 of an ω-word y ∈ (Σ ∪ {E}) ω in the form y = θ 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 . . . for some x ∈ Σ ω . The automaton A 1 will simulate, using four counters, a queue in which will be successively stored letters x(1), x(2), . . . , x(n), . . . as soon as they will be read. Two other counters of A 1 will be used to simulate the reading of the ω-word x by the Büchi 2-counter automaton A. Notice that only letters x(1), x(2), . . . , x(n), . . . will be added to the rear of the queue. Therefore after having read the initial segment x(1).E S .x(2).E S 2 .x(3).E S 3 .x(4) . . . x(n).E S n of y the content of the queue has cardinal smaller than or equal to n. When A 1 reads x(n + 1) it will firstly simulate the addition of the letter x(n + 1) to the rear of the queue, using four counters, and doing this in real time while continuing to read some following letters E. By Claim 10, the number of transitions of four counters needed to simulate the addition of x(n + 1) to the rear of the queue is smaller than (2k) n+2 where k = cardinal(Σ) + 2. Next A 1 determines which is the letter at the front of the queue. By Claim 11 this needs at most k n+2 transitions of the four counters (because there are now at most (n+1) letters in the queue). Now the automaton A 1 simulates, using two counters, only one transition of A. This transition may be a λ-transition or not. In the second case A 1 simulates the reading by A of the letter at the front of the queue so this letter is removed from the queue; by Claim 11 this needs again at most k n+2 transitions of the four counters. It holds that

(2k) n+2 + k n+2 + k n+2 + 1 ≤ ((3k) 3 ) n
Thus if we set S = (3k) 3 then all these transitions of the six counters can be achieved by the automaton A 1 in real-time during the reading of the letters E following x(n + 1) in y. Not all the S n+1 letters E are read during these transitions of the six counters. But A 1 will read the other ones without changing the contents of the six counters, waiting for the reading of the next letter of Σ: the letter x(n + 2). It will then simulate the addition of this letter to the rear of the queue, and so on. A Muller condition can be used to ensure that y ∈ θ S (Σ ω ), i.e. y = θ S (x) for some x ∈ Σ ω , and that x ∈ L = L(A). As mentioned in Section 2, this can also be achieved with a Büchi acceptance condition.

Notice that we did not aim to find the smallest possible integer S but only to find one such integer in order to prove Lemma 7.

5 Borel hierarchy of ω-languages in r-BCL(1) ω

We shall firstly prove the following result.

Proposition 13. Let k ≥ 2 be an integer. If, for some ordinal α ≥ 2, there is an ω-language in the class r-BCL(k) ω which is Σ 0 α -complete (respectively, Π 0 αcomplete, Σ 0 α of rank α, Π 0 α of rank α), then there is some ω-language in the class r-BCL(1) ω which is Σ 0 α -complete (respectively, Π 0 α -complete, Σ 0 α of rank α, Π 0 α of rank α).

To simplify the exposition of the proof of this result, firstly, we are going to give the proof for k = 2. Next we shall explain the modifications to do in order to infer the result for the integer k = 8 which is in fact the only case we shall need in the sequel. (However our main result will show that the proposition is true for every integer k ≥ 2).

For that purpose we define first a coding of ω-words over a finite alphabet Σ by ω-words over the alphabet Σ ∪ {A, B, 0} where A, B and 0 are new letters not in Σ. We shall code an ω-word x ∈ Σ ω by the ω-word h(x) defined by h(x) = A.0 6 .x(1).B.0 6 2 .A.0 6 2 .x(2).B.0 6 3 .A.0 6 3 .x(3).B . . . B.0 6 n .A.0 6 n .x(n).B . . .

This coding defines a mapping

h : Σ ω → (Σ ∪ {A, B, 0}) ω .
The function h is continuous because for all ω-words x, y ∈ Σ ω and each positive integer n, it holds that δ(x, y) < 2 -n → δ(h(x), h(y)) < 2 -n .

Lemma 14. Let Σ be a finite alphabet and

(h(Σ ω )) -= (Σ ∪ {A, B, 0}) ω - h(Σ ω ). If L⊆ Σ ω is Σ 0 α -complete (respectively, Π 0 α -complete, Σ 0 α of rank α, Π 0 α of rank α), for a countable ordinal α ≥ 2, then h(L)∪h(Σ ω ) -is a subset of (Σ ∪ {A, B, 0}) ω which is Σ 0 α -complete (respectively, Π 0 α -complete, Σ 0 α of rank α, Π 0 α of rank α).
Proof. The topological space Σ ω is compact thus its image by the continuous function h is also a compact subset of the topological space (Σ ∪ {A, B, 0}) ω . The set h(Σ ω ) is compact hence it is a closed subset of (Σ ∪ {A, B, 0}) ω . Then its complement (h

(Σ ω )) -= (Σ ∪ {A, B, 0}) ω -h(Σ ω )
is an open (i.e. a Σ 0 1 ) subset of (Σ ∪ {A, B, 0}) ω .

On the other hand the function h is also injective thus it is a bijection from Σ ω onto h(Σ ω ). But a continuous bijection between two compact sets is an homeomorphism therefore h induces an homeomorphism between Σ ω and h

(Σ ω ). Assume that L is a Σ 0 α (respectively, Π 0 α ) subset of Σ ω . Then h(L) is a Σ 0 α (respectively, Π 0 α ) subset of h(Σ ω ) (
where Borel sets of the topological space h(Σ ω ) are defined from open sets as in the case of the topological space Σ ω ).

The topological space h(Σ ω ) is a topological subspace of (Σ ∪ {A, B, 0}) ω and its topology is induced by the topology on (Σ ∪ {A, B, 0}) ω : open sets of h(Σ ω ) are traces on h(Σ ω ) of open sets of (Σ ∪ {A, B, 0}) ω and the same result holds for closed sets. Then one can easily show by induction that for every ordinal α ≥ 1, Π 0 α -subsets (resp. Σ 0 α -subsets) of h(Σ ω ) are traces on h(Σ ω ) of Π 0 αsubsets (resp. Σ 0 α -subsets) of (Σ ∪ {A, B, 0}) ω , i.e. are intersections with h(Σ ω ) of Π 0 α -subsets (resp. Σ 0 α -subsets) of (Σ ∪ {A, B, 0}) ω .

But h(L) is a Σ 0 α (respectively, Π 0 α )-subset of h(Σ ω ), for some ordinal α ≥ 2, hence there exists a Σ 0 α (respectively, Π 0 α ) subset T of (Σ ∪{A, B, 0}) ω such that h(L)=T ∩h(Σ ω ). But h(Σ ω ) is a closed i.e. Π 0 1 -subset of (Σ ∪{A, B, 0}) ω and the class of

Σ 0 α (respectively, Π 0 α ) subsets of (Σ ∪ {A, B, 0}) ω is closed under finite intersection thus h(L) is a Σ 0 α (respectively, Π 0 α ) subset of (Σ ∪ {A, B, 0}) ω . Now h(L) ∪(h(Σ ω )) -is the union of a Σ 0 α (respectively, Π 0 α ) subset and of a Σ 0 1 -subset of (Σ ∪ {A, B, 0}) ω therefore it is a Σ 0 α (respectively, Π 0 α ) subset of (Σ ∪ {A, B, 0}) ω because the class of Σ 0 α (respectively, Π 0 α ) subsets of (Σ ∪ {A, B, 0}) ω is closed under finite union. Assume now firstly that L is Σ 0 α -complete (respectively, Π 0 α -complete). In order to prove that h(L)∪(h(Σ ω )) -is Σ 0 α -complete (respectively, Π 0 α -complete) it suffices to remark that L=h -1 [h(L)∪(h(Σ ω )) -] This implies that h(L)∪(h(Σ ω )) -is Σ 0 α -complete (respectively, Π 0 α -complete) because L is assumed to be Σ 0 α -complete (respectively, Π 0 α -complete).
On the other hand if we assume only that L is a Σ 0 α -set of rank α (respectively, Π 0 α -set of rank α), then we can infer that h(L)∪(h(Σ ω )) -is also a Σ 0 α -set of rank α (respectively, Π 0 α -set of rank α). Indeed if h(L)∪(h(Σ ω )) -was of Borel rank β < α then L=h -1 [h(L)∪(h(Σ ω )) -] would be also of rank smaller than α because the class Σ 0 β (respectively, Π 0 β ) is closed under inverse images by continuous functions.

In order to apply Lemma 14, we want now to prove that if L(A)⊆ Σ ω is accepted by a real time 2-counter automaton A with a Büchi acceptance condition then h(L(A))∪h(Σ ω ) -is accepted by a 1-counter automaton with a Büchi acceptance condition. We firstly prove the following lemma.

Lemma 15. Let Σ be a finite alphabet and h be the coding of ω-words over Σ defined as above. Then h(Σ ω ) -= (Σ ∪ {A, B, 0}) ωh(Σ ω ) is accepted by a real time 1-counter Büchi automaton.

Proof. We can easily see that h(Σ ω ) -= (Σ ∪ {A, B, 0}) ωh(Σ ω ) is the set of ω-words in (Σ ∪ {A, B, 0}) ω which belong to one of the following ω-languages.

-D 1 is the set of ω-words over the alphabet Σ ∪ {A, B, 0} which have not any initial segment in A.0 6 .Σ.B. It is easy to see that D 1 is in fact a regular ω-language.

-D 2 is the complement of (A.0 + .Σ.B.0 + ) ω in (Σ∪{A, B, 0}) ω . The ω-language (A.0 + .Σ.B.0 + ) ω is regular thus its complement D 2 is also a regular ωlanguage. -D 3 is the set of ω-words over the alphabet Σ ∪ {A, B, 0} which contain a segment in B.0 n .A.0 m .Σ for some positive integers n = m. It is easy to see that this ω-language can be accepted by a real time 1-counter Büchi automaton. -D 4 is the set of ω-words over the alphabet Σ ∪ {A, B, 0} which contain a segment in A.0 n .Σ.B.0 m .A for some positive integers n and m with m = 6n. Again this ω-language can be accepted by a real time 1-counter Büchi automaton.

The class r-BCL(1) ω is closed under finite union because it is the class of ωlanguages accepted by non deterministic real time 1-counter Büchi automata.

On the other hand it holds that h(Σ

ω ) -= (Σ ∪{A, B, 0}) ω -h(Σ ω ) = ∪ 1≤i≤4 D i thus h(Σ ω )
-is accepted by a real time 1-counter Büchi automaton.

We would like now to prove that if L(A)⊆ Σ ω is accepted by a real time 2counter automaton A with a Büchi acceptance condition then h(L(A)) is in BCL(1) ω . We cannot show this, so we are firstly going to define another ωlanguage L(A) accepted by a 1-counter Büchi automaton and we shall prove that h(L(A))∪h(Σ ω ) -= L(A)∪h(Σ ω ) -. We shall need the following notion. Let N ≥ 1 be an integer such that N = 2 x .3 y .N 1 where x, y are positive integers and N 1 ≥ 1 is an integer which is neither divisible by 2 nor by 3. Then we set P 2 (N ) = x and P 3 (N ) = y. So 2 P2(N ) is the greatest power of 2 which divides N and 2 P3(N ) is the greatest power of 3 which divides N . Let then a 2-counter Büchi automaton A= (K, Σ, ∆, q 0 , F ) accepting the ωlanguage L(A)⊆ Σ ω . The ω-language L(A) is the set of ω-words over the alphabet Σ ∪ {A, B, 0} in the form

integers i ≥ 1, v i , w i ∈ 0 + , u i , z i ∈ 0 ⋆ , x i ∈ Σ, |u 1 | = 5, |u i+1 | = |z i |
and there is a sequence (q i ) i≥0 of states of K and integers j i , j ′ i ∈ {-1; 0; 1}, for i ≥ 1, such that for all integers i ≥ 1:

x i : (q i-1 , P 2 (|v i |), P 3 (|v i |)) → A (q i , P 2 (|v i |) + j i , P 3 (|v i |) + j ′ i ) and |w i | = |v i |.2 ji .3 j ′ i
Moreover some state q f ∈ F occurs infinitely often in the sequence (q i ) i≥0 . Notice that the state q 0 of the sequence (q i ) i≥0 is also the initial state of A.

Lemma 16. Let A be a real time 2-counter Büchi automaton accepting ω-words over the alphabet Σ and L(A)⊆ (Σ ∪{A, B, 0}) ω be defined as above. Then L(A) is accepted by a 1-counter Büchi automaton B.

Proof. We shall explain informally the behaviour of a 1-counter Büchi automaton B accepting the ω-language L(A).

We firstly consider the reading of an ω-word x ∈ (A.0 ⋆ .Σ.B.0 ⋆ ) ω in the form where, for all integers i ≥ 1, n i , m i , are positive integers and x i ∈ Σ.

Using the finite control the automaton B first checks that the six first letters of x form the initial segment A.0 5 . Then, when reading the following (n 1 -5) letters 0, the automaton B, using the finite control, checks that (n 1 -5) > 0 and determines whether P 2 (n 1 -5) = 0 and whether P 3 (n 1 -5) = 0. Moreover the counter content is increased by one for each letter 0 read. The automaton B reads now the letter x 1 and it guesses a transition of A leading to

x 1 : (q 0 , P 2 (n 1 -5), P 3 (n 1 -5)) → A (q 1 , P 2 (n 1 -5) + j 1 , P 3 (n 1 -5) + j ′ 1 )
We set v 1 = 0 n1-5 and w 1 = 0 (n1-5).2 j 1 .3 j ′ 1 . The counter value is now equal to (n 1 -5) and, when reading letters 0 following x 1 , the automaton B checks that m 1 ≥ (n 1 -5).2 j1 .3 j ′ 1 in such a way that the counter value becomes 0 after having read the (n 1 -5).2 j1 .3 j ′ 1 letters 0 following the first letter B. For instance if

j 1 = j ′ 1 = 1 then |w 1 | = |v 1 |.
6 so this can be done by decreasing the counter content by one each time six letters 0 are read. The other cases are treated in a similar way. Details are here left to the reader. Notice also that the automaton B has kept in its finite control the value of the state q 1 . We set now 0 m1 = w 1 .z 1 . We have seen that after having read w 1 the counter value is equal to zero. Now when reading z 1 the counter content is increased by one for each letter read so that it becomes |z 1 | after having read z 1 . The automaton B reads now a letter A and next decreased its counter by one for each letter 0 read until the counter content is equal to zero. We set 0 n2 = u 2 .v 2 with u 2 = z 1 . The automaton B reads now the segment v 2 . Using the finite control, it checks that |v 2 | > 0 and determines whether P 2 (|v 2 |) = 0 and whether P 3 (|v 2 |) = 0. Moreover the counter content is increased by one for each letter 0 read. The automaton B reads now the letter x 2 and it guesses a transition of A leading to

x 2 : (q 1 , P 2 (|v 2 |), P 3 (|v 2 |)) → A (q 2 , P 2 (|v 2 |) + j 2 , P 3 (|v 2 |) + j ′ 2 )
We set w 2 = 0 |v2|.2 j 2 .3 j ′ 2 . The counter value is now equal to |v 2 |. The automaton B reads now the second letter B and, when reading the m 2 letters 0 following this letter B, the automaton B checks that m 2 ≥ |v 2 |.2 j2 .3 j ′ 2 in such a way that the counter value becomes 0 after having read the |v 2 |.2 j2 .3 j ′ 2 letters 0 following the second letter B. For instance if j 2 = 0 and j

′ 2 = -1 then |w 2 | = |v 2 |.
3 -1 so this can be done by decreasing the counter content by three each time one letter 0 is read. And if j 2 = -1 and j

′ 2 = -1 then |w 2 | = |v 2 |.2 -1 .3 -1 = |v 2 |.
6 -1 so this can be done by decreasing the counter content by six each time one letter 0 is read. The other cases are treated in a similar way. Details are here left to the reader. Notice that these different cases can be achieved with the use of λ-transitions but in such a way that there will be at most 5 consecutive λ-transitions during a run of B on x. This will be an important useful fact in the sequel. Notice also that the automaton B has kept in its finite control the value of the state q 2 . The reading of x by B continues in the same way. A Büchi acceptance condition can be used to ensure that some state q f ∈ K occurs infinitely often in the sequence (q i ) i≥0 .

To complete the proof we can remark that R=(A.0 ⋆ .Σ.B.0 ⋆ ) ω is a regular ωlanguage so we have considered only the reading by B of ω-words x ∈ R. Indeed if the ω-language L(B) was not included into R we could replace it by L(B)∩R because the class BCL(1) ω is closed under intersection with regular ω-languages (by a classical construction of product of automata, the ω-language R being accepted by a deterministic Muller automaton).

Lemma 17. Let A be a real time 2-counter Büchi automaton accepting ω-words over the alphabet Σ and L(A)⊆ (Σ ∪ {A, B, 0}) ω be defined as above. Then

L(A) = h -1 (L(A)), i.e. ∀x ∈ Σ ω h(x) ∈ L(A)←→ x ∈ L(A).
Proof. Let A be a real time 2-counter Büchi automaton accepting ω-words over the alphabet Σ and L(A)⊆ (Σ ∪ {A, B, 0}) ω be defined as above. Let x ∈ Σ ω be an ω-word such that h(x) ∈ L(A). So h(x) may be written

h(x) = A.0 6 .x(1).B.0 6 2 .A.0 6 2 .x(2).B.0 6 3 .A.0 6 3 .x(3).B . . . B.0 6 n .A.0 6 n .x(n).B . . . and also h(x) = A.u 1 .v 1 .x 1 .B.w 1 .z 1 .A.u 2 .v 2 .x 2 .B.w 2 .z 2 .A . . . A.u n .v n .x n .B.w n .z n .A . . .

where, for all integers

i ≥ 1, v i , w i ∈ 0 + , u i , z i ∈ 0 ⋆ , x i = x(i) ∈ Σ, |u 1 | = 5, |u i+1 | = |z i |
and there is a sequence (q i ) i≥0 of states of K and integers j i , j ′ i ∈ {-1; 0; 1}, for i ≥ 1, such that for all integers i ≥ 1:

x i : (q i-1 , P 2 (|v i |), P 3 (|v i |)) → A (q i , P 2 (|v i |) + j i , P 3 (|v i |) + j ′ i ) and |w i | = |v i |.2 ji .3 j ′ i
some state q f ∈ F occurring infinitely often in the sequence (q i ) i≥0 .

In particular, u 1 = 0 5 and u 1 .v 1 = 0 6 thus |v 1 | = 1 = 2 0 .3 0 . We are going to prove by induction on the integer i ≥ 1 that, for all integers i ≥ 1, |wi|) .3 P3(|wi|) . Moreover, setting c i 1 = P 2 (|v i |) and c i 2 = P 3 (|v i |), we are going to prove that for each integer i ≥ 1 it holds that

|w i | = |v i+1 | = 2 P2(
x i : (q i-1 , c i 1 , c i 2 ) → A (q i , c i+1 1 , c i+1 2 )
We have already seen that |v 1 | = 1 = 2 0 .3 0 . By hypothesis there is a state q 1 ∈ K and integers j 1 , j ′ 1 ∈ {-1; 0; 1} such that x 1 : (q 0 , P 2 (|v 1 |), (|wi|) .3 P3(|wi|) andx

P 3 (|v 1 |)) → A (q 1 , P 2 (|v 1 |) + j 1 , P 3 (|v 1 |) + j ′ 1 ), i.e. x 1 : (q 0 , 0, 0) → A (q 1 , j 1 , j ′ 1 ). Then |w 1 | = |v 1 |.2 j1 .3 j ′ 1 = 2 j1 .3 j ′ 1 . We have now |w 1 .z 1 | = |u 2 .v 2 | = 0 6 2 and |u 2 | = |z 1 | thus |v 2 | = |w 1 | = 2 j1 .3 j ′ 1 . Setting c 1 1 = 0, c 1 2 = 0, c 2 1 = j 1 = P 2 (|v 2 |) and c 2 2 = j ′ 1 = P 3 (|v 2 |), it holds that x 1 : (q 0 , c 1 1 , c 1 2 ) → A (q 1 , c 2 1 , c 2 2 ). Assume now that, for all integers i, 1 ≤ i ≤ n -1, it holds that |w i | = |v i+1 | = 2 P2
i : (q i-1 , c i 1 , c i 2 ) → A (q i , c i+1 1 , c i+1
2 ) where c i 1 = P 2 (|v i |) and c i 2 = P 3 (|v i |). We know that there is a state q n ∈ K and integers j n , j ′ n ∈ {-1; 0; 1} such that

x n : (q n-1 , P 2 (|v n |), P 3 (|v n |)) → A (q n , P 2 (|v n |) + j n , P 3 (|v n |) + j ′ n ), i.e. x n : (q n-1 , c n 1 , c n 2 ) → A (q n , c n 1 +j n , c n 2 +j ′ n ). Then |w n | = |v n |.2 jn .3 j ′ n = 2 c n 1 +jn .3 c n 2 +j ′ n . On the other hand |w n .z n | = |u n+1 .v n+1 | = 0 6 n+1 and |u n+1 | = |z n | thus |v n+1 | = |w n | = 2 c n 1 +jn .3 c n 2 +j ′ n = 2 c n+1 1 .3 c n+1 2 by setting c n+1 1 = P 2 (|v n+1 |) and c n+1 2 = P 3 (|v n+1 |). So we have x n : (q n-1 , c n 1 , c n 2 ) → A (q n , c n+1 1 , c n+1
2

).

Finally we have proved by induction the announced claim. If for all integers i ≥ 1, we set c i 1 = P 2 (|v i |) and c i 2 = P 3 (|v i |), it holds that

x i : (q i-1 , c i 1 , c i 2 ) → A (q i , c i+1 1 , c i+1 2 )
But there is some state q f ∈ K which occurs infinitely often in the sequence (q i ) i≥1 . This implies that (

q i-1 , c i 1 , c i 2 ) i≥1 is a successful run of A on x thus x ∈ L(A).
Conversely it is easy to see that if x ∈ L(A) then h(x) ∈ L(A). This ends the proof of Lemma 17.

Remark 18. The simulation, during the reading of h(x) by the 1-counter Büchi automaton B, of the behaviour of the real time 2-counter Büchi automaton A reading x, can be achieved, using a coding of the content (c 1 , c 2 ) of two counters by a single integer 2 c1 .3 c2 and the special shape of ω-words in h(Σ ω ) which allows the propagation of the counter value of B. This will be sufficient here, because of the previous lemmas, and in particular of the fact that h(Σ ω ) -is in the class r-BCL(1) ω , and we can now end the proof of Proposition 13.

End of Proof of Proposition 13. Let α ≥ 2 be an ordinal. Assume that there is an ω-language L(A)⊆ Σ ω which is Σ 0 α -complete (respectively, Π 0 α -complete, Σ 0 α of rank α, Π 0 α of rank α) and is accepted by a real time 2-counter Büchi automaton A. By Lemma 14, h(L)∪h(Σ ω ) -is a subset of (Σ ∪{A, B, 0}) ω being Σ 0 α -complete (respectively, Π 0 α -complete, Σ 0 α of rank α, Π 0 α of rank α) . On the other hand Lemma 17 states that L(A) = h -1 (L(A)) and this implies that h(L(A))∪h(Σ ω ) -= L(A)∪h(Σ ω ) -. But we know by Lemmas 15 and 16 that the ω-languages h(Σ ω ) -and L(A) are in the class BCL(1) ω thus their union is also accepted by a 1-counter Büchi automaton. Therefore h(L(A))∪h(Σ ω ) - is an ω-language in the class BCL(1) ω which is Σ 0 α -complete (respectively, Π 0 αcomplete, Σ 0 α of rank α, Π 0 α of rank α).

We want now to find an ω-language in the class r-BCL(1) ω which is Σ 0 α -complete (respectively, Π 0 α -complete, Σ 0 α of rank α, Π 0 α of rank α). On one side we have proved that h(Σ ω ) -is accepted by a real time 1-counter Büchi automaton. On the other side we have proved that L(A) is accepted by a (non real time) 1-counter Büchi automaton B. However we have seen, in the proof of Lemma 16, that at most 5 consecutive λ-transitions can occur during the reading of an ω-word x by B. Consider now the mapping φ : (Σ ∪ {A, B, 0}) ω → (Σ ∪ {A, B, F, 0}) ω which is defined, for all x ∈ (Σ ∪ {A, B, 0}) ω by: φ(x) = F 5 .x(1).F 5 .x(2).F 5 .x(3) . . . F 5 .x(n).F 5 .x(n + 1).F 5 . . . The function φ is continuous and separates two successive letters of x by five letters F . We can prove, as in the proof of Lemma 6, that if

L ⊆ (Σ ∪{A, B, 0}) ω is Σ 0 α -complete (respectively, Π 0 α -complete, Σ 0 α of rank α, Π 0 α of rank α), for some ordinal α ≥ 2, then φ(L) is a subset of (Σ ∪ {A, B, F, 0}) ω which is Σ 0 α - complete (respectively, Π 0 α -complete, Σ 0 α of rank α, Π 0 α of rank α).
Thus the ω-language φ(L(A)∪h

(Σ ω ) -) is Σ 0 α -complete (respectively, Π 0 α -complete, Σ 0 α of rank α, Π 0 α of rank α).
Moreover it is easy to see that φ(L(A)) is accepted by a real time 1-counter Büchi automaton B ′ . The automaton B ′ checks with its finite control that an input ω-word is in the form φ(x) for some x ∈ (Σ ∪{A, B, 0}) ω . And B ′ simulates the reading of x by B, the λ-transitions of B occuring during the reading, in real time, of letters F of the ω-word φ(x).

Finally φ(L(A)∪h(Σ ω ) -) = φ(L(A))∪φ(h(Σ ω ) -))
is the union of two ω-languages in r-BCL(1) ω thus it is in r-BCL(1) ω and it is Σ 0 α -complete (respectively, Π 0 αcomplete, Σ 0 α of rank α, Π 0 α of rank α). This ends the proof of Proposition 13 for the integer k = 2.

We explain now the modifications to do in order to prove Proposition 13 for the integer k = 8. We assume that α ≥ 2 is an ordinal and that there is an ω-language L(A)⊆ Σ ω which is Σ 0 α -complete (respectively, Π 0 α -complete, Σ 0 α of rank α, Π 0 α of rank α) and is accepted by a real time 8-counter Büchi automaton A. We first modify the coding of ω-words which was given by the mapping h. We replace the number 6 = 2.3 by the product of the eight first prime numbers: 3.5.7.11.13.17.19 = 9699690 Then an ω-word x ∈ Σ ω will be coded by the ω-word

K = 2.
h K (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 . . . The mapping h K : Σ ω → (Σ ∪ {A, B, 0}) ω is continuous and we can prove, as in Lemma 14, that h K (L(A))∪h K (Σ ω ) -is a subset of (Σ ∪ {A, B, 0}) ω which is Σ 0 α -complete (respectively, Π 0 α -complete, Σ 0 α of rank α, Π 0 α of rank α). As in
Lemma 15, we can prove that h K (Σ ω ) -is in the class r-BCL(1) ω .

Next, for each prime number p ∈ {2; 3; 5; 7; 11; 13; 17; 19}, and each positive integer N ≥ 1, we denote P p (N ) the positive integer such that p Pp(N ) is the greatest power of p which divides N . We define the ω-language L(A) as the set of ω-words over the alphabet Σ ∪ {A, B, 0} in the form

A.u 1 .v 1 .x 1 .B.w 1 .z 1 .A.u 2 .v 2 .x 2 .B.w 2 .z 2 .A . . . A.u n .v n .x n .B.w n .z n .A . . .

where, for all integers

i ≥ 1, v i , w i ∈ 0 + , u i , z i ∈ 0 ⋆ , |u 1 | = K-1, |u i+1 | = |z i | and
there is a sequence (q i ) i≥0 of states of K and integers j 1 i , j 2 i , . . . , j 8 i , ∈ {-1; 0; 1}, for i ≥ 1, such that for all integers i ≥ 1:

x i : (q i-1 , P 2 (|v i |), P 3 (|v i |), . . . , P 19 (|v i |)) → A (q i , P 2 (|v i |)+j 1 i , P 3 (|v i |)+j 2 i , . . . , P 19 (|v i |)+j 8 i ) and |w i | = |v i |.2 j 1 i .3 j 2 i . . . . .19 j 8 i
and some state q f ∈ F occurs infinitely often in the sequence (q i ) i≥0 .

Applying the same ideas as in the proofs of Lemmas 16 and 17 we can prove that L(A) is accepted by a 1-counter Büchi automaton and that L(A)= h -1 K (L(A)). The essential change is that now the content (c 1 , c 2 , . . . , c 8 ) of eight counters is coded by the product 2 c1 .3 c2 . . . . .(17) c7 .( 19) c8 . Notice that again L(A) is accepted by a (non real time) 1-counter Büchi automaton B. However there are now at most (K -1) consecutive λ-transitions which can occur during the reading of an ω-word x by B. So we define now the mapping φ K : (Σ ∪ {A, B, 0}) ω → (Σ ∪ {A, B, F, 0}) ω by: for all x ∈ (Σ ∪ {A, B, 0}) ω , φ K (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 . . . The function φ K is continuous as the function φ was. The end of the proof is unchanged so we infer that φ K (h K (L(A))∪h K (Σ ω ) -) is an ω-language in the class r-BCL(1) ω which is Σ 0 α -complete (respectively, Π 0 α -complete, Σ 0 α of rank α, Π 0 α of rank α).

From the results of Section 4 and Proposition 13, we can now state the following result.

Theorem 19. Let C be a class of ω-languages such that: 6 Wadge hierarchy of ω-languages in r-BCL(1) ω

r-BCL(1) ω ⊆ C⊆ Σ 1 1 . (a)
We now introduce the Wadge hierarchy, which is a great refinement of the Borel hierarchy defined via reductions by continuous functions, [Dup01,Wad83].

Definition 20 (Wadge [Wad83]). 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 -,
′ ⊆ 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.

We can now define the Wadge class of a set L:

Definition 21. 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 .
There is a close relationship between Wadge reducibility and games which we now introduce.

Definition 22. 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, the player 1 has written an ω-word a ∈ X ω and the player 2 has written an ω-word b ∈ Y ω . The player 2 is allowed to skip, even infinitely often, provided he really writes an ω-word in ω steps. 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(X) (see [Kec95]), with X a borel set, is determined and this implies the following :

Theorem 23 (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 the player 2 has a winning strategy in the game W (L, L ′ ).

Theorem 24 (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 [Wad83,Dup01] by the use of the Veblen functions.

It is natural to ask for the Wadge hierarchy of classes of ω-languages accepted by finite machines, like X-automata. The Wadge hierarchy of regular ω-languages, now called the Wagner hierarchy, has been effectively determined by Wagner; it has length ω ω [Wag79,Sel95,Sel98]. Wilke and Yoo proved in [WY95] that one can compute in polynomial time the Wadge degree of an ω-regular language. The Wadge hierarchy of ω-languages accepted by Muller deterministic one blind (i. e. without zero-test) counter automata is an effective extension of the Wagner hierarchy studied in [Fin01a]. Its extension to deterministic context free ω-languages has been determined by Duparc, its length is ω (ω 2 ) [DFR01,Dup03] but we do not know yet whether it is effective. Selivanov has recently determined the Wadge hierarchy of ω-languages accepted by deterministic Turing machines; its length is (ω CK 1 ) ω [Sel03a,Sel03b].

In previous papers we have inductively constructed, using the work of Duparc on the Wadge hierarchy of Borel sets [Dup01], 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, [Fin01c,Fin01b,Fin03a,Fin03b]. Notice that the Wadge hierarchy of non-deterministic context-free ω-languages is not effective.

We are going to show here the very surprising following result, which extends Theorem 19.

Theorem 25. 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.

To prove this result, we are going to consider first non self dual sets. We recall the definition of Wadge degrees introduced by Duparc in [Dup01] and which is a slight modification of the previous one.

Definition 26. (a) d w (∅) = d w (∅ -) = 1 (b) d w (L) = sup{d w (L ′ ) + 1 | L ′ non self dual and L ′ < W L} (for either L self dual or not, L > W ∅).
We are going now to introduce the operation of sum of sets of infinite words which has as counterpart the ordinal addition over Wadge degrees.

Definition 27 (Wadge, see [Dup01]). Assume that X ⊆ Y are two finite alphabets, Y -X containing at least two elements, and that {X + , X -} is a partition of Y -X in two non empty sets. Let L ⊆ X ω and L ′ ⊆ Y ω , then

L ′ +L = df L∪{u.a.β | u ∈ X ⋆ , (a ∈ X + and β ∈ L ′ ) or (a ∈ X -and β ∈ L ′-)}
This operation is closely related to the ordinal sum as it is stated in the following:

Theorem 28 (Wadge, see [Dup01]). Let X ⊆ Y , Y -X containing at least two elements, L ⊆ X ω and L ′ ⊆ Y ω be non self dual Borel sets. Then (L + L ′ ) is a non self dual Borel set and d w (L ′ + L) = d w (L ′ ) + d w (L).
A player in charge of a set L ′ + L in a Wadge game is like a player in charge of the set L but who can, at any step of the play, erase his previous play and choose to be this time in charge of L ′ or of L ′-. Notice that he can do this only one time during a play. We shall use this property below.

Lemma 29. Let L ⊆ Σ ω be a non self dual Borel set such that d w (L) ≥ ω.

Then it holds that L ≡ W ∅ + L.

Notice that in the above lemma, ∅ is viewed as the empty set over an alphabet Γ such that Σ ⊆ Γ and cardinal (Γ -Σ) ≥ 2.

Proof. Assume that L ⊆ Σ ω is a non self dual Borel set and that d w (L) ≥ ω. We know that ∅ is a non self dual Borel set and that d w (∅) = 1. Let then L ⊆ Σ ω be a non self dual Borel set acccepted by a Turing machine with a Büchi acceptance condition ( in particular L is in the class BCL(2) ω ) such that d w (L) ≥ ω. Lemma 7 states that there exists an integer S ≥ 1 such that θ S (L) is in the class r-BCL(8) ω , where E is a new letter not in Σ and θ S : Σ ω → (Σ ∪ {E}) ω is the function defined, for all x ∈ Σ ω , by: θ 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 . . .

We are going to prove that θ S (L) ≡ W L.

Firstly, it is easy to see that L ≤ W θ S (L). In order to prove this we can consider the Wadge game W (L, θ S (L)). It is easy to see that Player 2 has a winning strategy in this game which consists in copying the play of Player 1, except that Player 2 adds letters E in such a way that he has written the initial word x(1).E S .x(2).E S 2 .x(3).E S 3 .x(4) . . . x(n).E S n while Player 1 has written the initial word x(1).x(2).x(3).x(4) . . . x(n). Notice that one can admit that a player writes a finite word at each step of the play instead of a single letter. This does not change the winner of a Wadge game.

To prove that θ S (L) ≤ W L, it suffices to prove that θ S (L) ≤ W ∅ + L because Lemma 29 states that ∅ + L ≡ W L. Consider the Wadge game W (θ S (L), ∅ + L).

Player 2 has a winning strategy in this play which consists first in copying the play of player 1 except that Player 2 skips when player 1 writes a letter E. He continues forever with this strategy if the word written by player 1 is always a prefix of some ω-word of θ S (Σ ω ). Then after ω steps Player 1 has written an ω-word θ S (x) for some x ∈ Σ ω , and Player 2 has written x. So in that case θ S (x) ∈ θ S (L) iff x ∈ L iff x ∈ ∅ + L. But if at some step of the play, Player 1 "goes out of" the closed set θ S (Σ ω ) because the word he has now written is not a prefix of any ω-word of θ S (Σ ω ), then its final word will be surely outside θ S (Σ ω ) hence also outside θ S (L). Player 2 can now writes a letter of Γ -Σ in such a way that he is now like a player in charge of the emptyset and he can now writes an ω-word u so that his final ω-word will be outside ∅ + L. Thus Player 2 wins this play too.

Finally we have proved that L ≤ W θ S (L) ≤ W L thus it holds that θ S (L) ≡ W L. This ends the proof.

Lemma 31. Let L ⊆ Σ ω be a non self dual Borel set in the class r-BCL(8) ω .

Then there is an ω-language L ′ ∈ r-BCL(1) ω such that L ≡ W L ′ .

Proof. As in the preceding proof we can consider only ω-languages of Wadge degrees greater than or equal to ω.

Let then L = L(A)⊆ Σ ω be a non self dual Borel set acccepted by a real time 8-counter Büchi automaton A such that d w (L) ≥ ω. We have shown in the preceding section that φ K (h K (L(A))∪h K (Σ ω ) -) is in the class r-BCL(1) ω , where h K is the continuous mapping h K : Σ ω → (Σ ∪ {A, B, 0}) ω defined by : for all x ∈ Σ ω , h K (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 . . . and the mapping φ K : (Σ ∪ {A, B, 0}) ω → (Σ ∪ {A, B, F, 0}) ω is defined by: for all x ∈ (Σ ∪ {A, B, 0}) ω , φ K (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 . . .

We can now prove, by a very similar reasoning as in the proof of the preceding Lemma 30, using the fact that d w (L) ≥ ω, that

L ≡ W h K (L(A))∪h K (Σ ω ) -≡ W φ K (h K (L(A))∪h K (Σ ω ) -) But φ K (h K (L(A))∪h K (Σ ω ) -
) is in the class r-BCL(1) ω , and this ends the proof.

End of Proof of Theorem 25. Let L ⊆ Σ ω be a Borel set acccepted by a Turing machine with a Büchi acceptance condition (in particular L is in the class BCL(2) ω ). If the Wadge degree of L is finite, it is well known that it is Wadge equivalent to a regular ω-language, hence also to an ω-language in the class r-BCL(1) ω . If L is non self dual and its Wadge degree is greater than or equal to ω, then we can infer from Lemmas 30 and 31 that there is an ω-language L ′ ∈ r-BCL(1) ω such that L ≡ W L ′ . It remains to consider the case of self dual Borel sets. The alphabet Σ being finite, a self dual Borel set L is always Wadge equivalent to a Borel set in the form Σ 1 .L 1 ∪ Σ 2 .L 2 , where (Σ 1 , Σ 2 ) form a partition of Σ, and L 1 , L 2 ⊆ Σ ω are non self dual Borel sets such that L 1 ≡ W L - 2 . Moreover L 1 and L 2 can be taken in the form L (u1) = u 1 .Σ ω ∩ L and L (u2) = u 2 .Σ ω ∩ L for some u 1 , u 2 ∈ Σ ⋆ , see [Dup03]. So if L ⊆ Σ ω is a self dual Borel set accepted by a Turing machine with a Büchi acceptance condition then L ≡ W Σ 1 .L 1 ∪ Σ 2 .L 2 , where (Σ 1 , Σ 2 ) form a partition of Σ, and L 1 , L 2 ⊆ Σ ω are non self dual Borel sets accepted by a Turing machine with a Büchi acceptance condition. We have already proved that there is an ω-language L ′ 1 ∈ r-BCL(1) ω such that L ′ 1 ≡ W L 1 and an ω-language L ′ 2 ∈ r-BCL(1) ω such that L ′-

2 ≡ W L 2 . Thus L ≡ W Σ 1 .L 1 ∪Σ 2 .L 2 ≡ W Σ 1 .L ′ 1 ∪Σ 2 .L ′ 2 and Σ 1 .L ′ 1 ∪ Σ 2 .L ′
2 is in the class r-BCL(1) ω .

Remark 32. We have only considered above the Wadge hierarchy of Borel sets. If we assume the axiom of Σ 1 1 -determinacy, then Theorem 24 can be extended by considering the class of analytic sets instead of the class of Borel sets. In fact in that case any set which is analytic but not Borel is Σ 1 1 -complete, see [Kec95]. So there is only one more Wadge degree containing Σ 1 1 -complete sets. It was already proved in [Fin03a] that there is a Σ 1 1 -complete set accepted by a Büchi 1-counter automaton and it is easy to see from the proof that one can find such a Σ 1 1 -complete set accepted by a Büchi 1-counter real-time automaton.

Remark 33. The result given by Theorem 19 can now be deduced from Theorem 25 and it can be seen as a particular case of this last result, because the Wadge hierarchy is a refinement of the Borel hierarchy and, for each countable non null ordinal γ, Σ 0 γ -complete sets (respectively, Π 0 γ -complete sets) form a single equivalence class of ≡ W , i.e. a single Wadge degree, [Kec95]. However we have preferred to expose the results given in this paper by considering firstly the Borel hierarchy. This way the reader who is just interested by the Borel hierarchy of ω-languages can read this part and skip Section 6 about the Wadge hierarchy.

Concluding remarks

We have proved that the Borel and the Wadge hierarchies of classes r-BCL(1) ω and CFL ω are also the Borel and the Wadge hierarchies of the class Σ 1 1 . The methods used in this paper are different from those used in previous papers on context free ω-languages [Fin01c,Fin01b,Fin03a,Fin03b], where we gave an inductive construction of some ∆ 0 ω context free ω-languages of a given Borel rank or Wadge degree, using work of Duparc on the Wadge hierarchy of ∆ 0 ω Borel sets, [Dup01]. However it will be possible to combine both methods for the effective construction of ω-languages in the class r-BCL(1) ω , and of 1-counter Büchi automata accepting them, of a given Wadge degree among the ε ω degrees obtained in [Fin01b] for ∆ 0 ω context free ω-languages.

Finally we mention that in another paper, using the results of this paper and applying similar methods to the study of topological properties of infinitary rational relations, we prove that their Wadge and Borel hierarchies are equal to the corresponding hierarchies of the classes r-BCL(1) ω , CFL ω or Σ 1 1 , [Fin06].

x

  = A.0 n1 x 1 .B.0 m1 .A.0 n2 x 2 .B.0 m2 .A . . . A.0 np x p .B.0 mp .A . . .

  The Borel hierarchy of the class C is equal to the Borel hierarchy of the classΣ 1 1 . (b) γ 1 2 = Sup {α | ∃L ∈ C such that L is a Borel set of rank α}. (c) For every non null ordinal α < ω CK1 , there exists some Σ 0 α -complete and some Π 0 α -complete ω-languages in the class C. Notice that above (b) and (c) just follow from (a) and from the known results about the Borel hierarchy of the class Σ 1 1 .

  The 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)].

  and otherwise it is said to be non self dual.The relation ≤ W is reflexive and transitive, and ≡ W is an equivalence relation. The equivalence classes of ≡ W are called Wadge degrees. The Wadge hierarchy W H is the class of Borel subsets of a set X ω , where X is a finite set, equipped with ≤ W and with ≡ W . For L ⊆ X ω and L

  Thus, by Theorem 28, it holds that d w (∅ + L) = d w (∅) + d w (L) = 1 + d w (L). But by hypothesis d w (L) ≥ ω and this implies that 1 + d w (L) = d w (L). So we have proved that d w (∅ + L) = d w (L). On the other hand L is non self dual and d w (∅ + L) = d w (L) imply that only two cases may happen : either∅ + L ≡ W L or ∅ + L ≡ W L -.But it is easy to see that L ≤ W ∅+L. For that purpose consider the Wadge game W (L, ∅ + L). Player 2 has clearly a winning strategy which consists in copying the play of Player 1 thus L ≤ W ∅ + L. This implies that ∅ + L ≡ W L -cannot hold so ∅ + L ≡ W L.Lemma 30. Let L ⊆ Σ ω be a non self dual Borel set acccepted by a Turing machine with a Büchi acceptance condition. Then there is an ω-language L ′ ∈ r-BCL(8) ω such that L ≡ W L ′ .Proof. It is well known that there are regular ω-languages of every finite Wadge degree,[Sta97,Sel98]. These ω-languages are Boolean combinations of open sets. So we have only to consider the case of non self dual Borel sets of Wadge degrees greater than or equal to ω.

Acknowledgements

Thanks to the anonymous referee for useful comments on a preliminary version of this paper.


Etienne Talbot

Rodrigue Lardé

Fabrice Gourbilleau

C Dufour

Philippe Pareige

Investigation of the Si-rich silicon oxide by 3D atom probe tomography

Silicon rich silicon oxide multilayers for optical devices have been investigated by laser assisted wide angle atom probe tomography. Three dimensional mapping of silicon nanoclusters multilayers was obtained. The composition of the different phases were deduced and compared to theoretical concentration. These results evidenced a size distribution of the Si clusters diameter and an incomplete phase separation between silica and silicon particles.

INTRODUCTION

The miniaturization and the integration of photonic components, notably for the telecommunications, are one of the main stakes of this last decade. In particular, Si based systems presenting promising potential for realization of light sources [1,2], waveguide amplifiers [1,3] and electroluminescence diodes compatible with the Si technology. One of the major lines deal with Silicon nanoclusters (Si-nc) embedded in silica which are promising for the realization of Si-based photonic devices. For example, Er doped silicon rich silica (SRSO) are promising candidate for planar optical amplifier at the wavelength of 1,54µm, which correspond to the minimum attenuation of silica optical fiber. In these systems, Si nanoclusters (Si-nc) have a sensitizer effect on Er 3+ ions, and enhanced the effective cross section of rare earth dopants by means of an efficient energy transfer between Si-nc and Er ions. To improve the properties of these devices, it will be essential to characterize more precisely Si nanoparticles and especially size distribution and interface nature between Si-nc and matrix in samples annealed in the optimized conditions of the Er emission [4,5,6].

In this paper, we report for the first time 3D mapping of Si-nc embedded in SiO 2 at the atomic level. We focused our study on the local chemistry, size distribution, and Si-nc density in SRSO/SiO 2 multilayered structures annealed at 900°C during one hour. The results are compared to the "theoretical" case of complete phase separation between Si and SiO 2 .

EXPERIMENT

SRSO/SiO 2 multilayers (MLs) were prepared on Si substrates ([110] oriented) by an alternative reactive magnetron sputtering of the silica target under a plasma of 50% H 2 + 50% Ar to obtain SRSO sublayers, owing to the ability of hydrogen to reduce oxygen [7] and under a plasma of pure Ar to deposit the SiO 2 sublayers. The MLs were grown at 650°C with a power density of 1.3 W.cm -2 and were subsequently annealed at 900°C for 1h under a flux of N 2 mixed with 5% of H 2 in order to favor the phase separation between Si and SiO 2 . The thickness of the SiO 2 and SRSO sublayers are 4nm and 3.8nm, respectively, and the size of the Si dots is limited by the thickness of the SRSO layers. High Resolution Transmission Electron Microscopy was performed using a Topcon 002B on samples prepared in the cross-section configuration.

Three-dimensional laser assisted atom probe tomography (3D-APT) analysis provides a spatial chemical map at the atomic scale of a material with an ultrahigh spatial resolution (depth resolution ~0.1 nm) [8,[START_REF] Miller | Atom Probe Tomogrpahy: Analysis at the Atomic Level[END_REF]. The use of APT on semiconductor or insulator has always been limited due to the poor conductivity of these materials. Today, the recent development of the laser assisted APT allows to analyze these materials [START_REF] Kellog | [END_REF]11]. During the analysis, a high positive DC voltage (several kilovolts) is applied on the sample in order to create a high electric field at the apex of the tip. The superposition of femtosecond laser pulses lead to the controlled evaporation of the specimen. The evaporated ions are collected on a position-sensitive detector which is used to i) measure the time of flight of individual ions and ii) the impact position of each ion on the surface of the detector. These data permit the three dimensional reconstruction of the analyzed volume. One requirement is the sharp tip shaped sample with an end curvature radius smaller than 50nm and a small cone angle in order to create a very high electric field at the surface of the tip. The specimen is prepared using Focus Ion Beam (FIB) annular milling [12,13]. SRSO/SiO 2 samples were prepared using a focused Ga beam (30 kV). To prevent ion beam damage and gallium implantation, samples were protected with a ~300nm Cr layer and the final steps of milling were performed at low acceleration voltage (2 kV). The results described in this paper were obtained by means of a Laser Assisted Wide Angle Tomographic Atom Probe (LAWATAP) from CAMECA. These experiments were performed at 80K in an ultrahigh vacuum chamber at a pressure of 10 -8 Pa, and using femtosecond laser pulsing (50 nJ, 350 fs) at the wavelength of 343 nm.

DISCUSSION

The cross-sectional HRTEM image of the SRSO/SiO 2 multilayers is shown on Figure 1.(a). A careful observation of this micrograph allows to reveal the presence of crystallized Si nanoclusters. Si-nc are only localized in the SRSO sublayers. As expected by the multilayers structures, no clusters with a diameter greater than the thickness of the SRSO layers are detected. However, due to the poor contrast between silica matrix and Si-nc, small or amorphous nanoclusters are not distinguishable with such a technique. Therefore, it is difficult to estimate the density and the size distribution of the Si-nc. The nominal composition, stacking of all MLs, was X Si =41% and X O =59%. This corresponds to an excess of silicon of ~11% for the MLs, which is about ~25% in the SRSO sublayers. Under the hypothesis of complete phase separation between Si and SiO 2 (

Si x SiO x SiO x ) 2 1 ( 2 2 - + →
), we can calculate the particles density in the MLs. In this case, all Si-nc have a diameter of 3.8nm, a sharp interface with the matrix and the density of Si-nc is about ~ 5.1×10 18 Si-nc/cm 3

3D-APT results

We have performed Laser Assisted Atom Probe Tomography analyses on these SRSO/SiO 2 MLs. A typical 3D reconstruction of the analysed volume is shown in Figure 2.(a). Alternating silica and silicon rich silica (indicate by arrows) regions are clearly distinguishable on this image. These results clearly evidence the alternating composition of the sample with layer of pure silica and layer of Si-nc in silica matrix. The associated concentration profile along the sample growth direction is presented in Figure 2.(b). The abscise axis corresponds to the ML's growth direction. The overall measured composition is X Si ≈ 43.0 ± 0.3% and X O ≈ 57.0 ± 0.3%, which correspond to a Si excess of ~14%, in good agreement with the nominal composition. The concentration in sublayers of pure silica is X Si ≈ 34.3 ± 0.3% and X O ≈ 65.7 ± 0.3%, and it is X Si ≈ 51.0 ± 0.3% and X O ≈ 49.0 ± 0.3% in the SRSO sublayers. The Si excess reached in the SRSO regions is about ~26% in good agreement with the nominal content. shows a 3D iso-concentration surface image of the multilayers which reveals the presence of Si-nc (red-zones) embedded in silica regions (green-zones). This image clearly evidenced the expected uniform distribution of Si-nc in the SRSO sublayers alternatively with pure silica sublayers after a 1h-annealing at 900°C. Data treatment of the 3D-APT analyses allow us to investigate independently, at the atomic scale, each nano-cluster or the matrix (excluding Si-nc). First, the composition of the SRSO matrix (measured after subtraction of the Si-nc cluster), which corresponds to the decomposition of the surrounding Si-nc, has been obtained. The measured SRSO matrix composition is X Si matrix ≈ 41.9 ± 0.3% and X O matrix ≈ 58.1 ± 0.3%, which is significantly higher than pure silica phase (X Si =33.3% and X O =66.7%) and indicating an incomplete phase separation. The Si excess remaining in the SRSO sublayers after 1hannealing at 900°C is ~13%, i.e. only ~50% of the Si excess has precipitated. The annealing conditions (1h at 900°C) are not long enough to ensure a complete phase separation of the system. These results confirm the slow phase separation process at this temperature as suggested by Iacona et al. [14]. Finally, the Si-nc size distribution in the SRSO/SiO 2 multilayers was studied and compared to the ideal case of a complete phase separation. An accurate size distribution of the silicon clusters in the SRSO layers is presented in figure 3.(b). The detections of small Si-nc embedded in silica matrix by APT highlight the capability of this technique compared to other ones (HRTEM, XRD, Raman spectroscopy, EFTEM …). On the figure 3.(b), the diameter ranges from 0.5 to 4.5 nm. The mean diameter was estimated to 2.9 nm. The silicon rich silicon oxide -silica multilayers was used to prevent Si diffusion in the silica during phase separation and the growth of clusters, and as a consequence limit the Si-nc size to the thickness of the SRSO sublayers. As expected, the presence of the SiO 2 sublayers on each side of the SRSO one limits efficiently the diameter of the Si-nc which has been found in majority to be less than 3.8 nm (i.e. less than the thickness of the SRSO layer). As evidenced by the size distribution (figure 3.b), there are small clusters in the ML's. Their presence can be explained by the incomplete phase separation between Si and SiO 2 . The detection of Si particles with a diameter greater than silica sublayers thickness can be partially explained by a poor interface quality between SiO 2 and SRSO layers and uncertainties on the layer thickness. The Si nanocluster number density is estimated to 5.7±1.0×10 18 Sinc/cm 3 . This result can be compared to the "theoretical" prediction of a complete phase separation between Si and SiO 2 phases considering that all nanoclusters have a diameter of 3.8 nm (figure 3.b). In this case, the Si-nc density would be about 5.1×10 18 Si-nc/cm 3 . The measured density is in good agreement with the hypothesis of a complete phase separation, but our size distribution evidenced the fact that annealing time and/or annealing temperature are not so long to favour homogeneous Si-nc size density.

CONCLUSIONS

In summary, Si nanoclusters array in SRSO/SiO 2 multilayered structures have been investigated by an original approach by means of three-dimensional atom probe tomography. 3D-APT results show at the atomic scale the characteristic of the structure. In the annealing conditions investigated here, i.e. 900°C, our results show an incomplete phase separation between Si and SiO 2 . This is evidenced by a Si supersaturation in the SRSO layers and a large scale distribution size of the Si-nc.

  . A schematic representation of this case is shown on Figure 1.(b).

Figure 1 :

 1 Figure 1 : (a) High-Resolution TEM image of the SRSO (3.8nm) / SiO 2 (4nm) multilayers. Crystallized silicon nanoclusters can be seen (circle and magnified image); (b) Schematic drawing of the MLs configuration in the case of a complete phase separation between Si and SiO 2 phases.

Figure 2 :

 2 Figure 2 : (a) 3D reconstruction of SRSO/SiO 2 ML's analysed by LA-WATAP (arrows and dashed-line indicate rich Si regions). The volume is 13× × × ×13× × × ×51 nm 3 . (b) Composition profile along the multilayer.

Figure 3 .

 3 Figure 3.(a) shows a 3D iso-concentration surface image of the multilayers which reveals the presence of Si-nc (red-zones) embedded in silica regions (green-zones). This image clearly evidenced the expected uniform distribution of Si-nc in the SRSO sublayers alternatively with pure silica sublayers after a 1h-annealing at 900°C. Data treatment of the 3D-APT analyses allow us to investigate independently, at the atomic scale, each nano-cluster or the matrix (excluding Si-nc). First, the composition of the SRSO matrix (measured after subtraction of the Si-nc cluster), which corresponds to the decomposition of the surrounding Si-nc, has been obtained. The measured SRSO matrix composition is X Si matrix ≈ 41.9 ± 0.3% and X O matrix ≈ 58.1 ± 0.3%, which is significantly higher than pure silica phase (X Si =33.3% and X O =66.7%) and indicating an incomplete phase separation. The Si excess remaining in the SRSO sublayers after 1hannealing at 900°C is ~13%, i.e. only ~50% of the Si excess has precipitated. The annealing conditions (1h at 900°C) are not long enough to ensure a complete phase separation of the system. These results confirm the slow phase separation process at this temperature as suggested by Iacona et al.[14].

Figure 3 :

 3 Figure 3 : (a) 3D iso-concentration of the SRSO/SiO2 ML's (red zones indicate Si-nc and green zones indicate silica). (b) Measured and theoretical size distribution of the Si-nc diameter in the SRSO layers.

ACKNOWLEDGMENTS

This work was supported by the Upper Normandy Region and the French Ministry of Research in the framework of Research Networks of Upper-Normandy.