Journal of Automata, Languages and Combinatorics u (v) w, x–y \begin{matrix}c \\ ◯ \end{matrix} Otto-von-Guericke-Universität Magdeburg

ON THE LENGTH OF THE WADGE HIERARCHY OF ω-CONTEXT-FREE LANGUAGES^{1}

Olivier Finkel Equipe de Logique Mathématique, U.F.R. de Mathématiques, Université Paris 7 2 Place Jussieu 75251 Paris cedex 05, France.

                       e-mail: finkel@logique.jussieu.fr

ABSTRACT We prove in this paper that the length of the Wadge hierarchy of ω-context-free languages is greater than the Cantor ordinal ε_{ω}, which is the ω^{th} fixed point of the ordinal exponentiation of base ω. We show also that there exist some Σ_{ω}^{0}-complete ω-context-free languages, improving previous results on ω-context-free languages and the Borel hierarchy. Keywords: ω-context-free languages; infinitary context-free languages; topological properties; Borel hierarchy; Wadge hierarchy; conciliating Wadge hierarchy.

1. Introduction

In the sixties Büchi studied the ω-languages accepted by finite automata to prove the decidability of the monadic second order theory of one successor over the integers. Since then the so called ω-regular languages have been intensively studied, see [Tho90, PP04] for many results and references. The extension to ω-languages accepted by pushdown automata has also been investigated, firstly by Cohen and Gold, Linna, Nivat, see Staiger’s paper [Sta97] for a survey of this work, including acceptance of infinite words by more powerful accepting devices, like Turing machines. A way to investigate the complexity of ω-languages is to consider their topological complexity. Mc Naugthon’s Theorem implies that ω-regular languages are boolean combinations of Π_{2}^{0}-sets. We proved that ω-context-free languages (accepted by pushdown automata with a Büchi or Muller acceptance condition) exhaust the finite ranks of the Borel hierarchy, [Fin01a], that there exist some ω-context-free languages (ω-CFL) which are analytic but non Borel sets, [Fin03a], and that there exist also some ω-CFL which are Borel sets of infinite rank, [Fin03b]. On the other hand the Wadge hierarchy of Borel sets is a great refinement of the Borel hierarchy and it induces on ω-regular languages the now called Wagner hierarchy which has been determined by Wagner in an effective way [Wag79]. Its length is the ordinal ω^{ω}. Notice that Wagner originally determined this hierarchy without citing links with the Wadge hierarchy. The applicability of the Wadge hierarchy to the Wagner hierarchy was established by Selivanov in [Sel94, Sel95]. The Wadge hierarchy of deterministic ω-context-free languages has been recently determined by Duparc: its length is the ordinal ω^{(ω^{2})}, [Dup03]. We proved in [Fin01b] that the length of the Wadge hierarchy of (non deterministic) ω-context-free languages is an ordinal greater than or equal to the first fixed point of the ordinal exponentiation of base ω, the Cantor ordinal ε_{0}. We improve here this result and show that the length of the Wadge hierarchy of ωcontext-free languages is an ordinal strictly greater than the ω^{th} fixed point of the ordinal exponentiation of base ω, the ordinal ε_{ω}. In order to get our results, we use recent results of Duparc. In [Dup01, Dup95a] he gave a normal form of Borel Δ_{ω}^{0}-sets, i.e. an inductive construction of a Borel set of every given degree in the Wadge hierarchy of Δ_{ω}^{0}-Borel sets. In the course of the proof he studied the conciliating hierarchy which is a hierarchy of sets of finite and infinite sequences, closely connected to the Wadge hierarchy of non self dual sets. On the other hand the infinitary languages, i.e. languages containing finite and infinite words, accepted by pushdown automata have been studied in [Bea84a, Bea84b] where Beauquier considered these languages as process behaviours which may or may not terminate, as for transition systems studied in [AN82]. We study the conciliating hierarchy of infinitary context-free languages, considering various operations over conciliating sets and their counterpart: arithmetical operations over Wadge degrees. On the other hand we show that there exists some Σ_{ω}^{0}-complete ω-context-free language, using results of descriptive set theory on sets of ω^{2}-words and a coding of ω^{2}-words by ω-words. The paper is organized as follows. In section 2 we recall some above definitions and results about ω-languages accepted by Büchi or Muller pushdown automata. In section 3 Borel and Wadge hierarchies are introduced. In section 4 we show that the class of infinitary context-free languages is closed under various operations and we study the effect of these operations on the Wadge degrees. In section 5 we prove our main result on the length of the Wadge hierarchy of ω-context-free languages. In section 6 we construct some Σ_{ω}^{0}-complete ω-context free language.

1A short version of this paper appeared in the Proceedings of the International Workshop on Logic and Complexity in Computer Science held in honour of Anatol Slissenko for his 60^{th} birthday, Créteil, France, 2001, [Fin01d]

2. ω-Regular and ω-Context-Free Languages

On the length of the Wadge hierarchy of ω-context free languages 3

We assume the reader to be familiar with the theory of formal languages and of ωregular 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 every 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 ⊑: the finite word u is a prefix of the finite word v (respectively, the 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 Σ^{ω}. For V ⊆ Σ^{⋆}, the ω-power of V is the ω-language: V^{ω} = {σ = u_{1} … u_{n} … ∈ Σ^{ω} | ∀i ≥ 1 u_{i} ∈ V − {λ}}. For any family L of finitary languages, the ω-Kleene closure of L, is : ω − KC(L) = {∪_{i=1}^{n}U_{i}.V_{i}^{ω} | ∀i ∈ [1, n] U_{i}, V_{i} ∈ L}. For V ⊆ Σ^{⋆}, the complement of V (in Σ^{⋆}) is Σ^{⋆} − V denoted V^{−}. For a subset A ⊆ Σ^{ω}, the complement of A is Σ^{ω} − A denoted A^{−}. When we consider subsets of Σ^{≤ω} = Σ^{⋆} ∪ Σ^{ω}, if A ⊆ Σ^{≤ω} then A^{−} = Σ^{≤ω} − A, (this will be clear from the context so that there will not be any confusion even if A ⊆ Σ^{⋆} or A ⊆ Σ^{ω}). Recall that the class REG_{ω} of ω-regular languages is the class of ω-languages accepted by non-deterministic finite automata with a Büchi or Muller acceptance condition. It is also the ω-Kleene closure of the class REG of regular finitary languages. Similarly the class CF L_{ω} of ω-context-free languages (ω-CFL) is the class of ωlanguages accepted by non-deterministic pushdown automata with a Büchi or Muller acceptance condition. It is also the ω-Kleene closure of the class CF L of context-free finitary languages, [CG77, Sta97]. Let Σ be a finite alphabet. A subset L of Σ^{≤ω} is said to be an infinitary contextfree language iff there exists a finitary context-free language L_{1} ⊆ Σ^{⋆} and an ω-CFL L_{2} ⊆ Σ^{ω} such that L = L_{1} ∪ L_{2}. The class of infinitary context-free languages will be denoted CF L_{≤ω}.

3. Borel and Wadge Hierarchies

We assume the reader to be familiar with basic notions of topology which may be found in [Mos80, Kec95, LT94, Sta97, PP04] and with the elementary theory of ordinals, including the operations of multiplication and exponentiation, which may be found in [Sie65]. For a finite alphabet X, we consider X^{ω} as a topological space with the Cantor topology. The open sets of X^{ω} are the sets 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 on X^{ω}:

Definition 3.1 For a non-null countable ordinal α, the classes Σ_{α}^{0} and Π_{α}^{0} of the Borel Hierarchy on the topological space X^{ω} are defined as follows: Σ_{1}^{0} is the class of open subsets of X^{ω}. Π_{1}^{0} 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}.

Notice that the above definition of Borel classes Σ_{α}^{0} and Π_{α}^{0}, for a limit ordinal α, is the usual one in descriptive set theory, as given in the textbooks [Mos80, Kec95]. In particular, the class Σ_{ω}^{0} is not the union of the classes Σ_{n}^{0} for integers n ≥ 1 but it strictly contains ∪_{n≥1}Σ_{n}^{0} = ∪_{n≥1}Π_{n}^{0} consisting of Borel sets of finite rank. Moreover classes Σ_{ω}^{0} and Π_{ω}^{0} are distinct and are incomparable for the inclusion relation. We shall say that a subset of X^{ω} is a Borel set of rank α, for a countable ordinal α, iff it is in Σ_{α}^{0} ∪ Π_{α}^{0} but not in ⋃_{γ<α}(Σ_{γ}^{0} ∪ Π_{γ}^{0}). In particular a Borel set has Borel rank ω iff it is in (Σ_{ω}^{0} ∪ Π_{ω}^{0}) but is not a Borel set of finite rank. Introduce now the Wadge Hierarchy which is in fact a huge refinement of the Borel hierarchy:

Definition 3.2 (Wadge [Wad84]) Let X, Y be two finite alphabets. For E ⊆ X^{ω} and F ⊆ Y^{ω}, E is said to be Wadge reducible to F (E ≤_{W} F) iff there exists a continuous function f : X^{ω} → Y^{ω}, such that E = f^{−1}(F). E and F are Wadge equivalent iff E ≤_{W} F and F ≤_{W} E. This will be denoted by E ≡_{W} F. And we shall say that E <_{W} F iff E ≤_{W} F but not F ≤_{W} E. A set E ⊆ X^{ω} is said to be self dual iff E ≡_{W} E^{−}, 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. W H is the class of Borel subsets of a set X^{ω}, where X is a finite set, equipped with ≤_{W} and with ≡_{W}. Remark that in the above definition, we consider that a subset E ⊆ X^{ω} is given together with the alphabet X. We can now define the Wadge class of a set F:

Definition 3.3 Let F be a subset of X^{ω}. The Wadge class of F is [F] defined by:

[F] = {E | E ⊆ Y^{ω} for a finite alphabet Y and E ≤_{W} F }.

Recall that each Borel class Σ_{α}^{0} and Π_{α}^{0} is a Wadge class. And that a set F ⊆ X^{ω} is a Σ_{α}^{0} (respectively Π_{α}^{0})-complete set iff for any set E ⊆ Y^{ω}, E is in Σ_{α}^{0} (respectively Π_{α}^{0}) iff E ≤_{W} F.

Theorem 3.4 (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_{W}^{0} from W H onto |W H| − {0}, such that for all A, B ∈ W H: d_{W}^{0} A < d_{W}^{0} B ↔ A <_{W} B and d_{W}^{0} A = d_{W}^{0} B ↔ [A ≡_{W} B or A ≡_{W} B^{−}].

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} = ω_{1}^{α_{n}} 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 ω_{1}^{th} 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 ω_{1}^{th} fixed point of the ordinal exponentiation of base ω_{1}. It is described in [Wad84, Dup01] by the use of the Veblen functions. There is an effective version of the Wadge hierarchy restricted to ω-regular languages:

Theorem 3.5 For A and B some ω-regular sets, one can effectively decide whether A ≤_{W} B and one can compute d_{W}^{0} (A).

The hierarchy obtained on ω-regular languages is now called the Wagner hierarchy and has length ω^{ω}. Wagner [Wag79] gave an automata structure characterization, based on notion of chain and superchain, for an automaton to be in a given class and then he got an algorithm to compute the Wadge degree of an ω-regular language. Wilke and Yoo proved in [WY95] that one can compute in polynomial time the Wadge degree of an ω-regular language. There is an effective extension of the Wagner hierarchy: the Wadge hierarchy of ω-languages accepted by Muller deterministic one blind (i. e. without zero-test) counter automata [Fin01c]. This hierarchy has an extension to deterministic ω-context-free languages as well as to deterministic Petri net ω-languages which has length ω^{(ω^{2})} [DFR01, Dup03, Fin01e] but we do not know yet whether these extensions are decidable. The Wadge hierarchy of ω-languages accepted by deterministic Turing machines has been very recently determined by Selivanov: its length is the ordinal (ω_{1}^{CK})^{ω}, where ω_{1}^{CK} is the first non-recursive ordinal, [Sel03a, Sel03b]. The Wadge hierarchy restricted to (non deterministic) ω-CFL is not effective: we have shown in [Fin01a, Fin01b, Fin03a] that one can neither decide the Borel rank nor the Wadge degree of a Borel ω-CFL. In fact one cannot even decide whether an ω-CFL is a Borel set.

4. Operations on Conciliating Sets

4.1. Conciliating Sets

We sometimes consider here subsets of X^{⋆} ∪ X^{ω} = X^{≤ω}, for an alphabet X, which are called conciliating sets in [Dup01, Dup95a].

Definition 4.1 Let X be a finite or countably infinite alphabet. A conciliating set over the alphabet X is a subset of the set X^{≤ω} = X^{⋆} ∪ X^{ω} of finite or infinite words over X.

Remark 4.2 We shall only consider in the sequel conciliating sets defined over a finite alphabet, except that we shall state Definition 4.20 and Proposition 4.21 in a more general case.

In order to give a “normal form” of Borel sets in the Wadge hierarchy, J. Duparc studied the conciliating (Wadge) hierarchy which is a hierarchy over conciliating sets closely related to the Wadge hierarchy. Recall the definition of the conciliating Wadge game:

Definition 4.3 ([Dup01]) Let X_{A}, X_{B} be two finite alphabets. For A ⊆ X_{A}^{≤ω} and B ⊆ X_{B}^{≤ω}, the conciliating Wadge game C(A, B) is a game with perfect information between two players, player 1 who is in charge of A and player 2 who is in charge of B. Player 1 first writes a letter a_{1} ∈ X_{A}, then the two players alternatively write letters a_{n} of X_{A} for player 1 and b_{n} of X_{B} for player 2. Both players are allowed to skip even indefinitely if they want to. Then after ω steps, the player 1 has written a (finite or infinite) word x ∈ X_{A}^{≤ω} and the player 2 has written a (finite or infinite) word y ∈ X_{B}^{≤ω}. Player 2 wins the play iff [x ∈ A ↔ y ∈ B], i.e. iff [(x ∈ A and y ∈ B) or (x ∉ A and y ∉ B)], otherwise player 1 wins.

A strategy for player 1 is a function σ : (X_{B} ∪ {s})^{⋆} → (X_{A} ∪ {s}). And a strategy for player 2 is a function f : (X_{A} ∪ {s})^{+} → X_{B} ∪ {s} (s for “skip”). A strategy σ is a winning strategy (w.s.) for player 1 iff he always wins a play when he uses the strategy σ, i.e. when he writes at step n the letter a_{n} = σ(b_{1}...b_{n−1}) if a_{n} ≠ s and he skips at step n if s = σ(b_{1}...b_{n−1}). A winning strategy for player 2 is defined in a similar manner. Without loss of generality we can consider that players are allowed to write a finite word instead of a single letter at each step of a play [Dup01].

Definition 4.4 For A ⊆ X_{A}^{≤ω} and B ⊆ X_{B}^{≤ω}, A ≤_{c} B iff player 2 has a winning strategy in C(A, B). Then A <_{c} B iff A ≤_{c} B but not conversely and A ≡_{c} B iff A ≤_{c} B ≤_{c} A.

It turned out that in the conciliating Wadge hierarchy every conciliating set is non self dual. The Wadge hierarchy and the conciliating Wadge hierarchy are connected via the following correspondence: first define A^{d} for A ⊆ Σ^{≤ω} and d a letter not in Σ by : A^{d} = {x ∈ (Σ ∪ {d})^{ω} | x(/d) ∈ A}, where x(/d) is the sequence obtained from x when removing every occurrence of the letter d. Then for A ⊆ Σ^{≤ω} such that A^{d} is a Borel set, (we shall say in that case that A is a Borel conciliating set), A^{d} is always a non self dual subset of (Σ ∪ {d})^{ω} and the correspondence A → A^{d} induces an isomorphism between the conciliating hierarchy and the Wadge hierarchy of non self dual Borel sets. This is due to the fact that for two conciliating sets A and B, A ≤_{c} B iff A^{d} ≤_{W} B^{d}. Martin’s Theorem states that Borel Gale-Stewart games are determined: in such infinite games one of the two players has a winning strategy, see [Kec95]. This implies the following result.

Theorem 4.5 Let X_{A}, X_{B} be two finite alphabets and A ⊆ X_{A}^{≤ω}, B ⊆ X_{B}^{≤ω} be such that A^{d} and B^{d} are Borel sets. Then the conciliating Wadge game C(A, B) is determined: one of the two players has a winning strategy.

From now on we shall first concentrate on non self dual sets as in [Dup01] and we shall use the following definition of the Wadge degrees which is a slight modification of the previous one:

Definition 4.6

(a) d_{w}(∅) = d_{w}(∅^{−}) = 1

(b) d_{w}(A) = sup{d_{w}(B) + 1 | B non self dual and B <_{W} A} (for either A self dual or not, A >_{W} ∅).

Recall the definition of the conciliating degree of a conciliating set:

Definition 4.7 Let A ⊆ Σ^{≤ω} be a conciliating set over the alphabet Σ such that A^{d} is a Borel set. The conciliating degree of A is d_{c}(A) = d_{w}(A^{d}).

We recall now some properties of the correspondence A → A^{d} when context-free languages are considered:

Proposition 4.8 ([Fin01a]) a) If A ⊆ Σ^{⋆} is a context-free (finitary) language, or if A ⊆ Σ^{ω} is an ω-CFL, then A^{d} is an ω-CFL.

b) If A is the union of a finitary context-free language and of an ω-CFL over the same alphabet Σ, then A^{d} is an ω-CFL over the alphabet Σ ∪ {d}.

We are going now to introduce several operations over conciliating sets: the operation of sum, of exponentiation and of iterated exponentiation. And we shall study their counterpart which are ordinal arithmetical operations over Wadge degrees.

4.2. Operation of Sum

Definition 4.9 ([Dup01]) Assume that X_{A} ⊆ X_{B} are two finite alphabets, X_{B}−X_{A} containing at least two elements, and that {X_{+}, X_{−}} is a partition of X_{B} − X_{A} in two non empty sets. Let A ⊆ X_{A}^{≤ω} and B ⊆ X_{B}^{≤ω}, then

B + A =_{df} A ∪ {u.a.β | u ∈ X_{A}^{⋆}, (a ∈ X_{+} and β ∈ B) or (a ∈ X_{−} and β ∈ B^{−})}

This operation is closely related to the ordinal sum as it is stated in the following:

Theorem 4.10 ([Dup01]) Let X_{A} ⊆ X_{B}, X_{B} − X_{A} containing at least two elements, A ⊆ X_{A}^{≤ω} and B ⊆ X_{B}^{≤ω} such that A^{d} and B^{d} are Borel sets. Then (B + A)^{d} is a Borel set and d_{c}(B + A) = d_{c}(B) + d_{c}(A).

Remark 4.11 As indicated in Remark 5 of [Dup01], when A ⊆ Σ^{≤ω} and X is a finite alphabet, it is easy to build A′ ⊆ (Σ ∪ X)^{≤ω}, such that (A′)^{d} ≡_{W} A^{d}. In fact A′ can be defined as follows: for σ ∈ (Σ ∪ X)^{≤ω}, let σ ∈ A′ ↔ σ′ ∈ A, where σ′ is σ except that each letter not in Σ is removed. Then in the sequel we assume that each alphabet is as enriched as desired, and in particular we can always define B + A (or in fact another set C such that C^{d} ≡_{W} (B + A)^{d}).

Consider now conciliating sets which are union of a finitary CFL and of an ω-CFL.

Proposition 4.12 ([Fin01b]) Let X_{A} ⊆ X_{B} such that {X_{+}, X_{−}} is a partition of X_{B} − X_{A} in two non empty sets. Assume A ⊆ X_{A}^{≤ω}, A, A^{−} ∈ CF L_{≤ω}, B ⊆ X_{B}^{≤ω} and B, B^{−} ∈ CF L_{≤ω}. Then B + A and (B + A)^{−} are in CF L_{≤ω}.

Definition 4.13 Let A ⊆ X_{A}^{≤ω} be a conciliating set over the alphabet X_{A}. Then A.n is inductively defined by A.1 = A and A.(n + 1) = (A.n) + A, for each integer n ≥ 1.

4.3. Operation of Exponentiation

We are going now to introduce the operation of exponentiation of conciliating sets which was firstly defined by Duparc in his study of the Wadge hierarchy [Dup01].

Definition 4.14 (Duparc [Dup01]) Let Σ be a finite alphabet and ↞∉ Σ, let X = Σ ∪ {↞}. Let x be a finite or infinite word over the alphabet X = Σ ∪ {↞}. Then x^{↞} is inductively defined by: λ^{↞} = λ, and for a finite word u ∈ (Σ ∪ {↞})^{⋆}: (u.a)^{↞} = u^{↞}.a, if a ∈ Σ, (u. ↞)^{↞} = u^{↞} with its last letter removed if |u^{↞}| > 0, i.e. (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 Σ^{⋆}, 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 4.15 For x ∈ X^{≤ω}, x^{↞} denotes the string x, once every ↞ occuring in x has been “evaluated” to the back space operation ( the one familiar to your computer!), proceeding from left to right inside x. In other words x^{↞} = x from which every interval of the form “a ↞ ” (a ∈ Σ) 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 4.14 the limit is not defined in the usual way: 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 4.14 implies that lim_{n∈ω}(u[n])^{↞} = b so u^{↞} = b. We can now define the operation A → A^{∼} of exponentiation of conciliating sets:

Definition 4.16 (Duparc [Dup01]) For A ⊆ Σ^{≤ω} and ↞ ∉ Σ, let X = Σ ∪ {↞} and A^{∼} =_{df} {x ∈ (Σ ∪ {↞})^{≤ω} | x^{↞} ∈ A}.

The operation ∼ is monotone with regard to the Wadge ordering and produce some sets of higher complexity, as we shall see below. We shall need the notion of cofinality of an ordinal which may be found in [Sie65, CK73] and which we briefly recall now.

Definition 4.17 Let α be a limit ordinal, the cofinality of α, denoted cof(α), is the least ordinal β such that there exists a strictly increasing sequence of ordinals (α_{i})_{i<β}, of length β, such that for all i < β, α_{i} < α, and sup_{i<β} α_{i} = α. This definition is usually extended to 0 and to the successor ordinals: cof(0) = 0 and cof(α + 1) = 1 for every ordinal α.

The cofinality of a limit ordinal is always a limit ordinal satisfying: ω ≤ cof(α) ≤ α. The ordinal cof(α) is in fact a cardinal [CK73]. Then if the cofinality of a limit ordinal α is ≤ ω_{1}, only the following cases may happen: cof(α) = ω or cof(α) = ω_{1}. In this paper we shall not have to consider cofinalities which are larger than ω_{1}.

We can now state that the operation of exponentiation of conciliating sets is closely related to ordinal exponentiation of base ω_{1}:

Theorem 4.18 (Duparc [Dup01]) Let A ⊆ Σ^{≤ω} be a conciliating set such that A^{d} is a Δ_{ω}^{0}-Borel set and d_{c}(A) = d_{w}(A^{d}) = α + n with α a limit ordinal and n an integer ≥ 0. Then (A^{∼})^{d} is a Δ_{ω}^{0}-Borel set and there are three cases:

a) If α = 0, then d_{c}(A^{∼}) = (ω_{1})^{d_{c}(A)−1}

b) If α has cofinality ω, then d_{c}(A^{∼}) = (ω_{1})^{d_{c}(A)+1}

c) If α has cofinality ω_{1}, then d_{c}(A^{∼}) = (ω_{1})^{d_{c}(A)}

Consider now this operation A → A^{∼} over infinitary context-free languages.

Theorem 4.19 ([Fin01a, Fin01b]) Whenever A ⊆ Σ^{ω} (respectively, A ⊆ Σ^{≤ω}) is in CF L_{ω}, (respectively, in CF L_{≤ω}), then A^{∼} is in CF L_{ω}, (respectively, in CF L_{≤ω}). And A, A^{−} ∈ CF L_{≤ω} implies that A^{∼}, (A^{∼})^{−} = (A^{−})^{∼} ∈ CF L_{≤ω}

4.4. Operation of Iterated Exponentiation

In this section we are going to define a new operation A → A^{•} which can be called iterated exponentiation. It will involve an infinite number of erasers so each eraser will be coded over a fixed finite alphabet and we shall see how a pushdown automaton will be able to guess, in a non deterministic way, that the erasing operations are correctly achieved in an input word. One can already iterate the operation of exponentiation of sets. We shall use, in order to simplify our proofs, a variant A^{≈} of A^{∼} we already introduced in [Fin01a, Fin03b]. A^{≈} is defined as A^{∼} with the only difference that in the definition 4.14, we write: (u. ↞)^{↞} is undefined if |u^{↞}| = 0, instead of (u. ↞)^{↞} = λ if |u^{↞}| = 0. Then one can show, as in [Fin01a], that if A ⊆ Σ^{≤ω} and d_{c}(A) ≥ 2 (hence A^{−} ≠ ∅), then A^{∼} and A^{≈} are (conciliating) Wadge equivalent. We define now, for a set A ⊆ Σ^{≤ω}: A^{≈.0} = A, A^{≈.1} = A^{≈} and A^{≈.(k+1)} = (A^{≈.k})^{≈}, where we apply k +1 times the operation A → A^{≈} with different new letters ↞_{1}, ↞_{2}, ↞_{3}, …, ↞_{k+1}. But this way, from a Borel conciliating set of finite rank, we obtain only (conciliating) Borel sets of finite ranks, of Wadge degree <^{1} ε_{0}. A way to get sets of higher degrees, is to use the supremum of the sets A^{≈.i}. More generally we set the following definition.

Definition 4.20 Let Σ be a finite or countably infinite alphabet containing at least two letters a and b and let (A_{i})_{i∈ℕ} be a family of subsets of Σ^{≤ω}. Then sup_{i∈ℕ} A_{i} =_{df} ⋃_{i∈ℕ} a^{i}.b.A_{i}.

Let us recall now the following result. Notice that we give it in the general case of a countable (and possibly infinite) alphabet although we have only defined the conciliating Wadge hierarchy for conciliating sets defined over a finite alphabet (in order to simplify the presentation). In fact the following proposition will only be used later in the case of a finite alphabet Σ, but we state it here (without details) in a more general case in order to give an indication of what we could obtain (all the A^{≈.i} are defined over the same infinite alphabet Σ ∪ {↞_{1}, ↞_{2}, … ↞_{k} …}).

Proposition 4.21 ([Dup01]) Let Σ be a finite or countably infinite alphabet containing at least two letters a and b and let (A_{i})_{i∈ℕ} be a family of subsets of Σ^{≤ω} with (A_{i})^{d} Borel. Assume moreover that ∀i ∈ ℕ ∃j_{i} ∈ ℕ such that d_{c}(A_{i}) < d_{c}(A_{j_{i}}). Then (sup_{i∈ℕ} A_{i})^{d} is Borel and d_{c}(sup_{i∈ℕ} A_{i}) = sup_{i∈ℕ} d_{c}(A_{i}).

Let us return now to the case of the supremum sup_{i∈ℕ} A^{≈.i} = ⋃_{i∈ℕ} a^{i}.b.A^{≈.i} of the sets A^{≈.i}. It is defined over an infinite alphabet, and any infinitary context-free language is defined over a finite alphabet. So we have first to code this set over a finite alphabet. The conciliating set A^{≈.n} is defined over the alphabet Σ ∪ {↞_{1}, …, ↞_{n}} hence we have to code every eraser ↞_{j} by a finite word over a fixed finite alphabet. We shall code the eraser ↞_{j} by the finite word α.B^{j}.C^{j}.D^{j}.E^{j}.β over the alphabet {α, B, C, D, E, β}. We shall construct below a pushdown automaton accepting an infinitary language close to the coding of sup_{i∈ℕ} A^{≈.i}, for A ∈ CF L_{≤ω}. It will need to read four times the integer j characterizing the eraser ↞_{j} and this justifies our coding of the erasers. Remark first that the morphism: F_{n} : (Σ ∪ {↞_{1}, …, ↞_{n}})^{⋆} → (Σ ∪ {α, β, B, C, D, E})^{⋆} defined by F_{n}(c) = c for each c ∈ Σ and F_{n}(↞_{j}) = α.B^{j}.C^{j}.D^{j}.E^{j}.β for each integer j ∈ [1, n], where B, C, D, E, α, β are new letters not in Σ, can be naturally extended to a function: F̄_{n} : (Σ ∪ {↞_{1}, …, ↞_{n}})^{≤ω} → (Σ ∪ {α, β, B, C, D, E})^{≤ω}. Using Wadge games, we can now state the following lemma, (but no proof is given here).

Lemma 4.22 Let A ⊆ Σ^{≤ω} be such that A^{d} is a Δ_{ω}^{0}-Borel set and d_{c}(A) ≥ 2. Then d_{c}(F̄_{n}(A^{≈.n})) = d_{c}(A^{≈.n}) holds for every integer n ≥ 2. If moreover, ∀n ≥ 1, d_{c}(A^{≈.n}) < d_{c}(A^{≈.(n+1)}) then d_{c}(sup_{i≥1} F̄_{i}(A^{≈.i})) = sup_{i≥1} d_{c}(A^{≈.i}).

We would like now to apply the above lemma to construct, from an infinitary contextfree language A such that A^{d} is a Δ_{ω}^{0}-Borel set and d_{c}(A) ≥ 2, another infinitary context-free language of Wadge degree sup_{i≥1} d_{c}(A^{≈.i}). But we can not show that, whenever A ∈ CF L_{≤ω}, then sup_{n≥1} F̄_{n}(A^{≈.n}) is in CF L_{≤ω}. This is connected to the fact that the finitary language {B^{j}C^{j}D^{j}E^{j} | j ≥ 1} is not a context-free language. But its complement is easily seen to be context-free. Then we shall sligthly modify the set sup_{n≥1} F̄_{n}(A^{≈.n}), in the following way. We can add to this language all (≤ ω)-words in the form a^{n}.b.u where there is in u a segment α.B^{j}.C^{k}.D^{l}.E^{m}.β, with j, k, l, m integers ≥ 1, which does not code any eraser, or codes an eraser ↞_{j} for j > n. Define first the following context-free finitary languages over the alphabet X^{□} = (Σ ∪ {α, β, B, C, D, E}) : L^{B} = {a^{n}.b.u.B^{j} | n ≥ 1 and j > n and u ∈ (X^{□})^{⋆}} L^{C} = {a^{n}.b.u.C^{j} | n ≥ 1 and j > n and u ∈ (X^{□})^{⋆}} L^{D} = {a^{n}.b.u.D^{j} | n ≥ 1 and j > n and u ∈ (X^{□})^{⋆}} L^{E} = {a^{n}.b.u.E^{j} | n ≥ 1 and j > n and u ∈ (X^{□})^{⋆}} L^{(B,C)} = {u.α.B^{j}.C^{k}.D^{l}.E^{m}.β | j, k, l, m ≥ 1 and j ≠ k and u ∈ a^{+}.b.(X^{□})^{⋆}} L^{(C,D)} = {u.α.B^{j}.C^{k}.D^{l}.E^{m}.β | j, k, l, m ≥ 1 and k ≠ l and u ∈ a^{+}.b.(X^{□})^{⋆}} L^{(D,E)} = {u.α.B^{j}.C^{k}.D^{l}.E^{m}.β | j, k, l, m ≥ 1 and l ≠ m and u ∈ a^{+}.b.(X^{□})^{⋆}} It is easy to show that each of these languages is a context free finitary language thus L = L^{B} ∪ L^{C} ∪ L^{D} ∪ L^{E} ∪ L^{(B,C)} ∪ L^{(C,D)} ∪ L^{(D,E)} is also context-free because the class CFL is closed under finite union. Then L.(X^{□})^{≤ω} is an infinitary CFL. Remark that all words in sup_{n≥1} F̄_{n}(A^{≈.n}) belong to the infinitary regular language R = a^{+}.b.(Σ ∪ (α.B^{+}.C^{+}.D^{+}.E^{+}.β))^{≤ω}. Consider now the language L.(X^{□})^{≤ω} ∩ R. A word σ in this language is a word in R, having an initial segment in the form a^{n}.b, with n ≥ 1, and containing a segment α.B^{j}.C^{k}.d^{l}.E^{m}.β with j, k, l, m ≥ 1 which does not code any eraser ↞_{i} or codes such an eraser but with i > n. Define now

A^{•} = sup_{n≥1} F̄_{n}(A^{≈.n}) ∪ [L.(X^{□})^{≤ω} ∩ R]

We shall show that the operation A → A^{•} conserves the context-freeness of infinitary languages and that if A is a Δ_{ω}^{0}-set of Wadge degree ≥ 2 then A^{•} and sup_{n≥1} F̄_{n}(A^{≈.n}) are Wadge equivalent. So we shall be able to construct, from such an infinitary context-free language A, another infinitary context-free language of Wadge degree sup_{i≥1} d_{c}(A^{≈.i}).

Theorem 4.23 If A ⊆ Σ^{≤ω} is an infinitary context-free language then A^{•} is an infinitary context-free language over the alphabet X^{□} = (Σ ∪ {α, β, B, C, D, E}).

Proof. It relies on a technical construction of a pushdown automaton accepting A^{•} from a pushdown automaton accepting A. The idea of the construction is already in [Fin03b], where A was assumed to be an ω-regular language and where we proved only the existence of some ω-context-free languages which are Borel sets of infinite rank. We shall give here a similar construction in the more general case of an infinitary context-free language A. Let then A ⊆ Σ^{≤ω} be an infinitary context-free language (A may contain finite and infinite words). We can write A = A_{1} ∪ A_{2} where A_{1} ⊆ Σ^{ω} is an ω-CFL and A_{2} ⊆ Σ^{⋆} is a finitary context-free language. Then A^{•} = A_{1}^{•} ∪ A_{2}^{•} holds by definition of A^{•}. The ω-language A_{1} ⊆ Σ^{ω} is accepted by a Muller pushdown automaton A_{1}. Remark that in that case all sets A_{1}^{≈.n} as well as sup_{n≥1} F̄_{n}(A_{1}^{≈.n}) contain only infinite words.

We shall find a MPDA B accepting an ω-CFL L(B) such that

sup_{n≥1} F̄_{n}(A_{1}^{≈.n}) ⊆ L(B) ⊆ A_{1}^{•} = sup_{n≥1} F̄_{n}(A_{1}^{≈.n}) ∪ [L.(X^{□})^{≤ω} ∩ R]

Thus we shall have A_{1}^{•} = L(B) ∪ [L.(X^{□})^{≤ω} ∩ R] and this will imply that A_{1}^{•} is in CF L_{≤ω} because the class CF L_{≤ω} is closed under finite union. It is easy to have L(B) ⊆ R because if L(B′) is an ω-CFL which is not included into R one can replace it by L(B) = L(B′) ∩ R which is then an ω-CFL such that L(B) = L(B′) ∩ R ⊆ R. Recall now that L.(X^{□})^{≤ω} ∩ R is the set of all (finite or infinite) words in R but not in ∪_{n≥1}a^{n}.b.F̄_{n}(Σ ∪ {↞_{1}, …, ↞_{n}})^{≤ω}. Thus, in order to define the MPDA B, we have only to consider the behaviour of B when reading ω-words in ∪_{n≥1}a^{n}.b.F̄_{n}(Σ ∪ {↞_{1}, …, ↞_{n}})^{ω} and we have to find a MPDA B such that L(B) contains such a word a^{n}.b.u if and only if u ∈ F̄_{n}(A_{1}^{≈.n}).

So we have to look first at ω-words in F̄_{n}(A_{1}^{≈.n}). In such a word u ∈ F̄_{n}(A_{1}^{≈.n}), there are (codes of) erasers ↞_{1}, …, ↞_{n}. In order to simplify our notations, we shall sometimes write in the sequel ↞_{j}= α.B^{j}.C^{j}.D^{j}.E^{j}.β and call eraser either ↞_{j} or its code α.B^{j}.C^{j}.D^{j}.E^{j}.β. The ω-word u is in F̄_{n}(A_{1}^{≈.n}) if and only if after the operations of erasing ( with the erasers ↞_{1}, ..., ↞_{n} ) have been achieved in u, then the resulting word is in A_{1}. Because of the inductive definition of the sets A_{1}^{≈.n}, the operations of erasing have to be done in a good order: in an ω-word which contains only the erasers ↞_{1}, ..., ↞_{n}, the first operation of erasing uses the last eraser ↞_{n}, then the second one uses the eraser ↞_{n−1}, and so on … We now informally describe the behaviour of the MPDA B when reading an ω-word a^{n}.b.u with u ∈ F̄_{n}(Σ ∪ {↞_{1}, …, ↞_{n}})^{ω}. The MPDA B will generalize the MPDA accepting A_{1}^{≈} constructed in [Fin01a]. After the reading of the initial segment in the form a^{n}.b, the MPDA B simulates the MPDA A_{1} until it guesses, using the non determinism, that it begins to read a segment w which contains erasers which really erase and some letters of Σ or some other erasers which are erased when the operations of erasing are achieved in u. Then, using the non determinism, when B reads a letter c ∈ Σ and guesses that this letter will be erased it pushes it in the pushdown store, keeping in memory the current global state (consisting in the stack content and the current state of the finite control) of the MPDA A_{1}. In a similar manner, when B reads the code ↞_{j}= α.B^{j}.C^{j}.D^{j}.E^{j}.β of an eraser and guesses that this eraser will be erased (by another eraser ↞_{k} with k > j), it pushes in the store the finite word γ.E^{j}.ε (coding the eraser ↞_{j} in the stack), where γ, ε are in the stack alphabet of B. But B may also guess that the eraser ↞_{j}= α.B^{j}.C^{j}.D^{j}.E^{j}.β will really be used as an eraser. In that case B has to pop from the top of the pushdown store either a letter c ∈ Σ or the code γ.E^{i}.ε of another eraser ↞_{i}, with i < j, which is erased by ↞_{j}. It would be easy for B to check whether i < j when reading the initial segment α.B^{j} of ↞_{j}.

The pushdown automaton B has also to ensure that the operations of erasing are achieved in a good order. This can be done, using our coding of erasers containing four times the integer j characterizing ↞_{j}. We refer to [Fin03b] where this behaviour of B is described. Consider now A_{2} ⊆ Σ^{⋆}. Then sup_{n≥1} F̄_{n}(A_{2}^{≈.n}) may contain finite and infinite words. Then sup_{n≥1} F̄_{n}(A_{2}^{≈.n}) = L_{1} ∪ L_{2} where L_{1} is a finitary language and L_{2} is an ωlanguage over the alphabet X^{□}. Following the same ideas as in the preceding case (where A_{1} ⊆ Σ^{ω}) we can construct a pushdown automaton B′ accepting a finitary context-free language L(B′) and a Muller pushdown automaton B′′ accepting an ω-CFL L(B′′) such that: L_{1} ⊆ L(B′) ⊆ L_{1} ∪ [L.(X^{□})^{≤ω} ∩ R], and L_{2} ⊆ L(B′′) ⊆ L_{2} ∪ [L.(X^{□})^{≤ω} ∩ R]. Then it turns out that A_{2}^{•} = L(B′) ∪ L(B′′) ∪ [L.(X^{□})^{≤ω} ∩ R] is in CF L_{≤ω}. Consider now again the infinitary context-free language A ⊆ Σ^{≤ω}. It turns out that A^{•} = A_{1}^{•} ∪A_{2}^{•} is an infinitary context-free language because the class CF L_{≤ω} is closed under finite union. □

The operation A → A^{•} provides a kind of infinite iteration of the operation A → A^{∼}. Thus the above theorem will enable us to get some infinitary context-free languages of larger Wadge degrees than those we could previously obtain.

In order to give precisely the Wadge degree of A^{•} from the Wadge degree of A we introduce now some notations for ordinals. For an ordinal α we define ω_{1}(1, α) = ω_{1}^{α} and for an integer n ≥ 1, ω_{1}(n + 1, α) = ω_{1}^{ω_{1}(n,α)}. If α ≤ ^{1}ε_{0} the limit of the sequence of ordinals ω_{1}(n, α) is the ordinal ^{1}ε_{0}. And if α > ^{1}ε_{0} the limit of the sequence of ordinals ω_{1}(n, α) is the first fixed point of the operation of ordinal exponentiation of base ω_{1} which is greater than (or equal to) α. We shall denote it ^{1}ε_{0}(α). Then one can enumerate the sequence of the ω first fixed points of the operation α → ω_{1}^{α}, which are: ^{1}ε_{0}, ^{1}ε_{1} = ^{1}ε_{0}(^{1}ε_{0} + 1), ^{1}ε_{2} = ^{1}ε_{0}(^{1}ε_{1} + 1), and for each integer n ≥ 0: 1ε_{n+1} = ^{1}ε_{0}(^{1}ε_{n} + 1). The next fixed point is the ω^{th} fixed point, denoted ^{1}ε_{ω}, and it is also the limit of the sequence of fixed points ^{1}ε_{n}, for n ≥ 0: ^{1}ε_{ω} = sup_{n∈ω}(^{1}ε_{n}). The sequence of fixed points of the operation of exponentiation of base ω_{1} continues beyond this ordinal because, for each ordinal α, there exists such a fixed point which is greater than α. These fixed points are indexed by ordinals and they are defined by induction on the ordinals. For every successor ordinal β + 1, the ordinal ^{1}ε_{β+1} is defined as above by: ^{1}ε_{β+1} = ^{1}ε_{0}(^{1}ε_{β} + 1). And for a limit ordinal δ the ordinal ^{1}ε_{δ} is defined by ^{1}ε_{δ} = sup_{β<δ}(^{1}ε_{β}). If A is a Δ_{ω}^{0}-Borel set then its Wadge degree is smaller than the ordinal ^{1}ε_{ω_{1}} which is the (ω_{1})^{th} fixed point of the operation of ordinal exponentiation of base ω_{1}. But for all ordinals δ < ω_{1} the ordinal ^{1}ε_{δ} has cofinality smaller than ω_{1}. Thus d_{w}(A) cannot be a fixed point of cofinality ω_{1} of the operation of ordinal exponentiation of base ω_{1}. The following Proposition easily follows from this fact and from Theorem 4.18.

Proposition 4.24 Let A ⊆ Σ^{≤ω} be a conciliating set such that A^{d} is a Δ_{ω}^{0}-Borel set and d_{c}(A) ≥ 2. Then d_{c}(A^{∼}) > d_{c}(A).

Remark 4.25 Let A ⊆ Σ^{≤ω} be such that A^{d} is a Δ_{ω}^{0}-Borel set and d_{c}(A) ≥ 2. Then one can easily show by induction that ∀n ≥ 1 d_{c}(A^{≈.n}) < d_{c}(A^{≈.(n+1)}). So this additional hypothesis we have made in Lemma 4.22 is in fact always satisfied.

The counterpart of the operation A → A^{•} with regard to Wadge degrees is given precisely by the following theorem.

Theorem 4.26 ^{2} Let A ⊆ Σ^{≤ω} be such that A^{d} is a Δ_{ω}^{0}-Borel set and d_{c}(A) ≥ 2.

(1) If d_{c}(A) is a fixed point (of cofinality ω) of the operation of exponentiation of base ω_{1}: α → ω_{1}^{α}, then d_{c}(A^{•}) = ^{1}ε_{0}(d_{c}(A) + 1).

(2) If d_{c}(A) is not a fixed point of the operation α → ω_{1}^{α}, then d_{c}(A^{•}) = ^{1}ε_{0}(d_{c}(A)).

(3) d_{c}(A^{•}) is the first fixed point of this operation which is strictly larger than d_{c}(A) and (A^{•})^{−} ≡_{c} A^{•} ∪ a^{≤ω} holds.

Proof. Let A ⊆ Σ^{≤ω} be such that A^{d} is a Δ_{ω}^{0}-Borel set and d_{c}(A) ≥ 2. We can prove that A^{•} and sup_{n≥1} F̄_{n}(A^{≈.n}) are conciliating Wadge equivalent, using the conciliating Wadge game, and examining in detail several cases which can happen. Then items (1) and (2) of Theorem 4.26 can be easily derived from Theorem 4.18 and Proposition 4.21. It follows from items (1) and (2) that d_{c}(A^{•}) is the first fixed point of the operation of ordinal exponentiation of base ω_{1} which is strictly larger than d_{c}(A). We can now prove that player 1 has a winning strategy in the conciliating Wadge game C(A^{•}, A^{•} ∪ a^{≤ω}) and also in the conciliating Wadge game C(A^{•} ∪ a^{≤ω}, A^{•}). This implies that neither A^{•} ∪ a^{≤ω} ≤_{c} A^{•} nor A^{•} ≤_{c} A^{•} ∪ a^{≤ω} hold. Then it follows from the properties of the conciliating hierarchy that (A^{•})^{−} ≡_{c} A^{•} ∪ a^{≤ω}. □

If A is an infinitary context-free language then A^{•} and A^{•}∪a^{≤ω} are infinitary contextfree languages. So if moreover A^{d} is a Δ_{ω}^{0}-Borel set and d_{c}(A) ≥ 2 then there exists an infinitary context-free language which is conciliating Wadge equivalent to (A^{•})^{−}. This fact will be useful in next section. Remark also that in particular if 2 ≤ d_{c}(A) <^{1} ε_{0}, i.e. if A^{d} is Borel of finite rank and of Wadge degree ≥ 2, then d_{c}(A^{•}) =^{1} ε_{0}, and A^{•} is a Borel set of rank ω.

5. Wadge Hierarchy of Infinitary Context-Free Languages

If we consider the operation of ordinal exponentiation of base ω: α → ω^{α}, one can define in a similar way as above the successive fixed points of this operation. These ordinals are the well known Cantor ordinals ε_{0}, ε_{1}, … and ε_{ω} is the ω^{th} such fixed point, [Sie65]. From the above closure properties of the class CF L_{≤ω} under the operations of sum, of exponentiation and of iterated exponentiation, and using the correspondence between these operations and the arithmetical operations over ordinals, one can show the following:

2In the short version [Fin01d] of this paper which appeared in the proceedings of LCCS 01 we omitted the distinction between items (1) and (2) of this theorem.

Theorem 5.1 The length of the conciliating hierarchy of infinitary languages in CF L_{≤ω} is greater than or equal to ε_{ω}. The length of the Wadge hierarchy of ωcontext-free languages in CF L_{ω} ∩ Δ_{ω}^{0} is greater than or equal to ε_{ω}.

Proof. We firstly define a strictly increasing function H from ε_{ω} into ^{1}ε_{ω}. This function is defined as follows: first H(n) = n for each integer n and H(ε_{i}) = ^{1}ε_{i} for each integer i ≥ 0. Next if α is a non null ordinal < ε_{ω}, it has an iterated Cantor normal form of base ω [Sie65]: α = ω^{α_{j}}.m_{j} + ω^{α_{j−1}}.m_{j−1} + … + ω^{α_{1}}.m_{1}, where j > 0 is an integer, ε_{ω} > α ≥ α_{j} > α_{j−1} > … > α_{1} are ordinals and m_{j}, m_{j−1}, …, m_{1} are integers > 0. And where each α_{i} itself is written in Cantor normal form of base ω, and so on. Then one can inductively define H′(α) and H(α) in the following way. We first set H′(α) = ω_{1}^{H(α_{j})}.m_{j}+ω_{1}^{H(α_{j−1})}.m_{j−1}+…+ω_{1}^{H(α_{1})}.m_{1}, and we distinguish now two cases:

First case. H′(α) = β + n with β a limit ordinal of cofinality ω, β ≠ ^{1}ε_{i} for all integers i ≥ 0, and n an integer ≥ 0. In that case we set H(α) = H′(α) + 1.

Second case. H′(α) = β + n with β a limit ordinal of cofinality ω_{1} or β = ^{1}ε_{i} for some integer i ≥ 0, and n an integer ≥ 0. In that case we set H(α) = H′(α).

So the shift we introduce in the first case is used to avoid the ordinal H(α) to be a limit ordinal of cofinality ω, different from ^{1}ε_{i} for all integers i ≥ 0, while the function H remains strictly increasing.

Let us give now some examples. For α = ε_{2} + 4, the above definition leads to H(α) = ^{1}ε_{2} + 4, while for α = ε_{2} + ε_{1} + 4 it holds that H(α) = ^{1}ε_{2} + ^{1}ε_{1} + 5. For α = ε_{2}.3 + ω^{(ε_{1}+ω^{ω})} + ω^{(ω^{ω}+2)}, the above definition leads to H(α) = ^{1}ε_{2}.3 + ω_{1}^{(^{1}ε_{1}+ω_{1}^{ω_{1}} )} + ω_{1}^{(ω_{1}^{ω_{1}} +2)}, and for

α = ε_{4}.3 + ω^{(ε_{3}+ε_{1})} + ω^{(ε_{2}+ε_{1}+5)} + ε_{2} + 3

it holds that

H(α) = ^{1}ε_{4}.3 + ω_{1}^{(^{1}ε_{3}+^{1}ε_{1}+1)} + ω_{1}^{(^{1}ε_{2}+^{1}ε_{1}+6)} + ^{1}ε_{2} + 4

It is easy to show that the function H is stricly increasing, thus the image H(ε_{ω}) is of order type ε_{ω}, and so is H(ε_{ω}) − {0}.

We can now follow Definition 32 of [Dup01] and define a conciliating context-free language Ω(H(α)) of degree H(α), for each non null ordinal α < ε_{ω}. We shall need also to define a conciliating context-free language Ω(H′(α)) of degree H′(α) in the case H′(α) is an ordinal of cofinality ω different from ^{1}ε_{i} for all integers i ≥ 0.

Let δ be a non null ordinal in H(ε_{ω}). Then δ < ^{1}ε_{ω} hence δ admits an iterated Cantor normal form of base ω_{1}, [Sie65]:

δ = ω_{1}^{δ_{j}}.ν_{j} + ω_{1}^{δ_{j−1}}.ν_{j−1} + … + ω_{1}^{δ_{1}}.ν_{1}

where j > 0 is an integer, ^{1}ε_{ω} > δ ≥ δ_{j} > δ_{j−1} > … > δ_{1} are ordinals and ν_{j}, ν_{j−1}, …, ν_{1} are non null ordinals < ω_{1}, and each δ_{i} itself is written in Cantor normal form of base ω_{1}, and so on … But here each ordinal ν_{i} is an integer because δ ∈ H(ε_{ω}) and for each i, δ_{i} ∈ H(ε_{ω}) also holds. Then one can inductively define the set

Ω(δ) = Ω(ω_{1}^{δ_{j}}).ν_{j} + Ω(ω_{1}^{δ_{j−1}}).ν_{j−1} + … + Ω(ω_{1}^{δ_{1}}).ν_{1}

where Ω(ω_{1}^{β}) with β < ^{1}ε_{ω} and β ∈ H(ε_{ω}) is defined by:

a) If β = 0, then Ω(ω_{1}^{β}) = Ω(1) = ∅.

b) If β = n > 0 is an integer, then Ω(ω_{1}^{β}) = Ω(β + 1)^{∼}.

c) If β = γ + n where γ is an ordinal of cofinality ω_{1} and n is an integer ≥ 0, then Ω(ω_{1}^{β}) = Ω(β)^{∼}.

d) Let β = ω_{1}^{β} = ^{1}ε_{i}, for some integer i, 0 ≤ i < ω. We shall construct some infinitary context-free languages of (conciliating) Wadge degrees ^{1}ε_{i}, for 0 ≤ i < ω. Let A ∈ CF L_{≤ω} such that d_{c}(A) = 2 (for example A = ∅ + ∅ where ∅ is the empty conciliating set,which is of Wadge degree 1) then d_{c}(A^{•}) = ^{1}ε_{0}(d_{c}(A)) = ^{1}ε_{0}. Denote Ω(^{1}ε_{0}) = A^{•}. The ordinal d_{c}(A^{•}) = ^{1}ε_{0} is a fixed point of the operation of exponentiation of base ω_{1} which has cofinality ω. Thus if A^{•.2} = (A^{•})^{•} then

d_{c}(A^{•.2}) = ^{1}ε_{0}(d_{c}(A^{•}) + 1)) = ^{1}ε_{0}(^{1}ε_{0} + 1) = ^{1}ε_{1}

by Theorem 4.26 (1). Next we can iterate this construction, defining inductively for integers j ≥ 2 the sets A^{•.j} = (A^{•.(j−1)})^{•}. Then one can prove by induction that for each integer j ≥ 2

d_{c}(A^{•.j}) = ^{1}ε_{0}(d_{c}(A^{•.(j−1)}) + 1)) = ^{1}ε_{0}(^{1}ε_{j−2} + 1) = ^{1}ε_{j−1}

Then we denote Ω(^{1}ε_{i}) = A^{•.(i+1)} and d_{c}(Ω(^{1}ε_{i})) = ^{1}ε_{i} holds for every integer i ≥ 0. Remark that the above construction is a particular case of Duparc’s construction of a conciliating set Ω(ω_{1}^{β}) of degree ω_{1}^{β} when β is an ordinal of cofinality ω. Indeed the ordinals ^{1}ε_{j}, for 0 ≤ j < ω, have cofinality ω because ^{1}ε_{0} = sup_{n≥1} ω_{1}(n, 2) and ^{1}ε_{j+1} = sup_{n≥1} ω_{1}(n, ^{1}ε_{j} + 1) holds for every integer j ≥ 0.

e) If β = ^{1}ε_{i} + n where i is an integer ≥ 0 and n is an integer > 0, then Ω(ω_{1}^{β}) = Ω(β − 1)^{∼}.

f) If β = γ + n where γ is an ordinal of cofinality ω, n is an integer > 1, and γ ≠^{1} ε_{i} for all integers i ≥ 0, then Ω(ω_{1}^{β}) = Ω(β − 1)^{∼}. g) Let β = γ + 1 where γ is an ordinal of cofinality ω, and γ ≠^{1} ε_{i} for all integers

i ≥ 0.

In that case there exists an ordinal α < ε_{ω} such that γ = H′(α) and β = H(α) = H′(α) + 1. The Cantor normal form of base ω of the ordinal α is:

α = ω^{α_{j}}.m_{j} + ω^{α_{j−1}}.m_{j−1} + … + ω^{α_{1}}.m_{1}

where j > 0 is an integer, ε_{ω} > α ≥ α_{j} > α_{j−1} > … > α_{1} are ordinals and m_{j}, m_{j−1}, …, m_{1} are integers > 0. And we have defined H′(α) by

H′(α) = ω_{1}^{H(α_{j})}.m_{j} + ω_{1}^{H(α_{j−1})}.m_{j−1} + … + ω_{1}^{H(α_{1})}.m_{1}

so we can inductively define

Ω(H′(α)) = Ω(ω_{1}^{H(α_{j})}).m_{j} + Ω(ω_{1}^{H(α_{j−1})}).m_{j−1} + … + Ω(ω_{1}^{H(α_{1})}).m_{1}

and we set

Ω(ω_{1}^{β}) = Ω(β − 1)^{∼} = Ω(γ)^{∼} = Ω(H′(α))^{∼}

h) Notice that it is not necessary to define Ω(ω_{1}^{β}) in the case of an ordinal β of cofinality ω and different from^{1}ε_{i} for all integers i ≥ 0. This case cannot happen here because of the shift we introduced in the first case of the definition of the ordinal H(α).

The closure properties of the class CF L_{≤ω} under the operations of sum, of exponentiation and of iterated exponentiation imply that, for every ordinal δ ∈ H(ε_{ω}), Ω(δ) ∈ CF L_{≤ω} holds and the complement of Ω(δ) is (conciliating) Wadge equivalent to some conciliating set in CF L_{≤ω}. By our construction and by Theorems 4.10, 4.18 and 4.26 (or using Theorem 33 of [Dup01]) d_{c}(Ω(δ)) = δ < ^{1}ε_{ω} holds for every δ ∈ H(ε_{ω}), the length of the conciliating hierarchy of infinitary context-free languages is greater than or equal to ε_{ω}. We consider now the Wadge hierarchy of ω-context-free languages. For each non null ordinal α < ε_{ω}, the ω-language Ω(H(α))^{d} is a Borel set in the class CF L_{ω} ∩ Δ_{ω}^{0} and d_{w}(Ω(H(α))^{d}) = d_{c}(Ω(H(α))) = H(α). This proves that the length of the Wadge hierarchy of ω-context-free languages in CF L_{ω} ∩ Δ_{ω}^{0} is greater than or equal to the ordinal ε_{ω}. □

6. Σ_{ω}^{0}-Complete ω-Context-Free Language

With the operations we have studied above, one cannot reach, from a (conciliating) Borel set of finite rank, a Borel set of Wadge degree ^{1}ε_{ω}. And every (conciliating) set that we can generate is of Wadge degree < ^{1}ε_{ω}. In particular one cannot construct, from known ω-CFL of finite Borel rank, an ω-context-free language being a Σ_{ω}^{0}- complete Borel set. Indeed the Wadge degree of a Σ_{ω}^{0}-complete Borel set is ^{1}ε_{ω_{1}}, i.e. the (ω_{1})^{th} fixed point of the operation of ordinal exponentiation of base ω_{1}, which is a much larger ordinal than ^{1}ε_{ω}. However we are going to show in this section that there exist some Σ_{ω}^{0}-complete ω-context-free language, using other methods and results about sets of ω^{2}-words.

The set Σ^{ω^{2}} is the set of ω^{2}-words over the finite alphabet Σ. It may also be viewed as the set of (infinite) (ω × ω)-matrices whose coefficients are letters of Σ. If x ∈ Σ^{ω^{2}} we shall write x = (x(m, n))_{m≥1,n≥1}. The infinite word x(m, 1)x(m, 2) … x(m, n) … will be called the m^{th} column of the ω^{2}-word x and the infinite word x(1, n)x(2, n) … x(m, n) … will be called the n^{th} row of the ω^{2}- word x. Thus an element of Σ^{ω^{2}} is completely determined by the (infinite) set of its columns or of its rows. The set Σ^{ω^{2}} is usually equipped with the product topology of the discrete topology on Σ (for which every subset of Σ is an open set), see [Kec95, PP04]. For this topology on Σ^{ω^{2}}, the basic open sets are the sets of ω^{2}-words with a fixed twodimensional prefix. This topology may be defined by the following distance d. Let x and y be two ω^{2}-words in Σ^{ω^{2}} such that x ≠ y, then d(x, y) = 2^{−n}, where n = min{p ≥ 1 | ∃(i, j) x(i, j) ≠ y(i, j) and i + j = p}. Then the topological space Σ^{ω^{2}} is homeomorphic to the above defined topological space Σ^{ω}. The Borel hierarchy on Σ^{ω^{2}} is defined from open sets in the same manner as in the case of the topological space Σ^{ω}. The notion of Σ_{α}^{0} (respectively Π_{α}^{0})- complete sets are also defined in a similar way. Notice that the topological space Σ^{ω^{2}} has already been used in a very closely work on the topological complexity of infinitary rational relations accepted by 2-tape Büchi automata [Fin03c].

Recall now that the set S = {x ∈ {0, 1}^{ω^{2}} | ∃m∃^{∞}n x(m, n) = 1}, where ∃^{∞} means “there exist infinitely many”, is a Σ_{3}^{0}-complete subset of {0, 1}^{ω^{2}}, [Kec95, p.179]. It is the set of ω^{2}-words having at least one column in the Π_{2}^{0}-complete subset R = (0^{⋆}.1)^{ω} of {0, 1}^{ω}. In a similar manner we can prove the following result:

Lemma 6.1 Let L ⊆ Σ^{ω} be a Σ_{ω}^{0}-subset of Σ^{ω} which is of Borel rank ω. Then the set L = {x ∈ Σ^{ω^{2}} | ∃m x(m, 1)x(m, 2) … x(m, n) … ∈ L} of ω^{2}-words over Σ having at least one column in L is a Σ_{ω}^{0}-complete subset of Σ^{ω^{2}}.

In order to simplify our proofs we shall use in the sequel the following variant of lemma 6.1 which can be proved with a slight modification.

Lemma 6.2 Let L ⊆ Σ^{ω} be a Σ_{ω}^{0}-subset of Σ^{ω} which is of Borel rank ω. Then the set L^{e} = {x ∈ Σ^{ω^{2}} | ∃m ≥ 1 x(2m, 1)x(2m, 2) … x(2m, n) … ∈ L} of ω^{2}-words over Σ having at least one column of even index in L is a Σ_{ω}^{0}-complete subset of Σ^{ω^{2}}.

In order to use these results we shall firstly define a coding of ω^{2}-words over Σ by ω-words over the alphabet (Σ ∪ {C, B}) where C and B are new letters not in Σ. Let us call, for x ∈ Σ^{ω^{2}} and p an integer ≥ 2:

T_{p+1}^{x} = {x(p, 1), x(p − 1, 2), …, x(2, p − 1), x(1, p)}

the set of elements x(m, n) with m + n = p + 1 and

U_{p+1}^{x} = x(p, 1).x(p − 1, 2) … x(2, p − 1).x(1, p)

the sequence formed by the concatenation of elements x(m, n) of T_{p+1}^{x} for increasing values of n. We also call

V_{p+1}^{x} = (U_{p+1}^{x})^{R} = x(1, p).x(2, p − 1) … x(p − 1, 2).x(p, 1)

the reverse image of U_{p+1}^{x}. Thus U_{p+1}^{x} and V_{p+1}^{x} are finite non empty words over Σ and U_{2}^{x} = V_{2}^{x} = x(1, 1).

We shall code an ω^{2}-word x ∈ Σ^{ω^{2}} by the ω-word h(x) defined by

h(x) = V_{2}^{x}.C.U_{3}^{x}.B.V_{4}^{x}.C.U_{5}^{x}.B.V_{6}^{x}.C … C.U_{2k+1}^{x}.B.V_{2k+2}^{x}.C …

The word h(x) begins with x(1, 1) = V_{2}^{x} followed by a letter C; then the word h(x) enumerates the elements of the sets T_{p+1}^{x} for increasing values of the integer p. More precisely for every even integer 2k ≥ 2 the elements of T_{2k+1}^{x} are enumerated by the sequence U_{2k+1}^{x}, followed by a letter B, followed by the elements of T_{2k+2}^{x}, enumerated by the sequence V_{2k+2}^{x}, followed by a letter C, and so on … Let then h be the mapping from Σ^{ω^{2}} into (Σ ∪ {C, B})^{ω} such that, for every ω^{2}-word x over the alphabet Σ, h(x) is the code of the ω^{2}-word x as defined above. It is easy to see, from the definition of h and of the order of the enumeration of letters x(m, n) (they are enumerated for increasing values of m + n), that h is a continuous function from Σ^{ω^{2}} into (Σ ∪ {C, B})^{ω}.

Lemma 6.3 Let Σ be a finite alphabet. If L ⊆ Σ^{ω^{2}} is Σ_{ω}^{0}-complete then h(L) ∪ h(Σ^{ω^{2}})^{−} is a Σ_{ω}^{0}-complete subset of (Σ ∪ {C, B})^{ω}.

Proof. The topological space Σ^{ω^{2}} is compact thus its image by the continuous function h is also a compact subset of the topological space (Σ ∪ {C, B})^{ω}. The set h(Σ^{ω^{2}}) is compact hence it is a closed subset of (Σ ∪ {C, B})^{ω}. Then its complement (h(Σ^{ω^{2}}))^{−} is an open (i.e. a Σ_{1}^{0}) subset of (Σ ∪ {C, B})^{ω}. On the other hand the function h is also injective thus it is a bijection from Σ^{ω^{2}} onto h(Σ^{ω^{2}}). But a continuous bijection between two compact sets is an homeomorphism therefore h induces an homeomorphism between Σ^{ω^{2}} and h(Σ^{ω^{2}}). By hypothesis L is a Σ_{ω}^{0}-subset of Σ^{ω^{2}} thus h(L) is a Σ_{ω}^{0}-subset of h(Σ^{ω^{2}}) (where Borel sets of the topological space h(Σ^{ω^{2}}) are defined from open sets as in the cases of the topological spaces Σ^{ω} or Σ^{ω^{2}}). The topological space h(Σ^{ω^{2}}) is a topological subspace of (Σ ∪ {C, B})^{ω} and its topology is induced by the topology on (Σ ∪ {C, B})^{ω}: open sets of h(Σ^{ω^{2}}) are traces on h(Σ^{ω^{2}}) of open sets of (Σ ∪ {C, B})^{ω} 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(Σ^{ω^{2}}) are traces on h(Σ^{ω^{2}}) of Π_{α}^{0}-subsets (resp. Σ_{α}^{0}-subsets) of (Σ ∪ {C, B})^{ω}, i.e. are intersections with h(Σ^{ω^{2}}) of Π_{α}^{0}-subsets (resp. Σ_{α}^{0}-subsets) of (Σ ∪ {C, B})^{ω}. But h(L) is a Σ_{ω}^{0}-subset of h(Σ^{ω^{2}}), hence there exists a Σ_{ω}^{0}-subset T of (Σ∪{C, B})^{ω} such that h(L) = T ∩ h(Σ^{ω^{2}}). But h(Σ^{ω^{2}}) is a closed i.e. Π_{1}^{0}-subset of (Σ ∪ {C, B})^{ω} and the class of Σ_{ω}^{0}-subsets of (Σ ∪ {C, B})^{ω} is closed under finite intersection, thus h(L) is a Σ_{ω}^{0}-subset of (Σ ∪ {C, B})^{ω}. Now h(L)∪(h(Σ^{ω^{2}}))^{−} is the union of a Σ_{ω}^{0}-subset and of a Σ_{1}^{0}-subset of (Σ∪{C, B})^{ω} therefore it is a Σ_{ω}^{0}-subset of (Σ ∪ {C, B})^{ω} because the class of Σ_{ω}^{0}-subsets of (Σ ∪ {C, B})^{ω} is closed under finite (and even countable) union. In order to prove that h(L) ∪ (h(Σ^{ω^{2}}))^{−} is Σ_{ω}^{0}-complete it suffices to remark that L = h^{−1}[h(L) ∪ (h(Σ^{ω^{2}}))^{−}]. This implies that h(L) ∪ (h(Σ^{ω^{2}}))^{−} is Σ_{ω}^{0}-complete because L is assumed to be Σ_{ω}^{0}-complete. □

Lemma 6.4 Let Σ be a finite alphabet and h be the coding of ω^{2}-words over Σ defined as above. Then h(Σ^{ω^{2}})^{−} = (Σ ∪ {C, B})^{ω} − h(Σ^{ω^{2}}) is an ω-CFL.

Proof. Remark first that h(Σ^{ω^{2}}) is the set of ω-words in (Σ ∪ {C, B})^{ω} which belong to

Σ.C.Σ^{2}.B.Σ^{3}.C.Σ^{4}.B … C.Σ^{2k}.B.Σ^{2k+1}.C …

In other words this is the set of words in (Σ ∪ {C, B})^{ω} which are in (Σ^{⋆}.C.Σ^{⋆}.B)^{ω} and have k + 1 letters of Σ between the k^{th} and the (k + 1)^{th} occurrences of letters in {C, B}. It is now easy to see that the complement of the set h(Σ^{ω^{2}}) of codes of ω^{2}-words over Σ is the union of the sets C_{1} and C_{2} where:

• C_{1} = (Σ ∪ {C, B})^{ω} − (Σ^{⋆}.C.Σ^{⋆}.B)^{ω} hence C_{1} is the complement of the ωregular language (Σ^{⋆}.C.Σ^{⋆}.B)^{ω} so it is also an ω-regular language thus C_{1} is an ω-CFL.

• C_{2} is the set of ω-words over (Σ ∪ {C, B}) which may be written in the form w.u.C.t or w.u.B.t where w ∈ (Σ^{⋆}.{C, B})^{k}, for k ≥ 0, and u ∈ Σ^{⋆} and |u| ≠ k + 1 and t ∈ (Σ ∪ {C, B})^{ω}. It is easy to show that

C = {w.u | w ∈ (Σ^{⋆}.{C, B})^{k} for an integer k ≥ 0 and u ∈ Σ^{⋆} and |u| ≠ k + 1}

is a context-free finitary language, thus C_{2} = C.{C, B}.(Σ ∪ {C, B})^{ω} is an ω-CFL.

Now h(Σ^{ω^{2}})^{−} = C_{1} ∪ C_{2} is an ω-CFL because CF L_{ω} is closed under finite union. □

Let L ⊆ Σ^{ω} be an ω-CFL over the alphabet Σ and

L^{e} = {x ∈ Σ^{ω^{2}} | ∃m ≥ 1 x(2m, 1)x(2m, 2) … x(2m, n) … ∈ L}

We cannot show that h(L^{e}) is an ω-CFL but we shall find an ω-CFL C^{e} ⊆ (Σ ∪ {C, B})^{ω} such that, for every ω^{2}-word x ∈ Σ^{ω^{2}}, h(x) ∈ C^{e} if and only if x ∈ L^{e}. We are now going to describe the ω-language C^{e}. A word y ∈ (Σ ∪ {C, B})^{ω} is in C^{e} if and only if it is in the form

y = U_{k}.t(1).u_{1}.B.v_{1}.t(2).w_{1}.C.z_{1}.t(3) …
… t(2n + 1).u_{n+1}.B.v_{n+1}.t(2n + 2).w_{n+1}.C.z_{n+1}.t(2n + 3) …

where k is an integer ≥ 1, U_{k} ∈ (Σ^{⋆}.C.Σ^{⋆}.B)^{k−1}.(Σ^{⋆}.C), and for all integers i ≥ 1, t(i) ∈ Σ and u_{i}, v_{i}, w_{i}, z_{i} ∈ Σ^{⋆} and |v_{i}| = |u_{i}| and |z_{i}| = |w_{i}| + 1, and the ω-word t = t(1)t(2) … t(n) … is in the ω-language L.

We now state the following result.

Lemma 6.5 Let L ⊆ Σ^{ω} and let L^{e} ⊆ Σ^{ω^{2}} and C^{e} ⊆ (Σ ∪ {C, B})^{ω} be defined as above. Then L^{e} = h^{−1}(C^{e}), i.e. ∀x ∈ Σ^{ω^{2}} h(x) ∈ C^{e} ⟷ x ∈ L^{e}.

Proof. Let L ⊆ Σ^{ω} be an ω-language over the alphabet Σ and let L^{e} ⊆ Σ^{ω^{2}} and C^{e} ⊆ (Σ ∪ {C, B})^{ω} be defined as above. Assume now that an y ∈ C^{e}, written in the above form, is the code h(x) of an ω^{2}-word x ∈ Σ^{ω^{2}}, then t(1).u_{1} = U_{2k+1}^{x} = x(2k, 1)x(2k − 1, 2) … x(1, 2k). So in particular x(2k, 1) = t(1) holds. Next v_{1}.t(2).w_{1} = V_{2k+2}^{x} then x(2k, 2) = t(2) holds because the elements of T_{2k+2}^{x} and the elements of T_{2k+1}^{x} are enumerated in reverse orders in the code of x and because |u_{1}| = |v_{1}|. Then |z_{1}| = |w_{1}| + 1 implies that x(2k, 3) = t(3). By construction this phenomenon will happen further. One can easily show by induction on integers n that letters t(n) are successive letters of the (2k)^{th} column of x. For that purpose assume that for some integer n ≥ 1 it holds that t(2n+1) = x(2k, 2n+1). By definition of the code h(x) we know that

U_{2k+2n+1}^{x} = x(2k + 2n, 1)x(2k + 2n − 1, 2) … x(1, 2k + 2n) = z_{n}.t(2n + 1).u_{n+1}

and t(2n + 1) = x(2k, 2n + 1) implies that |u_{n+1}| = (2k + 2n) − (2n + 1) = 2k − 1. Thus |v_{n+1}| = |u_{n+1}| = 2k − 1. But it holds also that

V_{2k+2n+2}^{x} = x(1, 2k + 2n + 1)x(2, 2k + 2n) … x(2k + 2n + 1, 1) = v_{n+1}.t(2n + 2).w_{n+1}

therefore t(2n + 2) = x(2k, 2n + 2) and |w_{n+1}| = (2k + 2n + 1) − (2k) = 2n + 1. But |z_{n+1}| = |w_{n+1}| + 1 = 2n + 2 and

U_{2k+2n+3}^{x} = x(2k+2n+2, 1)x(2k+2n+1, 2) … x(1, 2k+2n+2) = z_{n+1}.t(2n+3).u_{n+2}

thus t(2n + 3) = x(2k, 2n + 3). Then we have proved by induction that: t = t(1)t(2) … t(n) … = x(2k, 1)x(2k, 2) … x(2k, n) … Thus if a code h(x) of an ω^{2}-word x ∈ Σ^{ω^{2}} is in C^{e} then x has a column of even index in L, i.e. x ∈ L^{e}. Conversely it is easy to see that every code h(x) of x ∈ L^{e} may be written in the above form of a word in C^{e} (remark that if x ∈ L^{e} has several columns of even indices in L then h(x) has several written forms as above, the integer k determining one of the columns of even index of x being in L). Then we have proved that for every ω^{2}-word x ∈ Σ^{ω^{2}} h(x) ∈ C^{e} if and only if x ∈ L^{e}. □

Lemma 6.6 Let L ⊆ Σ^{ω} be an ω-CFL over the alphabet Σ and let L^{e} ⊆ Σ^{ω^{2}} and C^{e} ⊆ (Σ ∪ {C, B})^{ω} be defined from L as above. Then C^{e} is an ω-CFL over the alphabet Σ ∪ {C, B}.

Proof. Assume that L ⊆ Σ^{ω} is an ω-CFL and let L^{e} ⊆ Σ^{ω^{2}} and C^{e} ⊆ (Σ ∪ {C, B})^{ω} be defined from L as above. Let D_{1} and D_{2} be the following finitary languages:

D_{1} = {u.B.v | u, v ∈ Σ^{⋆} and |u| = |v|},
D_{2} = {w.C.z | w, z ∈ Σ^{⋆} and |z| = |w| + 1}.

It is easy to see that D_{1} and D_{2} are context-free finitary languages over the alphabet Σ ∪ {C, B} thus D = D_{1} ∪ D_{2} is also a context-free finitary language.

Recall now the definition of substitution in languages: a substitution f is defined by a mapping Σ → P (Γ^{⋆}), where Σ = {a_{1}, a_{2} …, a_{n}} and Γ are two finite alphabets, f : a_{i} → L_{i} where ∀i ∈ [1; n], L_{i} is a finitary language over the alphabet Γ. This mapping is extended in the usual manner to finite words: f(x(1) … x(n)) = {u_{1} … u_{n} | ∀i ∈ [1; n] u_{i} ∈ f(x(i))}, where x(1), …, x(n) are letters in Σ, and to finitary languages E ⊆ Σ^{⋆}: f(E) = ∪_{x∈E}f(x). The substitution f is called λ-free if for every i ∈ [1; n] L_{i} does not contain the empty word. In that case 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 E ⊆ Σ^{ω} by f(E) = ∪_{x∈E}f(x). Let 𝔽 be a family of languages, if for every i ∈ [1; n] the language L_{i} belongs to 𝔽 the substitution f is called a 𝔽-substitution. Let then g be the substitution Σ → P ((Σ ∪ {C, B})^{⋆}) defined by: a → a.D where D is the context-free language defined above. Then g is a λ-free substitution. But the languages a.D are context-free and CF L_{ω} is closed under λ-free context-free substitution [CG77] thus the ω-language g(L) is context-free. The class CF L_{ω} is closed under intersection with ω-regular languages, therefore the ω-language g(L) ∩ (Σ^{⋆}.B.Σ^{⋆}.C)^{ω} is context-free. But it is easy to see that

C^{e} = (Σ^{⋆}.C.Σ^{⋆}.B)^{⋆}.(Σ^{⋆}.C).[g(L) ∩ (Σ^{⋆}.B.Σ^{⋆}.C)^{ω}].

Thus C^{e} is an ω-context-free language because the class CF L_{ω} is closed under left concatenation by regular (finitary) languages. □

We can now state the main result of this section.

Theorem 6.7 There exist some ω-context-free languages which are Σ_{ω}^{0}-complete Borel sets.

Proof. We already know that there exist some ω-context-free languages which are Σ_{ω}^{0}-sets of Borel rank ω. Let then L be such an ω-CFL and let L^{e} ⊆ Σ^{ω^{2}} and C^{e} ⊆ (Σ ∪ {C, B})^{ω} defined from L as above. By Lemma 6.2 the set L^{e} is a Σ_{ω}^{0}- complete subset of Σ^{ω^{2}} then by Lemma 6.3 the ω-language h(L^{e}) ∪ h(Σ^{ω^{2}})^{−} is a Σ_{ω}^{0}-complete subset of (Σ ∪ {C, B})^{ω}. But Lemma 6.5 states that L^{e} = h^{−1}(C^{e}), and this implies that h(L^{e}) ∪ h(Σ^{ω^{2}})^{−} = C^{e} ∪ h(Σ^{ω^{2}})^{−}. On the other hand we have proved in Lemmas 6.4 and 6.6 that the ω-languages h(Σ^{ω^{2}})^{−} and C^{e} are contextfree. Thus their union is an ω-context-free language which is a Σ_{ω}^{0}-complete subset of (Σ ∪ {C, B})^{ω}. □

We know that the Wadge degree of the Σ_{ω}^{0}-complete Borel set C^{e} ∪ h(Σ^{ω^{2}})^{−} is the ordinal ^{1}ε_{ω_{1}}. On the other hand it is easy to see that this set has same degree if we consider it as a conciliating set. So we can now state the following result, improving Theorem 5.1 of preceding section.

Theorem 6.8 The length of the conciliating hierarchy of infinitary context-free languages, which are Borel of rank ω, is strictly greater than ε_{ω}. The length of the Wadge hierarchy of ω-context-free languages in CF L_{ω} ∩ Σ_{ω}^{0} is strictly greater than ε_{ω}.

7. Concluding Remarks

We have improved previous results on Wadge and Borel hierarchies of ω-context-free languages. We have proved the existence of more than ε_{ω} Wadge degrees of ω-context-free languages. And we have also given an inductive construction of an ω-context-free language in each of these degrees and also of a Büchi or Muller pushdown automaton accepting it, using the previous work of Duparc on the Wadge hierarchy of Borel sets. The question remains open to determine all the Borel ranks and the Wadge degrees of ω-context-free languages.

Acknowledgements

Thanks to Jean-Pierre Ressayre and Jacques Duparc for many useful discussions about Wadge and Wagner Hierarchies and to the anonymous referees for useful comments on a preliminary version of this paper.

References

[AN82] A. Arnold and M. Nivat, Comportements de Processus, Colloque AFCET ”Les Mathématiques de l’Informatique” , Paris (1982), p. 35-68.

[ABB96] J-M. Autebert, J. Berstel and L. Boasson, Context Free Languages and Pushdown Automata, in Handbook of Formal Languages, Vol 1, Springer Verlag 1996.

[Bea84a] D. Beauquier, Langages Algébriques Infinitaires, Ph. D. Thesis, Université Paris 7, 1984.

[Bea84b] D. Beauquier, Some Results about Finite and Infinite Behaviours of a Pushdown Automaton, Proceedings of the 11^{th} International Colloquium on Automata, languages and Programming (ICALP 84) LNCS 172, p. 187-195 (1984).

24 O. Finkel

[BN80] L. Boasson and M. Nivat, Adherences of Languages, J. Comput. System Sci. 20 (1980) no. 3, p. 285-309.

[CP97] O. Carton and D. Perrin, Chains and Superchains for ω-Rational Sets, Automata and semigroups, International Journal of Algebra and Computation Vol. 7, no. 7(1997), p. 673-695.

[CP99] O. Carton and D. Perrin, The Wagner Hierarchy of ω-Rational Sets, International Journal of Algebra and Computation, Vol. 9, no. 5 (1999), p. 597-620.

[CK73] C.C. Chang and H.J. Keisler, Model Theory, American Elsevier Publishing Company, Inc, New York, 1973. ( North Holland, Amsterdam, 3rd ed., 1990).

[CG77] R. S. Cohen and A. Y. Gold, Theory of ω-Languages, Parts one and two, J. Computer and System Science 15 (1977) 2, 169-184 and 185-208.

[CG78] R. S. Cohen and A. Y. Gold, ω-Computations on Deterministic Pushdown Machines, J. Computer and System Science (1978) 3, 257-300.

[Dup95a] J. Duparc, La Forme Normale des Boréliens de Rang Fini, Ph.D. Thesis, Université Paris 7, 1995.

[Dup01] J. Duparc, Wadge Hierarchy and Veblen Hierarchy: Part 1: Borel Sets of Finite Rank, Journal of Symbolic Logic, 66 (2001), no. 1, p. 56-86.

[Dup03] J. Duparc, A Hierarchy of Deterministic Context Free ω-Languages, Theoretical Computer Science, Volume 290 (3), 2003, p. 1253-1300.

[DFR01] J. Duparc, O. Finkel and J-P. Ressayre, Computer Science and the Fine Structure of Borel Sets, Theoretical Computer Science, Volume 257 (1-2), 2001, p.85-105.

[EH93] J. Engelfriet and H. J. Hoogeboom, X-automata on ω-Words, Theoretical Computer Science 110 (1993) 1, 1-51.

[Fin01a] O. Finkel, Topological Properties of Omega Context Free Languages, Theoretical Computer Science, Volume 262 (1-2), 2001, p. 669-697.

[Fin01b] O. Finkel, Wadge Hierarchy of Omega Context Free Languages, Theoretical Computer Science, Volume 269 (1-2), 2001, p.283-315.

[Fin01c] O. Finkel, An Effective Extension of the Wagner Hierarchy to Blind Counter Automata, Proceedings of Computer Science Logic 2001, Lecture Notes in Computer Science, Volume 2142, p. 369-383.

[Fin01d] O. Finkel, On the Wadge Hierarchy of Omega Context Free Languages, in the Proceedings of the International Workshop on Logic and Complexity in Computer Science held in honour of Anatol Slissenko for his 60^{th} birthday, Créteil, France, 2001, p.69-79. Available from http://www.univ-paris12.fr/lacl/LCCS2001/index.html

[Fin01e] O. Finkel, Wadge Hierarchy of Petri Net Omega Languages, in preparation.

[Fin03a] O. Finkel, Borel Hierarchy and Omega Context Free Languages, Theoretical Computer Science, Volume 290 (3), 2003, p.1385-1405.

[Fin03b] O. Finkel, On Omega Context Free Languages which are Borel Sets of Infinite Rank, Theoretical Computer Science, Volume 299 (1-3), 2003, p. 327-346.

[Fin03c] O. Finkel, On Infinitary Rational Relations and Borel Sets, in the Proceedings of the Fourth International Conference on Discrete Mathematics and Theoretical Computer Science DMTCS 2003, Dijon, France, Lecture Notes in Computer Science, Volume 2731, 2003, p. 155-167.

[Kec95] A.S. Kechris, Classical Descriptive Set Theory, Springer-Verlag, 1995.

[LT94] H. Lescow and W. Thomas, Logical Specifications of Infinite Computations, In:”A Decade of Concurrency” (J. W. de Bakker et al., eds), Springer LNCS 803 (1994), 583-621.

[Lin76] M. Linna, On ω-Sets Associated with Context-Free Languages, Inform. Control 31 (1976) 3, 272-293.

[Lin77] M. Linna, A Decidability Result for Deterministic ω-Context-Free Languages, Theoretical Computer Science 4 (1977), 83-98.

[Mos80] Y. N. Moschovakis, Descriptive Set Theory, North-Holland, Amsterdam 1980.

[Niv77] M. Nivat, Mots Infinis Engendrés par une Grammaire Algébrique, RAIRO Infor. Théor. 11 (1977), 311-327.

[Niv78] M. Nivat, Sur les Ensembles de Mots Infinis Engendrés par une Grammaire Algébrique, RAIRO Infor. théor. 12 (1978), 259-278.

[PP04] D. Perrin and J.-E. Pin, Infinite Words, Automata, Semigroups, Logic and Games, Volume 141 of Pure and Applied Mathematics, Elsevier, 2004.

[Sel94] V. Selivanov, Fine Hierarchy of Regular ω-Languages, Preprint N 14, 1994, The University of Heidelberg, Chair of Mathematical Logic, 13pp.

[Sel95] V. Selivanov, Fine Hierarchy of Regular ω-Languages, In the Proceedings of the International Joint Conference on the Theory and Practice of Software Development TAPSOFT-95, in Aarhus, Denmark, Lecture Notes in Computer Science, Volume 915, Berlin, Springer, 1995, p. 277-287.

[Sel98] V. Selivanov, Fine Hierarchy of Regular ω-Languages, Theoretical Computer Science, Volume 191, (1998), p.37-59.

[Sel03a] V. L. Selivanov: Wadge Degrees of omega-Languages of Deterministic Turing Machines, in the Proceedings of STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, Lecture Notes in Computer Science 2607, Springer 2003, p. 97-108.

[Sel03b] V. L. Selivanov: Wadge Degrees of omega-Languages of Deterministic Turing Machines, RAIRO-Theoretical Informatics and Applications, Volume 37 (1), 2003, p. 67-83.

[Sie65] W. Sierpinski, Cardinal and Ordinal Numbers, Polish Scientific Publisher, Varsovie, 1965.

[Sim92] P. Simonnet, Automates et Théorie Descriptive, Ph.D. Thesis, Université Paris 7, March 1992.

[SW74] L. Staiger and K. Wagner, Automatentheoretische und Automatenfreie Charakterisierungen Topologischer Klassen Regulärer Folgenmengen. Elektron. Informationsverarb. Kybernetik EIK 10 (1974) 7, 379-392.

[Sta86] L. Staiger, Hierarchies of Recursive ω-Languages, Jour. Inform. Process. Cybernetics EIK 22 (1986) 5/6, 219-241.

[Sta87] L. Staiger, Research in the Theory of ω-Languages, J. Inform. Process. Cybernetics EIK 23 (1987) 8/9, 415-439.

[Sta97] L. Staiger, ω-Languages, Chapter of the Handbook of Formal Languages, Vol 3, edited by G. Rozenberg and A. Salomaa, Springer-Verlag, Berlin, 1997.

[Tho90] W. Thomas, Automata on Infinite Objects, in: J. Van Leeuwen, ed., Handbook of Theorical Computer Science, Vol. B (Elsevier, Amsterdam, 1990), p. 133-191.

[Wad84] W.W. Wadge, Ph. D. Thesis, Berkeley, 1984.

[Wag79] K. Wagner, On Omega Regular Sets, Inform. and Control 43 (1979) p. 123-177.

[WY95] Th. Wilke and H. Yoo, Computing the Wadge Degree, the Lifschitz Degree and the Rabin Index of a Regular Language of Infinite Words in Polynomial Time, in: TAPSOFT’ 95: Theory and Practice of Software Development (eds. P.D. Mosses, M. Nielsen and M.I. Schwartzbach), L.N.C.S. 915, p. 288-302, 1995.