WADGE HIERARCHY OF OMEGA CONTEXT FREE LANGUAGES

Olivier Finkel Equipe de Logique Mathématique CNRS URA 753 et Université Paris 7 U.F.R. de Mathématiques 2 Place Jussieu 75251 Paris cedex 05, France. E Mail: finkel@logique.jussieu.fr

Abstract

The main result of this paper is that the length of the Wadge hierarchy of omega context free languages is greater than the Cantor ordinal ε_{0}, and the same result holds for the conciliating Wadge hierarchy, defined in [Dup99], of infinitary context free languages, studied in [Bea84a]. In the course of our proof, we get results on the Wadge hierarchy of iterated counter ω-languages, which we define as an extension of classical (finitary) iterated counter languages to ω-languages.

Keywords: omega context free languages; topological properties; Wadge hierarchy; conciliating Wadge hierarchy; infinitary context free languages; iterated counter ω-languages.

Contents

1 Introduction 2

2 ω-regular and ω-context free languages 4

3 Iterated counter ω-languages 9

4 Borel and Wadge hierarchies 13 5 Operations on conciliating sets 16

5.1 Conciliating sets . . . . . . . . . . . . . . . . . . . . . . . . . . 16 5.2 Operation of sum . . . . . . . . . . . . . . . . . . . . . . . . . 18 5.3 Operation A → A^{+} . . . . . . . . . . . . . . . . . . . . . . . . 19 5.4 Operation of multiplication by an ordinal < ω^{ω} . . . . . . . . 21 5.5 Operation of exponentiation . . . . . . . . . . . . . . . . . . . 25

6 Conciliating hierarchy of infinitary context free languages 29

7 Wadge hierarchy of omega context free languages 33

8 Concluding remarks and further work 39

1 Introduction

Since J.R. Büchi studied the ω-languages recognized by finite automata to prove the decidability of the monadic second order theory of one successor over the integers [Büc60a] the so called ω-regular languages have been intensively studied. See [Tho90] and [PP98] for many results and references.

As Pushdown automata are a natural extension of finite automata, R. S. Cohen and A. Y. Gold [CG77] , [CG78] and M. Linna [Lin76] studied the ω-languages accepted by omega pushdown automata, considering various acceptance conditions for omega words. It turned out that the omega languages accepted by omega pushdown automata were also those generated by context free grammars where infinite derivations are considered , also studied by M. Nivat [Niv77] ,[Niv78] and L. Boasson and M. Nivat [BN80]. These languages were then called the omega context free languages (ω-CFL). See also Staiger’s paper [Sta97] for a survey of general theory of ω-languages, including more powerful accepting devices , like Turing machines.

Topological properties of ω-regular languages were first studied by L. H. Landweber in [Lan69] where he showed that these languages are boolean combination of G_{δ} sets and that one can decide whether a given ω-regular language is in a given Borel class. It turned out that an ω-regular language is in the class G_{δ} iff it is accepted by a deterministic Büchi automaton. These results have been extended to deterministic pushdown automata in [Lin77][Fin99a]. But (non deterministic ) omega context free languages exhaust the hierarchy of Borel sets of finite rank and it is undecidable to determine the Borel rank of an ω-CFL [Fin99a].

The hierarchy induced on ω-regular languages by the Borel Hierarchy was refined in [Bar92] and [Kam85] but K. Wagner had found the most refined one, now called the Wagner hierarchy and which is the hierarchy induced on ω-regular languages by the Wadge Hierarchy of Borel sets [Wag79].

This paper is mainly a study of the Wadge hierarchy of context free and iterated counter ω-languages:

We study iterated counter ω-languages which are an extension of the well known iterated counter languages to ω-languages. The class of iterated counter languages is divided into an infinite hierarchy of subclasses of the class of context free languages which can be defined by means of substitution by counter languages or by some restrictions on the pushdown automaton: the words in the pushdown store always belong to a bounded language in the form (z_{k})^{⋆}...(z_{2})^{⋆}(z_{1})^{⋆}Z_{0}, where {Z_{0}, z_{1}, ..., z_{k}} is the pushdown alphabet [Ber79][ABB96]. Thus these automata are X-automata in the sense of J. Engelfriet and H. J. Hoogeboom who initiated the study of general storage type for machines reading infinite words [EH93]. The study of topologically defined hierarchies of ω-languages accepted by such X-automata is asked by W. Thomas and H. Lescow [LT94].

To study the Wadge hierarchy of these languages, we shall use results of J. Duparc about the Wadge hierarchy of Borel sets. In [Dup99] [Dup95a] he gave a normal form of Borel sets of finite rank, i.e. an inductive construction of a Borel set of every given degree in the Wadge hierarchy of Borel sets of finite rank. In the course of the proof he studied the concilating hierarchy which is a hierarchy of sets of finite and infinite sequences. The conciliating hierarchy is closely related 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 D. Beauquier considered these languages as process behaviours which may terminate or not, as for transition systems studied in [AN82]. We continue this study, giving results on the conciliating hierarchy of infinitary iterated counter languages and showing that the length of the conciliating hierarchy of infinitary context free languages is greater than the Cantor ordinal ε_{0}.

Then we study the Wadge hierarchy of omega context free languages, showing that the length of the Wadge hierarchy of k-iterated counter languages is greater than the ordinal ω(k+2) obtained by k+2 iterations of the operation of ordinal exponentiation of base ω. More precisely ω(0) = 1 and for each integer n ≥ 0, ω(n + 1) = ω^{ω(n)}. We then deduce that the Wadge hierarchy of omega context free languages has length greater than ε_{0} which is a much larger ordinal than: ω^{ω} which is the length of the hierarchy of ω-regular languages, [Wag79], and ω^{(ω^{2})} which is the length of the hierarchy of deterministic context free ω-languages, [Dup99][Fin99b].

In section 2, we first review some above definitions and results about ωregular, ω-context free languages, and infinitary context free languages.

In section 3, we extend the definition of (k-) iterated counter (finitary) languages to ω-languages and we show that these latter languages verify some characterizations by means of automata with (k-) iterated counter storage type as well as by means of omega Kleene closure of finitary languages.

In section 4, we recall some basic facts about Borel and Wadge hierarchies and we prove that the Wadge hierarchy of ω-context free languages is non effective.

In section 5, we introduce Duparc’s operations on conciliating sets and we investigate closure properties, with regard to these operations, of classes of iterated counter infinitary languages.

In section 6, we apply preceding properties to the study of the conciliating hierarchy of infinitary context free languages.

In section 7, we prove results about the length of the Wadge hierarchies of ω-context free languages and of iterated counter ω-languages.

2 ω-regular and ω-context free languages

We assume the reader to be familiar with the theory of formal languages and of ω-regular languages, see for example [HU69] ,[Tho90]. We first recall some of the definitions and results concerning ω-regular and ω-context free languages and omega pushdown automata as presented in [Tho90] [CG77] , [CG78]. When Σ is a finite alphabet, a finite string (word) over Σ is any sequence x = x_{1} … x_{k} , where x_{i} ∈ Σ for i = 1, …, k ,and k is an integer ≥ 1. The length of x is k, denoted by |x|.

If |x| = 0 , x is the empty word denoted by λ. we write x(i) = x_{i} and x[i] = x(1) … x(i) for i ≤ k and x[0] = λ. Σ^{⋆} is the set of finite words over Σ. The first infinite ordinal is ω. An ω-word over Σ is an ω -sequence a_{1} … a_{n} …, where a_{i} ∈ Σ, ∀i ≥ 1. When σ is an ω-word over Σ, we write σ = σ(1)σ(2) … σ(n) … and σ[n] = σ(1)σ(2) … σ(n) the finite word of length n, prefix of σ. The set of ω-words over the alphabet Σ is denoted by Σ^{ω}. An ω-language over an alphabet Σ is a subset of Σ^{ω}.

The usual concatenation product of two finite words u and v is denoted u.v (and sometimes just uv). This product is extended to the product of a finite word u and an ω-word v: the infinite word u.v is then the ω-word such that: (u.v)(k) = u(k) if k ≤ |u| , and (u.v)(k) = v(k − |u|) if k > |u|.

For V ⊆ Σ^{⋆}, V^{ω} = {σ = u_{1} … u_{n} … ∈ Σ^{ω}/u_{i} ∈ V, ∀i ≥ 1} is the ω-power of V. 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, but when A = B ∪ C with B ⊆ Σ^{⋆} and C ⊆ Σ^{ω} we shall use the notation B^{−} for Σ^{⋆} − B and C^{−} for Σ^{ω} − C when this will be clear from the context.

The prefix relation is denoted ⊑: the finite word u is a prefix of the finite word v (denoted u ⊑ v) if and only if there exists a (finite) word w such that v = u.w. This definition is extended to finite words which are prefixes of ω-words: the finite word u is a prefix of the ω-word v (denoted u ⊑ v) iff there exists an ω-word w such that v = u.w.

Definition 2.1 : A finite state machine (FSM) is a quadruple 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 δ is a mapping from K × Σ into 2^{K} . A FSM is called deterministic (DFSM) iff : δ : K × Σ → K. A Büchi automaton (BA) is a 5-tuple M = (K, Σ, δ, q_{0}, F) where M′ = (K, Σ, δ, q_{0}) is a finite state machine and F ⊆ K is the set of final states. A Muller automaton (MA) is a 5-tuple M = (K, Σ, δ, q_{0}, F) where M′ = (K, Σ, δ, q_{0}) is a FSM and F ⊆ 2^{K} is the collection of designated state sets. A Büchi or Muller automaton is said deterministic if the associated FSM is deterministic.

Let σ = a_{1}a_{2} … a_{n} … be an ω-word over Σ. A sequence of states r = q_{1}q_{2} … q_{n} … is called an (infinite) run of M = (K, Σ, δ, q_{0}) on σ, starting in state p, iff: 1) q_{1} = p and 2) for each i ≥ 1, q_{i+1} ∈ δ(q_{i}, a_{i}). In case a run r of M on σ starts in state q_{0}, we call it simply ”a run of M on σ ” . For every (infinite) run r = q_{1}q_{2} … q_{n} … of M, In(r) is the set of states in K entered by M infinitely many times during run r: In(r) = {q ∈ K/{i ≥ 1/q_{i} = q} is infinite }. For M = (K, Σ, δ, q_{0}, F) a BA , the ω-language accepted by M is L(M) = {σ ∈ Σ^{ω} / there exists a run r of M on σ such that In(r) ∩ F ≠ ∅}. For M = (K, Σ, δ, q_{0}, F) a MA, the ω-language accepted by M is L(M) = {σ ∈ Σ^{ω} / there exists a run r of M on σ such that In(r) ∈ F }.

The classical result of R. Mc Naughton [MaN66] established that the expressive power of deterministic MA (DMA) is equal to the expressive power of non deterministic MA (NDMA) which is also equal to the expressive power of non deterministic BA (NDBA) . There is also a characterization of the languages accepted by MA by means of the ”ω-Kleene closure” which we give now the definition:

Definition 2.2 For any family L of finitary languages over the alphabet Σ, the ω-Kleene closure of L, is :

ω − KC(L) = {∪_{i=1}^{n}U_{i}.V_{i}^{ω}/U_{i}, V_{i} ∈ L, ∀i ∈ [1, n]}

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

1. L belongs to ω − KC(REG) , where REG is the class of (finitary) regular languages.

2. There exists a DMA that accepts L.

3. There exists a MA that accepts L.

4. There exists a BA that accepts L.

An ω-language L satisfying one of the conditions of the above Theorem is called an ω-regular language (or regular ω-language). The class of ωregular languages will be denoted by REG_{ω}.

We now define the pushdown machines and the classes of ω-context free languages.

Definition 2.4 A pushdown machine (PDM) is a 6-tuple M = (K, Σ, Γ, δ, q_{0}, Z_{0}), where K is a finite set of states, Σ is a finite input alphabet, Γ is a finite pushdown alphabet, q_{0} ∈ K is the initial state, Z_{0} ∈ Γ is the start symbol, and δ is a mapping from K × (Σ ∪ {λ}) × Γ to finite subsets of K × Γ^{⋆} . If γ ∈ Γ^{+} describes the pushdown store content, the leftmost symbol will be assumed to be on ” top” of the store. A configuration of a PDM is a pair (q, γ) where q ∈ K and γ ∈ Γ^{⋆}. For a ∈ Σ ∪ {λ}, α, γ ∈ Γ^{⋆} and Z ∈ Γ, if (p, β) is in δ(q, a, Z), then we write a : (q, Zγ) ↦_{M} (p, βγ). ↦_{M}^{⋆} is the transitive and reflexive closure of ↦_{M}. (The subscript M will be omitted whenever the meaning remains clear).

Let σ = a_{1}a_{2} … a_{n} be a finite word over Σ. A (finite) sequence of configurations r = (q_{i}, γ_{i})_{1≤i≤m} is called a complete run of M on σ, starting in configuration (p, γ), iff:

1. (q_{1}, γ_{1}) = (p, γ)

2. for each i ∈ [1, m−1], there exists b_{i} ∈ Σ∪{λ} satisfying b_{i} : (q_{i}, γ_{i}) ↦_{M} (q_{i+1}, γ_{i+1}) such that a_{1}a_{2} … a_{n} = b_{1}b_{2} … b_{m}

Let σ = a_{1}a_{2} … a_{n} … be an ω-word over Σ. An infinite sequence of configurations r = (q_{i}, γ_{i})_{i≥1} is called a complete run of M on σ, starting in configuration (p, γ), iff:

1. (q_{1}, γ_{1}) = (p, γ)

2. for each i ≥ 1, there exists b_{i} ∈ Σ ∪ {λ} satisfying b_{i} : (q_{i}, γ_{i}) ↦_{M} (q_{i+1}, γ_{i+1}) such that a_{1}a_{2} … a_{n} … = b_{1}b_{2} … b_{n} …

As for FSM, for every such run, In(r) is the set of all states entered infinitely often during run r. A complete run r of M on σ , starting in configuration (q_{0}, Z_{0}), will be simply called ” a run of M on σ ”.

Definition 2.5 A Büchi pushdown automaton (BPDA) is a 7-tuple M = (K, Σ, Γ, δ, q_{0}, Z_{0}, F) where M′ = (K, Σ, Γ, δ, q_{0}, Z_{0}) is a PDM and F ⊆ K is the set of final states. The ω-language accepted by M is L(M) = {σ ∈ Σ^{ω} / there exists a complete run r of M on σ such that In(r) ∩ F ≠ ∅}.

Definition 2.6 A Muller pushdown automaton (MPDA) is a 7-tuple M = (K, Σ, Γ, δ, q_{0}, Z_{0}, F) where M′ = (K, Σ, Γ, δ, q_{0}, Z_{0}) is a PDM and F ⊆ 2^{K} is the collection of designated state sets. The ω-language accepted by M is L(M) = {σ ∈ Σ^{ω} / there exists a complete run r of M on σ such that In(r) ∈ F }.

Remark 2.7 We consider here two acceptance conditions for ω-words , the Büchi and the Muller acceptance conditions, respectively denoted 2-acceptance and 3-acceptance in [Lan69] and in [CG78] and (inf, ⊓) and (inf, =) in [Sta97].

Remark 2.8 Without loss of generality we can always assume that the pushdown alphabet is Γ = {Z_{0}} ∪ Γ′ where Γ′ does not contain the symbol Z_{0}. And we can assume that the start symbol remains, during any finite or infinite computation, at the bottom of the store, and appears only there, i.e. that the content of the pushdown store is always in the form γZ_{0} where γ ∈ (Γ − {Z_{0}})^{⋆}.

R.S. Cohen and A.Y. Gold, and independently M. Linna, established a characterization Theorem for ω-CFL:

Theorem 2.9 Let CF be the class of context free (finitary) languages. Then for any ω-language L the following three conditions are equivalent:

1. L ∈ ω − KC(CF).

2. There exists a BP DA that accepts L.

3. There exists a MP DA that accepts L.

In [CG77] are also studied the ω-languages generated by ω-context free grammars and it is shown that each of the conditions 1), 2), and 3) of the above Theorem is also equivalent to: 4) L is generated by a context free grammar G by leftmost derivations. These grammars are also studied in [Niv77] , [Niv78]. Then we can let the following definition:

Definition 2.10 An ω-language is an ω-context free language (ω-CFL) (or context free ω-language) iff it satisfies one of the conditions of the above Theorem.

If finite and infinite words are viewed as process behaviours, it is natural to consider the infinitary languages (containing finite and infinite words) recognized by transition systems [AN82]. the infinitary languages accepted by pushdown machines have been studied in [Bea84a], [Bea84b]. A pushdown machine M = (K, Σ, Γ, δ, q_{0}, Z_{0}) is given with subsets K_{1} and K_{2} of K: K_{1} is used for acceptation of finite words by final states (in K_{1}) and K_{2} is used for acceptation of ω-words by a Büchi condition with the set K_{2} as set of final states. The set of (finite or infinite) words accepted by the pushdown machine in such a way is the union of a finitary context free language and of an ω-CFL [Bea84a]. Then we let the following:

Definition 2.11 Let X be a finite alphabet. A subset L of X^{≤ω} is said to be an infinitary context free language iff there exist a finitary context free language L_{1} ⊆ X^{⋆} and an ω-CFL L_{2} ⊆ X^{ω} such that L = L_{1} ∪ L_{2}.

3 Iterated counter ω-languages

Recall first that a rational cone is a class of (finitary) languages which is closed under morphism, inverse morphism, and intersection with a rational language (or, equivalently to these three properties, closed under rational transduction), [Ber79].

Definition 3.1 ([Lat83]) Let Rocl (restricted one counter languages) be the family of (finitary) languages accepted by pushdown automata, with a pushdown alphabet containing only one symbol which is the start symbol Z_{0}, by empty storage and accepting states. It is also the rational cone generated by the semi-Dyck language D_{1}^{′⋆} over one pair of parentheses.

We consider now a pushdown automaton with a pushdown alphabet in the form Γ = {Z_{0}, a} (Z_{0} is the bottom symbol as in the remark 2.8 and it always remains at the bottom of the pushdown store). It is called a one counter automaton. The languages accepted by such automata have been much studied. It turned out that these languages are obtained by substituting languages of Rocl in languages of REG:

Definition 3.2 ([Lat83][Ber79]) Let OCL be the family of (finitary) languages accepted by one counter automata by final states.

Recall now the definition of substitution in languages: A substitution f is defined by a mapping Σ → P (Γ^{⋆}), where Σ = {a_{1}, …, 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 Γ. Now this mapping is extended in the usual manner to finite words: f(x(1) … x(n)) = {u_{1} … u_{n} / u_{i} ∈ f(x(i)), ∀i ∈ [1; n]}, where x(1), …, x(n) are letters in Σ. And to finitary languages L ⊆ Σ^{⋆}: f(L) = ∪_{x∈L}f(x). Let ℂ be a family of languages, if ∀i ∈ [1; n] the language L_{i} belongs to ℂ the substitution f is called a ℂ-substitution. Define then the operation □ on families of languages: Let ℂ and 𝔻 be two families of (finitary) languages, then:

ℂ □ 𝔻 = {f(L) / L ∈ ℂ and f is a 𝔻 − substitution}

Proposition 3.3

OCL = REG□Rocl

In fact the operation of substitution gives rise to an infinite hierarchy of context free finitary languages defined as follows:

Definition 3.4 Let OCL(0) = REG, OCL(1) = OCL and OCL(k + 1) = OCL(k)□OCL for k ≥ 1.

It is well known that the hierarchy given by the families of languages OCL(k) is a strictly increasing hierarchy. And there exists a characterization of these languages by means of automata:

Proposition 3.5 ([ABB96]) A language A is in OCL(k) iff it is recognized (by accepting states) by a pushdown automaton such that, during any computation, the words in the pushdown store remain in a bounded language in the form (z_{k})^{⋆} … (z_{2})^{⋆}(z_{1})^{⋆}Z_{0}, where {Z_{0}, z_{1}, …, z_{k}} is the pushdown alphabet. The union

ICL = ∪_{k≥1}OCL(k)

is called the family of iterated counter languages.

In order to generalize these results to languages of ω-words, we first define k-iterated counter pushdown machines:

Definition 3.6 Let M′ = (K, Σ, Γ, δ, q_{0}, Z_{0}) be a PDM. If, during any computation, the words in the pushdown store remain in a bounded language in the form (z_{k})^{⋆} … (z_{2})^{⋆}(z_{1})^{⋆}Z_{0}, where {Z_{0}, z_{1}, …, z_{k}} is the pushdown alphabet, the PDM M is said to be a k-iterated counter pushdown machine, and this leads in a natural manner to the definition of k-iterated counter pushdown automata (reading finite words) and k-iterated counter BPDA and k-iterated counter MPDA (reading infinite words).

We have seen that the finitary languages accepted by k-iterated counter pushdown automata have a nice characterization: they form the class OCL(k). Considering now automata reading ω-words, the following result holds:

Theorem 3.7 Let OCL(k) be the class of k-iterated counter (finitary) languages, for an integer k ≥ 1. Then for any ω-language L the following three conditions are equivalent:

1. L ∈ ω − KC(OCL(k)).

2. There exists a k-iterated counter BP DA that accepts L.

3. There exists a k-iterated counter MP DA that accepts L.

Remark 3.8 This result remains true for k = 0, and it is in fact the characterization Theorem 2.3 of ω-regular languages, with the convention that a 0-iterated counter PDA is a finite automaton (because the word in the pushdown store is then always Z_{0} where Z_{0} is the bottom symbol)

Proof of 2 ↔ 3. The k-iterated counter Büchi and Muller P DA considered here are non deterministic and then the expresssive power of k-iterated counter Büchi P DA is the same as the expresssive power of k-iterated counter Muller P DA. The idea of the proof is the same as for the general case of pushdown automata, [Sta97]. And in fact this is also true for a general storage type as considered in [EH93] and k-iterated counter storage type is a particular case of this result. □

Proof of 2 ↔ 1. It is similar to the proof of the equivalence 2 ↔ 1 of Theorem 2.9 given in [Sta97], replacing finitary context free languages by languages in OCL(k) and pushdown automata by k-iterated counter PDA.

□

Then we can let the following definition:

Definition 3.9 An ω-language is a k-iterated counter ω-language (ω-k-ICL) iff it satisfies one of the conditions of the above Theorem. We denote k − ICL_{ω} the family of k-iterated counter ω-languages. An ω-language L is an iterated counter ω-language iff there exists an integer k such that L ∈ k − ICL_{ω}. And

ICL_{ω} = ⋃_{k≥1} k − ICL_{ω}

is the family of iterated counter ω-languages.

Remark 3.10 The class k−ICL_{ω} is defined by means of acceptation by non deterministic k-iterated counter PDA and thus it is closed under finite union. This property follows also from the characterization as the omega Kleene closure of the class OCL(k). And then the whole class ICL_{ω} is also closed under finite union because the hierarchy of the classes k − ICL_{ω} is increasing as the hierarchy of the OCL(k).

It is proved in [CG77] that if V ⊆ Σ^{⋆} is a finitary language over the alphabet Σ and a is a new letter not in Σ, then the ω-language V.a^{ω} is an ω-CFL iff the language V is a context free (finitary) language. This result can be extended to the class k − ICL_{ω} in the following form:

Proposition 3.11 Let V ⊆ Σ^{⋆} be a finitary language over the alphabet Σ and a be a new letter not in Σ, then the ω-language V.a^{ω} is in k − ICL_{ω} iff the language V is in OCL(k).

Proof. In one direction it is obvious that if V is in OCL(k), then the ωlanguage V.a^{ω} is in ω − KC(OCL(k)) = k − ICL_{ω} because the language {a} is in OCL(k). In the other direction, let us assume that V.a^{ω} is in k − ICL_{ω} where V ⊆ Σ^{⋆} and a ∉ Σ. Then by Theorem 3.7 there exist some languages U_{i} and V_{i} in OCL(k), 1 ≤ i ≤ n, such that

V.a^{ω} = ⋃_{i=1}^{n} U_{i}.V_{i}^{ω}

But then for each i ∈ [1, n], V_{i} ⊆ {a^{n} / n ≥ 1}. Thus if U′_{i} is the image of U_{i} by the erasing morphism which just erases the letters a, it holds that

(⋃_{i=1}^{n} U′_{i}) = V

But OCL(k) is closed under morphism because of the more general result that it is closed under regular substitution, then U′_{i} is in OCL(k) for each integer i ∈ [1, n]. And OCL(k) is closed under finite union (because it is defined by non deterministic machines) then ⋃_{i=1}^{n} U′_{i} = V is in OCL(k). □

From this result one can deduce that the hierarchy of the classes k − ICL_{ω} is strictly increasing and strictly included in the class CF L_{ω}:

Theorem 3.12 For each integer k ≥ 0, the following inclusion is strict: k − ICL_{ω} ⊊ (k + 1) − ICL_{ω}, and the whole family of iterated counter ωlanguages is strictly included into the family of omega context free languages: ICL_{ω} ⊊ CF L_{ω}.

Proof. It follows directly from the above proposition and the fact that for each integer k ≥ 0, OCL(k) ⊊ OCL(k + 1) and ICL ⊊ CF L. □

As in the general case of pushdown machines we can consider together finite and infinite runs of a k-iterated counter pushdown machine given with two state sets K_{1} and K_{2} (one is used for the acceptation of finite words by final states and the other for acceptation of ω-words by final states using a Büchi acceptance condition) and in a similar manner we let the following:

Definition 3.13 Let X be a finite alphabet. A subset L of X^{≤ω} is said to be an infinitary k-iterated counter language (or k-iterated counter (≤ ω)-language) iff there exist a finitary language L_{1} ∈ OCL(k) and an ω-language L_{2} ∈ k − ICL_{ω} such that L = L_{1} ∪ L_{2}. The set of k-iterated counter (≤ ω)-languages is denoted k − ICL_{≤ω}.

4 Borel and Wadge hierarchies

We assume the reader to be familiar with basic notions of topology which may be found in [LT94] [Kur66] and with the elementary theory of ordinals, including the operations of multiplication and exponentiation, which may be found in [Sie65].

Topology is an important tool for the study of ω-languages, and leads to characterization of several classes of ω-languages. 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. The class of open sets of X^{ω} will be denoted by G or by Σ_{1}^{0}. The class of closed sets will be denoted by F or by Π_{1}^{0}. Define now the next classes of the Borel Hierarchy:

Definition 4.1 The classes Σ_{n}^{0} and Π_{n}^{0} of the Borel Hierarchy on the topological space X^{ω} are defined as follows: Σ_{1}^{0} is the class of open sets of X^{ω}. Π_{1}^{0} is the class of closed sets of X^{ω}. Π_{2}^{0} or G_{δ} is the class of countable intersections of open sets of X^{ω}. Σ_{2}^{0} or F_{σ} is the class of countable unions of closed sets of X^{ω}. And for any integer n ≥ 1: Σ_{n+1}^{0} is the class of countable unions of Π_{n}^{0}-subsets of X^{ω}. Π_{n+1}^{0} is the class of countable intersections of Σ_{n}^{0}-subsets of X^{ω}. The Borel Hierarchy is also defined for transfinite levels. The classes Σ_{α}^{0} and Π_{α}^{0}, for a countable ordinal α, are defined in the following way ^{1}: For a successor ordinal (α + 1), the definition is as above for (n + 1). And for a limit ordinal α, Σ_{α}^{0} = Π_{α}^{0} = ∪_{γ<α}Σ_{γ}^{0}.

Recall some basic results about these classes:

Proposition 4.2 ([Mos80]) a) Σ_{α}^{0}∪Π_{α}^{0} ⊊ Σ_{α+1}^{0}∩Π_{α+1}^{0}, for each countable ordinal α.

b) A set W ⊆ X^{ω} is in the class Σ_{α}^{0} if and only if its complement W^{−} is in the class Π_{α}^{0}.

c) Σ_{α}^{0} − Π_{α}^{0} ≠ ∅ and Π_{α}^{0} − Σ_{α}^{0} ≠ ∅ hold for every countable successor ordinal α.

We shall say that a subset of X^{ω} is a Borel set of rank 1 iff it is in Σ_{1}^{0} ∪ Π_{1}^{0} and that it is a Borel set of rank α + 1 ≥ 2, for a countable ordinal α, iff it is in Σ_{α+1}^{0} ∪ Π_{α+1}^{0} but not in Σ_{α}^{0} ∪ Π_{α}^{0}.

Introduce now the Wadge Hierarchy which is in fact a huge refinement of the Borel hierarchy:

Definition 4.3 For E ⊆ X^{ω} and F ⊆ Y^{ω}, E is said 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 4.4 In the above definition, we consider that a subset E ⊆ X^{ω} is given together with the alphabet X.

Then we can define the Wadge class of a set F:

1In another presentation of the Borel hierarchy, as in [Mos80], when α is a limit ordinal, Σ_{α}^{0} (respectively Π_{α}^{0}) is the class we call here Σ_{α+1}^{0} (respectively Π_{α+1}^{0}), and our class Σ_{α}^{0} (respectively Π_{α}^{0}), which is simply the union of the preceding ones, does not appear.

Definition 4.5 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 Σ_{n}^{0} and Π_{n}^{0} is a Wadge class. And that a set F ⊆ X^{ω} is a Σ_{n}^{0} (respectively Π_{n}^{0})-complete set iff for any set E ⊆ Y^{ω}, E is in Σ_{n}^{0} (respectively Π_{n}^{0}) iff E ≤_{W} F. Σ_{n}^{0} (respectively Π_{n}^{0})-complete sets are thoroughly characterized in [Sta86].

Theorem 4.6 (Wadge) Up to the complement and ≡_{W}, the class of Borel subsets of X^{ω}, for X a finite alphabet, 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^{−}].

We shall here restrict our study to Borel sets of finite rank. And the Wadge hierarchy has then length ε^{1} where ε^{1} 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.

There is an effective version of the Wadge Hierarchy restricted to ω-regular languages:

Theorem 4.7 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. This hierarchy has been recently studied in [CP97] , [CP98] and [Sel98]. And it has an extension to omega deterministic context free languages which has length ω^{ω^{2}} [DFR99] [Dup99] [Fin99b].

The Wadge hierarchy restricted to ω-CFL is not effective: We have shown in [Fin99a] the following:

Theorem 4.8 Let n be an integer ≥ 1. Then it is undecidable whether an effectively given ω-CFL is in the class Σ_{n}^{0} ( repectively Π_{n}^{0}).

This result can be strengthened by showing the following:

Theorem 4.9 Let B be a Borel set of finite rank such that d_{W}^{0} B = α < ε^{1}. Then it is undecidable whether an effectively given ω-CFL L is in the Wadge class [B] of B, and it is undecidable whether d_{W}^{0} (L) ≤ α.

Proof. As above, the ordinals α_{n} are defined by α_{1} = ω_{1} and α_{n+1} = ω_{1}^{α_{n}} for n a non negative integer. If d_{W}^{0} (B) = α < ε^{1}, there exists an integer n_{B} ≥ 1 such that α < α_{n_{B}}. Recall that a Borel set L ⊆ X^{ω} is in the class Π_{n+1}^{0} or in the class Σ_{n+1}^{0} iff d_{W}^{0} (L) ≤ α_{n} [Dup99]. Return now to the proof of Theorem 7.2 of [Fin99a]. Let n be an integer ≥ 1. We had found a family of omega context free languages

(A_{X,Y}^{∼.n})^{d} = ((L_{X,Y} ∪ Σ^{⋆})^{∼.n})^{d}

over the alphabet {a, b, c, ↞_{1}, ↞_{2}, …, ↞_{n}, d} such that (A_{X,Y}^{∼.n})^{d} is either {a, b, c, ↞_{1}, ↞_{2}, …, ↞_{n}, d}^{ω} or an ω-language which is neither a Π_{n+1}^{0}- subset nor a Σ_{n+1}^{0}-subset of {a, b, c, ↞_{1}, ↞_{2}, …, ↞_{n}, d}^{ω}. In the first case d_{W}^{0} ((A_{X,Y}^{∼.n})^{d}) = d_{W}^{0} ({a, b, c, ↞_{1}, ↞_{2}, …, ↞_{n}, d}^{ω}) = 1, (because the Wadge degree of Σ^{ω} considered as an ω-language over the alphabet Σ is always 1).

And in the second case d_{W}^{0} ((A_{X,Y}^{∼.n})^{d}) > α_{n}. Take now the integer n_{B} and consider the family of omega context free languages

(A_{X,Y}^{∼.n_{B}})^{d}

Then there are two cases:

a) d_{W}^{0} ((A_{X,Y}^{∼.n_{B}})^{d}) = 1

b) d_{W}^{0} ((A_{X,Y}^{∼.n_{B}})^{d}) > α_{n_{B}} > α

But one cannot decide which case holds. □

5 Operations on conciliating sets

5.1 Conciliating sets

We sometimes consider here subsets of X^{⋆} ∪ X^{ω} = X^{≤ω}, for an alphabet X, which are called conciliating sets in [Dup99] [Dup95a]. In order to give a ”normal form” of Borel sets in the Wadge hierarchy, J. Duparc studied the Conciliating hierarchy which is a hierarchy over conciliating sets closely related to the Wadge hierarchy. The two hierarchies are connected via the following correspondance:

First define A^{d} for A ⊆ X_{A}^{≤ω} and d a letter not in X_{A}:

A^{d} = {x ∈ (X_{A} ∪ {d})^{ω} / x(/d) ∈ A}

where x(/d) is the sequence obtained from x when removing every occurrence of the letter d.

Then for A ⊆ X_{A}^{≤ω}, A^{d} is always a non self dual subset of (X_{A} ∪ {d})^{ω} and the correspondance A → A^{d} induces an isomorphism between the conciliating hierarchy and the Wadge hierarchy of non self dual sets. Hence we shall first concentrate on non self dual sets as in [Dup99] and we shall use the following definition of the Wadge degrees which is a slight modification of the previous one:

Definition 5.1 • d_{w}(∅) = d_{w}(∅^{−}) = 1

• 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 5.2 Let A ⊆ X_{A}^{≤ω} be a conciliating set over the alphabet X_{A} such that A^{d} is a Borel set. The conciliating degree of A is:

d_{c}(A) = d_{w}(A^{d})

Prove now some properties of the correspondance A → A^{d} when iterated counter languages are considered:

Proposition 5.3 a) if A ⊆ Σ^{⋆} is a (finitary) language in OCL(k), then A^{d} is in k − ICL_{ω}.

b) if A ⊆ Σ^{ω} is in k − ICL_{ω}, then A^{d} is in k − ICL_{ω}.

c) If A is the union of a finitary language in OCL(k), and of an ωlanguage in k−ICL_{ω}, over the same alphabet Σ, then A^{d} is a k-iterated counter ω-language over the alphabet Σ ∪ {d}.

Proof of a). Let A ⊆ Σ^{⋆} be a language in OCL(k). Substitute first the language (d^{⋆}).a for each letter a ∈ Σ. In such a way we obtain another language A′ in OCL(k) because OCL(k) is closed under substitution by regular languages and the languages (d^{⋆}).a are regular. Indeed A^{d} = A′.d^{ω} hence A^{d} is in k − ICL_{ω} because ω − KC(OCL(k)) = k − ICL_{ω} by Theorem 3.7. □

Proof of b). Let A ⊆ Σ^{ω} be an ω-language in k − ICL_{ω}. The ω-language A^{d} is obtained from A by substituting the language (d^{⋆}).a for each letter a ∈ Σ in the words of A. But the class k − ICL_{ω} is closed under λ-free regular substitution because OCL(k) is closed under regular substitution hence A^{d} is in k − ICL_{ω}. □

Proof of c). Let A and B be subsets of Σ^{≤ω} for a finite alphabet Σ. Then we easily see that if C = A ∪ B, C^{d} = A^{d} ∪ B^{d} holds. c) is now an easy consequence of a) and b) because k − ICL_{ω} is closed under union. □

And we now introduce several operations over conciliating sets:

5.2 Operation of sum

Definition 5.4 ([Dup99]) Assume that X_{A} ⊆ X_{B} and that X_{B} − X_{A} contains 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 = 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:

Proposition 5.5 Let X_{A} ⊆ X_{B} and 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 5.6 As indicated in Remark 5 of [Dup99], when A ⊆ X_{A}^{≤ω} and X is a finite alphabet, it is easy to build A′ ⊆ (X_{A} ∪X)^{≤ω}, such that (A′)^{d} ≡_{W} A^{d}. In fact A′ can be defined as follows: for α ∈ (X_{A}∪X)^{≤ω}, let α ∈ A′ ↔ α′ ∈ A, where α′ is α except each letter not in X_{A} 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 language in OCL(k) and of an ω-language in k − ICL_{ω}:

Proposition 5.7 Let X_{A} ⊆ X_{B} such that X_{B} − X_{A} contains at least two elements and that {X_{+}, X_{−}} is a partition of X_{B} − X_{A} in two non empty sets. Assume A ⊆ X_{A}^{≤ω} and A, A^{−} ∈ k − ICL_{≤ω}, and B ⊆ X_{B}^{≤ω} and B, B^{−} ∈ k − ICL_{≤ω}, for an integer k ≥ 0. Then B + A is also in the form D_{1} ∪ D_{2} where D_{1} is in OCL(k) and D_{2} is in k − ICL_{ω} and its complement X_{B}^{≤ω} − (B + A) = (X_{B}^{⋆} − D_{1}) ∪ (X_{B}^{ω} − D_{2}) is also in that form.

Proof. Let A and B be two conciliating sets as in the hypothesis of the above proposition: assume A = A_{1} ∪ A_{2} where A_{1} and X_{A}^{⋆} − A_{1} are in OCL(k) and A_{2} and X_{A}^{ω} −A_{2} are in k −ICL_{ω}, for an integer k ≥ 0. And assume also that B = B_{1} ∪ B_{2} where B_{1} and X_{B}^{⋆} − B_{1} are in OCL(k) and B_{2} and X_{B}^{ω} − B_{2} are in k −ICL_{ω}. By definition it holds that B +A = A∪X_{A}^{⋆}.X_{+}.B ∪X_{A}^{⋆}.X_{−}.B^{−}.

Then the finite words in B + A form the language D_{1} = A_{1} ∪ X_{A}^{⋆}.X_{+}.B_{1} ∪ X_{A}^{⋆}.X_{−}.B_{1}^{−} and the ω-words in B + A form the ω-language D_{2} = A_{2} ∪ X_{A}^{⋆}.X_{+}.B_{2} ∪ X_{A}^{⋆}.X_{−}.B_{2}^{−}. OCL(k) is closed under concatenation product and finite union hence A_{1} ∪ X_{A}^{⋆}.X_{+}.B_{1} ∪ X_{A}^{⋆}.X_{−}.B_{1}^{−} is in OCL(k). Similarly k − ICL_{ω} is closed under left concatenation by regular (finitary) languages and finite union hence A_{2} ∪ X_{A}^{⋆}.X_{+}.B_{2} ∪ X_{A}^{⋆}.X_{−}.B_{2}^{−} is in k − ICL_{ω}.

It remains to check that X_{B}^{≤ω} − (B + A) is in the same form. But X_{B}^{≤ω} − (B +A) = (X_{B}^{⋆} −D_{1})∪(X_{B}^{ω} −D_{2}), and X_{B}^{⋆} −D_{1} = (X_{A}^{⋆} −A_{1})∪X_{A}^{⋆}.X_{+}.B_{1}^{−} ∪ X_{A}^{⋆}.X_{−}.B_{1} is in OCL(k) because (X_{A}^{⋆} −A_{1}), B_{1} and X_{B}^{⋆} −B_{1} are in OCL(k). And X_{B}^{ω} −D_{2} = (X_{A}^{ω} −A_{2})∪X_{A}^{⋆}.X_{+}.B_{2}^{−} ∪X_{A}^{⋆}.X_{−}.B_{2}, is in k −ICL_{ω} because (X_{A}^{ω} − A_{2}), B_{2} and X_{B}^{ω} − B_{2} are in k − ICL_{ω}.

5.3 Operation A → A^{+}

Definition 5.8 Let A ⊆ X_{A}^{≤ω} and O_{−}, O_{+} be two new letters not in X_{A}. Let X = X_{A} ∪ {O_{−}, O_{+}}. Then A^{+} is the conciliating set over the alphabet X defined by A^{+} = A ∪ X^{⋆}.O_{+}.A ∪ X^{⋆}.O_{−}.(X_{A}^{≤ω} − A).

This operation is connected with the ordinal multiplication by ω_{1}:

Proposition 5.9 Let A ⊆ X_{A}^{≤ω} be a conciliating set over the alphabet X_{A} such that A^{d} is a Borel set. Then (A^{+})^{d} is a Borel set and:

d_{c}(A^{+}) = d_{c}(A).ω_{1}

Consider now conciliating sets which are unions of a finitary language in OCL(k) and of an ω-language in k − ICL_{ω}:

Proposition 5.10 Assume A = A_{1} ∪ A_{2} where A_{1} and X_{A}^{⋆} − A_{1} are in OCL(k) and A_{2} and X_{A}^{ω} − A_{2} are in k − ICL_{ω}, for an integer k ≥ 0. Then A^{+} and (A^{+})^{−} are also unions of a finitary language in OCL(k) and of an ω-language in k − ICL_{ω}.

Proof. Let A = A_{1} ∪ A_{2} where A_{1} and X_{A}^{⋆} − A_{1} are in OCL(k) and A_{2} and X_{A}^{ω}−A_{2} are in k−ICL_{ω}. By definition A^{+} = A∪X^{⋆}.O_{+}.A∪X^{⋆}.O_{−}.(X_{A}^{≤ω}−A), so

A^{+} = [A_{1}∪X^{⋆}.O_{+}.A_{1}∪X^{⋆}.O_{−}.(X_{A}^{⋆}−A_{1})]∪[A_{2}∪X^{⋆}.O_{+}.A_{2}∪X^{⋆}.O_{−}.(X_{A}^{ω}−A_{2})]

But OCL(k) is closed under finite union and concatenation and k − ICL_{ω} is closed under finite union and left concatenation by finitary languages in REG. This implies that A^{+} is the union of a finitary language in OCL(k) and of an ω-language in k − ICL_{ω}.

Consider now

(A^{+})^{−} = (A^{−})^{+} ∪ (X_{A}^{⋆}.{O_{+}, O_{−}})^{ω}
□

Where (X_{A}^{⋆}.{O_{+}, O_{−}})^{ω} is the set of ω-words over the alphabet X_{A}∪{O_{+}, O_{−}} which contain infinitely many letters O_{+} or O_{−}. This ω-language is an ωregular language then it is in k − ICL_{ω} for any integer k ≥ 0. Then the same argument as for the case of A^{+} shows that (A^{−})^{+} is in the form V_{1} ∪ V_{2} with V_{1} ∈ OCL(k) and V_{2} ∈ k − ICL_{ω} and then (A^{+})^{−} is in the same form because k − ICL_{ω} is closed under union. □

The two above operations A, B → B + A and A → A^{+} permit to obtain ω-languages C of Wadge degrees in the form

d_{w}(C) = ω_{1}^{n_{k}}.m_{k} + ω_{1}^{n_{k−1}}.m_{k−1} + … + ω_{1}^{n_{1}}.m_{1}

where k > 0 is an integer, n_{k} > n_{k−1} > … > n_{1} ≥ 0 are integers and m_{k}, m_{k−1}, …, m_{1} are integers > 0.

For that it suffices to start with the emptyset ∅ (considered as a subset of X^{≤ω} where X is an alphabet containing n letters, n ≥ 2) and its complement X^{≤ω}. In fact the emptyset is given with the alphabet X so we start with infinitely many conciliating sets but for an alphabet X it always holds that:

d_{c}(∅) = d_{w}((∅)^{d}) = d_{w}((X^{≤ω})^{d}) = 1

Then take the closure of these conciliating sets under the two operations A, B → B + A and A → A^{+} and complementation. We obtain a family C_{0} of conciliating sets closed under complementation such that, for A ∈ C_{0}, A^{d} is an ω-regular language and d_{c}(A) = d_{w}(A^{d}) is in the above form. It is well known that these degrees are exactly those of ω-regular languages. Thus in such a way, for each non self dual ω-regular language B, we obtain an ω-language A^{d} (with A ∈ C_{0}) such that A^{d} is Wadge equivalent to B.

The Wadge hierarchy of ω-regular languages has length ω^{ω} and it has also the same length when it is restricted to non self dual sets. Hence the family C_{0} of conciliating sets provides a class C_{0}^{d} = {A^{d} / A ∈ C_{0}} of ω-languages such that the length of the Wadge hierarchy of C_{0}^{d} has length ω^{ω}.

5.4 Operation of multiplication by an ordinal < ω^{ω}

J. Duparc defined in [Dup99] another operation which is the multiplication by a countable ordinal, i.e. an ordinal < ω_{1}. We shall restrict here the study to the operation of multiplication by an ordinal < ω^{ω}. And these operations may be defined by defining first the multiplication by the ordinal ω.

Definition 5.11 Let A ⊆ X_{A}^{≤ω} be a conciliating set over the alphabet X_{A} and O_{+}, O_{−} be two new letters not in X_{A}, then A.ω is defined over the alphabet X_{A} ∪ {O_{+}, O_{−}} by:

A.ω = ⋃_{n≥1}(O^{+})^{n}.X_{A}.(X_{A}^{⋆}.{O_{+}, O_{−}})^{≤(n−1)}.X_{A}^{⋆}.(O_{+}.A ∪ O_{−}.A^{−})

Thus in a (finite or infinite) word of A.ω, the word has an initial prefix in the form (O^{+})^{n}.a for an integer n ≥ 1 and a letter a ∈ X_{A}, and then there are at most n more letters from {O_{+}, O_{−}} in the word and the last such letter determines whether the suffix following this last letter O_{+} or O_{−} is in A or in A^{−}.

Prove now that k-iterated counter languages are closed under this operation:

In the following proposition, we consider first:

In a) A ⊆ X_{A}^{⋆}, then A.ω is defined as in the preceding definition but with A^{−} = X_{A}^{⋆} − A. Thus here A.ω is a set of finite words.

In b) A ⊆ X_{A}^{ω}, then A.ω is defined as in the preceding definition but with A^{−} = X_{A}^{ω} − A. Thus here A.ω is a set of infinite words.

Proposition 5.12 a) If A ⊆ X_{A}^{⋆} is a (finitary) language in OCL(k) such that X_{A}^{⋆} − A is also in OCL(k), for an integer k ≥ 1, then A.ω and (A.ω)^{−} are in OCL(k).

b) If A ⊆ X_{A}^{ω} is in k − ICL_{ω} and X_{A}^{ω} − A is in k − ICL_{ω}, for an integer k ≥ 1, then A.ω and (A.ω)^{−} are in k − ICL_{ω}.

c) If A ⊆ X_{A}^{≤ω} and X_{A}^{≤ω} − A are unions of a language in OCL(k) and of an ω-language in k − ICL_{ω}, then A.ω and (A.ω)^{−} are also in that form.

Proof of a). Assume that A ⊆ X_{A}^{⋆} such that A ∈ OCL(k) and X_{A}^{⋆} − A ∈ OCL(k). It is clear that the language

⋃_{n≥1}(O^{+})^{n}.X_{A}.(X_{A}^{⋆}.{O_{+}, O_{−}})^{≤(n−1)}.X_{A}^{⋆}

is a one counter language in OCL(1).( The counter is first increased of 1 when the one counter automaton reads a letter O_{+} and after the first letter of X_{A} is read the counter is decreased when a letter O_{+} or O_{−} is read). But OCL(k) is closed under concatenation product and union hence A.ω is in OCL(k).

From the definition of A.ω, it holds that:

(A.ω)^{−} = (O_{+})^{⋆} ∪ ((O_{+})^{⋆}.O_{−} ∪ X_{A}).(X_{A} ∪ {O_{+}, O_{−}})^{⋆}

∪ ⋃_{n≥1}(O^{+})^{n}.X_{A}.(X_{A}^{⋆}.{O_{+}, O_{−}})^{≥(n+1)}.X_{A}^{⋆} ∪ (A^{−}).ω

But (O_{+})^{⋆} ∪ ((O_{+})^{⋆}.O_{−} ∪ X_{A}).(X_{A} ∪ {O_{+}, O_{−}})^{⋆} is a regular language and

⋃_{n≥1}(O^{+})^{n}.X_{A}.(X_{A}^{⋆}.{O_{+}, O_{−}})^{≥(n+1)}.X_{A}^{⋆}

is a one counter language thus it is in OCL(k) and so is (A^{−}).ω by similar arguments as for A.ω, hence the language (A.ω)^{−} is in OCL(k) because OCL(k) is closed under union. □

Proof of b). Assume A ⊆ X_{A}^{ω} is in k − ICL_{ω} such that X_{A}^{ω} − A is also in k − ICL_{ω}, for an integer k ≥ 1. The proof that A.ω ∈ k − ICL_{ω} is the same as for a) because k − ICL_{ω} is closed under left concatenation by languages in OCL(k) (and also in OCL(1) because k ≥ 1 and OCL(1) ⊆ OCL(k)) and by finite union because

k − ICL_{ω} = ω − KC(OCL(k))

by Theorem 3.7.

From the definition of A.ω, it holds that:

(A.ω)^{−} = (O_{+})^{ω} ∪ ((O_{+})^{⋆}.O_{−} ∪ X_{A}).(X_{A} ∪ {O_{+}, O_{−}})^{ω}

∪ ⋃_{n≥1}(O^{+})^{n}.X_{A}.(X_{A}^{⋆}.{O_{+}, O_{−}})^{(n+1)}.(X_{A} ∪ {O_{+}, O_{−}})^{ω} ∪ (A^{−}).ω

But (O_{+})^{ω} ∪ ((O_{+})^{⋆}.O_{−} ∪ X_{A}).(X_{A} ∪ {O_{+}, O_{−}})^{ω} is in REG_{ω} and

⋃_{n≥1}(O^{+})^{n}.X_{A}.(X_{A}^{⋆}.{O_{+}, O_{−}})^{(n+1)}.(X_{A} ∪ {O_{+}, O_{−}})^{ω}

and (A^{−}).ω are in k −ICL_{ω}, hence (A.ω)^{−} ∈ k −ICL_{ω} holds by finite union. □

Proof of c). Let A = A_{1} ∪ A_{2} where A_{1} and X_{A}^{⋆} − A_{1} are in OCL(k) and A_{2} and X_{A}^{ω} − A_{2} are in k − ICL_{ω}, for an integer k ≥ 1. Then, from the definition of A.ω, it holds that:

A.ω = A_{1}.ω ∪ A_{2}.ω

(A.ω)^{−} = [(X_{A} ∪ {O_{+}, O_{−}})^{⋆} − (A_{1}.ω)] ∪ [(X_{A} ∪ {O_{+}, O_{−}})^{ω} − (A_{2}.ω)]

hence c) follows from a) and b). □

From this operation A → A.ω over conciliating sets, we can inductively define the multiplication by an ordinal ω^{n} for an integer n ≥ 1:

Definition 5.13 Let A ⊆ X_{A}^{≤ω} be a conciliating set over the alphabet X_{A}. Then A.ω^{n} is inductively defined by:

a) A.ω is defined as above and

b) A.ω^{n+1} = (A.ω^{n}).ω for each integer n ≥ 1.

In order to extend this definition to every non null ordinal < ω^{ω}, remark that it is well known that each non null ordinal α < ω^{ω} has a Cantor normal form [Sie65]:

α = ω^{n_{k}}.m_{k} + ω^{n_{k−1}}.m_{k−1} + … + ω^{n_{1}}.m_{1}

where k > 0 is an integer, n_{k} > n_{k−1} > … > n_{1} ≥ 0 are integers and m_{k}, m_{k−1}, …, m_{1} are integers > 0.

Definition 5.14 Let A ⊆ X_{A}^{≤ω} be a conciliating set over the alphabet X_{A}. Then A.n is inductively defined by:

a) A.1 = A

b) A.(n + 1) = (A.n) + A for each integer n ≥ 1.

This allows to define A.(ω^{n_{k}}.m_{k}) for n_{k} ≥ 0 and m_{k} > 0. And the operation of sum previously defined leads to the inductive definition of:

A.(ω^{n_{k}}.m_{k}+ω^{n_{k−1}}.m_{k−1}+…+ω^{n_{1}}.m_{1}) = A.(ω^{n_{k}}.m_{k})+A.(ω^{n_{k−1}}.m_{k−1}+…+ω^{n_{1}}.m_{1})

These operations A → A.α satisfy the following:

Proposition 5.15 Let α be a non null ordinal < ω^{ω}, then: If A ⊆ X_{A}^{≤ω} and X_{A}^{≤ω} − A are unions of a language in OCL(k) and of an ω-language in k − ICL_{ω} (i.e. are in k − ICL_{≤ω}) , then A.α and (A.α)^{−} are also in k − ICL_{≤ω}.

Proof. It follows from the similar properties for the operations of sum and of multiplication by ω of propositions 5.7 and 5.12, because of the inductive definition of the operations A → A.α, for α < ω^{ω}, using the preceding operations A, B → A + B and A → A.ω. □

The operation A → A.α is related with the ordinal multiplication by α:

Proposition 5.16 Let α be a non null ordinal < ω^{ω}, and A ⊆ X_{A}^{≤ω} such that A^{d} is a Borel set, then (A.α)^{d} is a Borel set and:

d_{c}(A.α) = d_{c}(A).α

5.5 Operation of exponentiation

Definition 5.17 Let X_{A} be a finite alphabet and ↞∉ X_{A}, let X = X_{A}∪{↞}. Let x be a finite or infinite word over the alphabet X = X_{A} ∪ {↞}. Then x^{↞} is inductively defined by: λ^{↞} = λ, For a finite word u ∈ (X_{A} ∪ {↞})^{⋆}: (u.a)^{↞} = u^{↞}.a, if a ∈ X_{A}, (u. ↞)^{↞} = u^{↞} with its last letter removed if |u^{↞}| > 0, (u. ↞)^{↞} = λ if |u^{↞}| = 0, and for u infinite: (u)^{↞} = lim_{n∈ω}(u[n])^{↞}, where, given β_{n} and u in X_{A}^{⋆}, u ⊑ lim_{n∈ω} β_{n} ↔ ∃n∀p ≥ n β_{p}[|u|] = u.

Remark 5.18 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 ∈ X_{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^{ω}, if u = bb(↞ a)^{ω} then (u)^{↞} = b.

We can now define the operation A → A^{∼} of exponentiation of conciliating sets:

Definition 5.19 For A ⊆ X_{A}^{≤ω} and ↞ ∉ X_{A}, let X = X_{A} ∪ {↞} and A^{∼} = {x ∈ (X_{A} ∪ {↞})^{≤ω}/x^{↞} ∈ A}.

The operation ∼ is monotone with regard to the Wadge ordering and produce some sets of higher complexity, in the following sense:

Theorem 5.20 (Duparc [Dup99] ) a) For A ⊆ X_{A}^{≤ω} and B ⊆ X_{B}^{≤ω}, A^{d} and B^{d} borel sets, A^{d} ≤_{W} B^{d} ↔ (A^{∼})^{d} ≤_{W} (B^{∼})^{d}.

b) If A^{d} ⊆ (X_{A} ∪ {d})^{ω} is a Σ_{n}^{0}-complete (respectively Π_{n}^{0}-complete) set ( for an integer n ≥ 1 ), then (A^{∼})^{d} is a Σ_{n+1}^{0}-complete (respectively Π_{n+1}^{0}-complete) set.

Recall now the notion of cofinality of an ordinal which is an important notion in set theory [CK73]. 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

∀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(α) ≤ α

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 larger cofinalities.

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

Theorem 5.21 (Duparc [Dup99]) Let A ⊆ X_{A}^{≤ω} be a conciliating set such that A^{d} is a 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 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 ∼ with regard to k-iterated counter languages:

Theorem 5.22 Whenever A ⊆ X_{A}^{ω} is in k−ICL_{ω} , then A^{∼} ⊆ (X_{A}∪{↞})^{ω} is in (k + 1) − ICL_{ω} .

Proof. An ω-word σ ∈ A^{∼} may be considered as an ω-word σ^{↞} ∈ A to which we possibly add, before the first letter σ^{↞}(1) of σ^{↞} (respectively between two consecutive letters σ^{↞}(n) and σ^{↞}(n + 1) of σ^{↞}), a finite word v_{1} (respectively v_{n+1} ) where: v_{n+1} belongs to the context free (finitary) language L_{3} generated by the context free grammar with the following production rules: S → aS ↞ S with a ∈ X_{A}, S → a ↞ S with a ∈ X_{A}, S → λ (λ being the empty word). this language L_{3} corresponds to words where every letter of X_{A} has been removed after using the back space operation. And v_{1} belongs to the finitary language L_{4} = (↞)^{⋆}.(L_{3}.(↞)^{⋆})^{⋆}. This language corresponds to words where every letter of X_{A} has been removed after using the back space operation and this operation maybe has been used also when there was not any letter to erase. L_{3} is a one counter language i.e. L_{3} is in OCL (during a reading of a word the counter is increased when a letter of X_{A} is read and it is decreased when a letter ↞ is read). And for a ∈ X_{A}, the language L_{3}.a is also accepted by a one counter automaton. L_{4} is also in OCL because the class OCL is closed under star operation and concatenation product. Then we can state the following:

Lemma 5.23 Whenever A ⊆ X_{A}^{ω}, the ω-language A^{∼} ⊆ (X_{A} ∪ {↞})^{ω} is obtained by substituting in A the language L_{3}.a for each letter a ∈ X_{A}, where L_{3} is the one counter language defined above, and then making a left concatenation by the language L_{4}.

Let now A be an ω-language in k−ICL_{ω}, given by A = ⋃_{i=1}^{n} U_{i}.V_{i}^{ω} where U_{i} and V_{i} are in OCL(k). Then A^{∼} = ⋃_{i=1}^{n}(L_{4}.U′_{i}).V_{i}^{′ω}, where U′_{i} (respectively V′_{i}) is obtained by substituting the language L_{3}.a to each letter a ∈ X_{A} in U_{i} (respectively V_{i}). It holds that OCL(k)□OCL = OCL(k + 1), so U′_{i} and V′_{i} are in OCL(k + 1), and so is the language (L_{4}.U′_{i}) by concatenation product (because L_{4} ∈ OCL ⊆ OCL(k+1), and OCL(k+1) is closed under concatenation product). Hence the ω-language A^{∼} is in (k + 1) − ICL_{ω}, because ω − KC(OCL(k + 1)) = (k + 1) − ICL_{ω}.

Consider now subsets of X^{≤ω} in the form A∪B, where A is a finitary language in OCL(k) and B is an ω-language in k − ICL_{ω}. Remark that A and B should not be accepted by the same pushdown automaton (but it may be). Prove then the following.

Proposition 5.24 If C = A ∪ B, where A is a language in OCL(k) and B is an ω-language in k − ICL_{ω} over the same alphabet X_{A} = X_{B}, then C^{∼} is the union of a finitary language in OCL(k + 1) and of an ω-language in (k + 1) − ICL_{ω} over the alphabet X_{A} ∪ {↞}.

Proof. It is easy to see from the definition of the operation of exponentiation of sets that if C = A ∪ B then: C^{∼} = A^{∼} ∪ B^{∼}. But if B is a k-iterated counter ω-language over X_{B} = X_{A}, then by Theorem 5.22 B^{∼} is a k + 1-iterated counter ω-language D_{1}.

Consider now the set A^{∼}: This subset of (X_{A} ∪ {↞})^{≤ω} is constituted of finite and infinite words. Let h be the substitution: X → P ((X_{A} ∪ {↞})^{⋆}) defined by a → a.L_{3} where L_{3} is the one counter language defined above. Then it is easy to see that the finite words are obtained by substituting in A the language a.L_{3} for each letter a ∈ X_{A} and concatenating on the left by the language L_{4}. But after substitution we obtain a language in OCL(k+1) because OCL(k)□OCL = OCL(k +1), and then by concatenation by the language L_{4} which is in OCL we obtain a language D_{2} which is also in OCL(k + 1).

The infinite words in A^{∼} constitutes the ω-language D_{2}.(L_{3} − {λ})^{ω} if λ ∉ A, and D_{2}.(L_{3} − {λ})^{ω} ∪ (L_{4} − {λ})^{ω} if λ ∈ A,

The languages L_{4} −{λ} and L_{3} −{λ} are one counter languages, thus the set of infinite words in A^{∼} is a (k + 1)-iterated counter ω-language D_{3} because ω − KC(OCL(k + 1)) ⊆ (k + 1) − ICL_{ω} by Theorem 3.7. Then:

A^{∼} = D_{1} ∪ D_{2} ∪ D_{3}

But (k +1)−ICL_{ω} is closed under union hence D_{1} ∪D_{3} is in (k +1)−ICL_{ω}. □

Remark 5.25 It is easy to see from the definition of A^{∼} that whenever A ⊆ X_{A}^{≤ω} it holds that:

(X_{A} ∪ {↞})^{≤ω} − A^{∼} = (X_{A}^{≤ω} − A)^{∼}

hence if A and A^{−} are unions of a language in OCL(k) and of an ωlanguage in k−ICL_{ω}, A^{∼} and (A^{∼})^{−} are unions of a language in OCL(k+1) and of an ω-language in (k + 1) − ICL_{ω}, by proposition 5.24.

6 Conciliating hierarchy of infinitary context free languages

In this section we study the conciliating hierarchy of infinitary context free languages.

We denote Co−k −ICL_{ω} (respectively Co−k −ICL_{≤ω}) the class of complements of ω-languages (respectively (≤ ω)-languages) which are in k − ICL_{ω} (respectively k − ICL_{≤ω}) and similarly we denote Co − CF L_{ω} (respectively Co − CF L_{≤ω}) the class of complements of omega (respectively infinitary) context free languages.

Then we can summarize the preceding results:

Proposition 6.1 a) For each integer k ≥ 0, the class (k−ICL_{≤ω})∩(Co− k − ICL_{≤ω}) is closed under the operations A, B → A + B, A → A^{+}.

b) For each integer k ≥ 1, the class (k − ICL_{≤ω}) ∩ (Co − k − ICL_{≤ω}) is closed under the operations A → A.α, for α < ω^{ω}.

c) For each integer k ≥ 0, if A ∈ (k − ICL_{≤ω}) ∩ (Co − k − ICL_{≤ω}) the (≤ ω)-language A^{∼} is in ((k + 1) − ICL_{≤ω}) ∩ (Co − (k + 1) − ICL_{≤ω}).

Introduce now some notations for ordinals obtained by iterating the operation of exponentiation of base ω: i.e. the operation α → ω^{α} for α ordinal. We denote ω(1) = ω and for an integer n ≥ 1, ω(n + 1) = ω^{ω(n)}:

ω(n) = \underbrace{ω^{ω^{.^{.^{.^{ω}}}}}}_{n}

Then the limit of the ordinals ω(n) which is also the upper bound of the ordinals ω(n) is the well known Cantor ordinal ε_{0}. It is the first fixed point of the operation of exponentiation of base ω.

Now we can state the main result about the conciliating hierarchy of infinitary context free languages.

Theorem 6.2 a) For each integer k ≥ 0, the length of the conciliating hierarchy of (≤ ω)-languages in (k − ICL_{≤ω}) ∩ (Co − k − ICL_{≤ω}) is an ordinal greater than ω(k + 2).

b) the length of the conciliating hierarchy of iterated counter (and Co−iterated counter) infinitary languages is an ordinal greater than ε_{0}.

Corollary 6.3 The length of the conciliating hierarchy of infinitary languages in CF L_{≤ω} ∩ Co − CF L_{≤ω} is greater than ε_{0}.

Proof of a). We reason by induction on the integer k. The result has been already proved for the case k = 0.

In order to prove a) for k > 0, we shall use only the operation of sum and the operation of exponentiation A → A^{∼}. Recall that if A ⊆ X_{A}^{≤ω} is a conciliating set such that A^{d} is a Borel set and d_{c}(A) = d_{w}(A^{d}) = α + n with α a limit ordinal and n an integer ≥ 0, then 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)}

We have already obtained a family C_{0} of conciliating sets in (0 − ICL_{≤ω}) ∩ (Co − 0 − ICL_{≤ω}), closed under complementation, such that, for A ∈ C_{0}, d_{c}(A) is in the following form:

d_{c}(A) = ω_{1}^{n_{j}}.m_{j} + ω_{1}^{n_{j−1}}.m_{j−1} + … + ω_{1}^{n_{1}}.m_{1}

where j > 0 is an integer, n_{j} > n_{j−1} > … > n_{1} ≥ 0 are integers and m_{j}, m_{j−1}, …, m_{1} are integers > 0.

Then for A ∈ C_{0}, d_{c}(A) is an ordinal in the form α + n, with α = 0 or α a limit ordinal of cofinality ω_{1}, and n an integer ≥ 0.

Then if A ∈ C_{0}, there are two cases:

a) If d_{c}(A) = n, n being an integer ≥ 1, then d_{c}(A^{∼}) = ω_{1}^{n−1}

b) If d_{c}(A) = α + n with α a limit ordinal of cofinality ω_{1}, then d_{c}(A^{∼}) = (ω_{1})^{d_{c}(A)}

So we see that d_{c}(A^{∼}) may take the value 1 and all the values ω_{1}^{β} for β ∈ {d_{c}(A) / A ∈ C_{0}} = D_{0}.

From the closure properties of proposition 6.1, we can infer that (1−ICL_{≤ω})∩ (Co − 1 − ICL_{≤ω}) contains all (≤ ω)-languages in the form:

(A_{j})^{∼}.n_{j} + (A_{j−1})^{∼}.n_{j−1} + … + (A_{1})^{∼}.n_{1}

where j is an integer ≥ 1, for each i, 1 ≤ i ≤ j, A_{i} ∈ C_{0}, and n_{1}, n_{2}, …, n_{j} are integers ≥ 1.

The length of the conciliating hierarchy of C_{0} is ω^{ω} and there exists a strictly increasing isomorphism:

ϕ_{0} : {d_{c}(A) / A ∈ C_{0}} ⟶ ω^{ω} − {0}

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

where j > 0 is an integer, n_{j} > n_{j−1} > … > n_{1} ≥ 0 are integers and m_{j}, m_{j−1}, …, m_{1} are integers > 0.

This isomorphism is easily extended to a strictly increasing isomorphism:

ϕ̄_{0} : {0} ∪ {d_{c}(A) / A ∈ C_{0}} ⟶ ω^{ω}
α ≠ 0 ⟶ ϕ_{0}(α)
0 ⟶ 0

Define C_{1} as the family containing all conciliating sets in the following form and their complements:

(A_{j})^{∼}.n_{j} + (A_{j−1})^{∼}.n_{j−1} + … + (A_{1})^{∼}.n_{1}

where j is an integer ≥ 1, for each i, 1 ≤ i ≤ j, A_{i} ∈ C_{0}, and n_{1}, n_{2}, …, n_{j} are integers ≥ 1.

Then C_{1} ⊆ (1 − ICL_{≤ω}) ∩ (Co − 1 − ICL_{≤ω}) We shall prove that the length of the conciliating hierarchy of C_{1} is greater than ω(3).

Remark first that for A ∈ C_{1}, d_{c}(A) is in the following form:

d_{c}(A) = ω_{1}^{α_{j}}.m_{j} + ω_{1}^{α_{j−1}}.m_{j−1} + … + ω_{1}^{α_{1}}.m_{1}

where j > 0 is an integer, α_{j} > α_{j−1} > … > α_{1} are in {d_{c}(A) / A ∈ C_{0}}∪{0} and m_{j}, m_{j−1}, …, m_{1} are integers > 0.

Consider now the Cantor normal form of a non null ordinal

α < ω^{ω^{ω}} = ω(3)

Such an ordinal α can be written in the form:

α = ω^{δ_{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.

Now it is easy to see that there exists a strictly increasing isomorphism:

ϕ_{1} : {d_{c}(A) / A ∈ C_{1}} ⟶ ω^{ω^{ω}} − {0}

ω_{1}^{α_{j}}.m_{j}+ω_{1}^{α_{j−1}}.m_{j−1}+…+ω_{1}^{α_{1}}.m_{1} ⟶ α = ω^{ϕ̄_{0}(α_{j})}.m_{j}+ω^{ϕ̄_{0}(α_{j−1})}.m_{j−1}+…+ω^{ϕ̄_{0}(α_{1})}.m_{1}

where j > 0 is an integer, α_{j} > α_{j−1} > … > α_{1} are in {d_{c}(A) / A ∈ C_{0}}∪{0} and m_{j}, m_{j−1}, …, m_{1} are integers > 0.

Hence the length of the conciliating hierarchy of infinitary languages in C_{1} and also in (1 − ICL_{≤ω}) ∩ (Co − 1 − ICL_{≤ω}) is greater than ω^{ω^{ω}} (the order type of the set of ordinals ω^{ω^{ω}} − {0} is given by the ordinal ω^{ω^{ω}}).

Now we see that we can iterate this proof:

Assume that we have already obtained a family C_{k} of conciliating sets in (k − ICL_{≤ω}) ∩ (Co − k − ICL_{≤ω}), closed under complementation, such that, for A ∈ C_{k}, d_{c}(A) is an ordinal in the form α + n, with α = 0 or α a limit ordinal of cofinality ω_{1}, and n an integer ≥ 0. And assume also that there exists a strictly increasing isomorphism:

ϕ̄_{k} : {0} ∪ {d_{c}(A) / A ∈ C_{k}} ⟶ ω(k + 2)

Define C_{k+1} as the family containing all conciliating sets in the following form and their complements:

(A_{j})^{∼}.n_{j} + (A_{j−1})^{∼}.n_{j−1} + … + (A_{1})^{∼}.n_{1}

where j is an integer ≥ 1, for each i, 1 ≤ i ≤ j, A_{i} ∈ C_{k}, and n_{1}, n_{2}, …, n_{j} are integers ≥ 1.

Then C_{k+1} ⊆ ((k + 1) − ICL_{≤ω}) ∩ (Co − (k + 1) − ICL_{≤ω}) We shall prove that the length of the conciliating hierarchy of C_{k+1} is greater than ω(k + 3).

Remark first that for A ∈ C_{k+1}, d_{c}(A) is in the following form:

d_{c}(A) = ω_{1}^{α_{j}}.m_{j} + ω_{1}^{α_{j−1}}.m_{j−1} + … + ω_{1}^{α_{1}}.m_{1}

where j > 0 is an integer, α_{j} > α_{j−1} > … > α_{1} are in {d_{c}(A) / A ∈ C_{k}}∪{0} and m_{j}, m_{j−1}, …, m_{1} are integers > 0.

Consider now the Cantor normal form of a non null ordinal

α < ω(k + 3)

Such an ordinal α can be written in the form:

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

where j > 0 is an integer, δ_{j} > δ_{j−1} > … > δ_{1} are ordinals < ω(k + 2) and m_{j}, m_{j−1}, …, m_{1} are integers > 0.

Now it is easy to see that there exists a strictly increasing isomorphism:

ϕ_{k+1} : {d_{c}(A) / A ∈ C_{k+1}} ⟶ ω(k + 3) − {0}

ω_{1}^{α_{j}}.m_{j}+ω_{1}^{α_{j−1}}.m_{j−1}+…+ω_{1}^{α_{1}}.m_{1} ⟶ α = ω^{ϕ̄_{k}(α_{j})}.m_{j}+ω^{ϕ̄_{k}(α_{j−1})}.m_{j−1}+…+ω^{ϕ̄_{k}(α_{1})}.m_{1}

where j > 0 is an integer, α_{j} > α_{j−1} > … > α_{1} are in {d_{c}(A) / A ∈ C_{k}}∪{0} and m_{j}, m_{j−1}, …, m_{1} are integers > 0.

Hence the length of the conciliating hierarchy of infinitary languages in C_{k+1} and also in ((k + 1) − ICL_{≤ω}) ∩ (Co − (k + 1) − ICL_{≤ω}) is greater than ω(k + 3) (the order type of the set of ordinals ω(k + 3) − {0} is given by the ordinal ω(k + 3)).

And we can define the isomorphism ϕ̄_{k+1} from ϕ_{k+1} then this ends the proof by induction on the integer k. □

7 Wadge hierarchy of omega context free languages

We consider now ω-languages. Recall that the operation A → A^{d} over conciliating sets has the following property:

If A ∈ (k−ICL_{≤ω})∩(Co−k−ICL_{≤ω}) then A^{d} ∈ (k−ICL_{ω})∩(Co−k−ICL_{ω}). And if A^{d} is a Borel set, it holds that: d_{w}(A^{d}) = d_{c}(A).

Hence the following results can be derived from the corresponding study of the conciliating hierarchy of iterated counter (≤ ω)-languages:

Theorem 7.1 a) For each integer k ≥ 0, the length of the Wadge hierarchy of ω-languages in (k − ICL_{ω}) ∩ (Co − k − ICL_{ω}) is an ordinal greater than ω(k + 2).

b) the length of the Wadge hierarchy of iterated counter (and Co−iterated counter) ω-languages is an ordinal greater than ε_{0}.

Corollary 7.2 The length of the Wadge hierarchy of context free ω-languages is greater than ε_{0}.

Proof. Recall that we had obtained in proof of Theorem 6.2, for each integer k ≥ 0, a family C_{k} of conciliating sets in (k − ICL_{≤ω}) ∩ (Co − k − ICL_{≤ω}), closed under complementation, such that the conciliating hierarchy restricted to C_{k} has length ω(k + 2).

Let C_{k}^{d} = {A^{d} / A ∈ C_{k}}. Then C_{k}^{d} ⊆ (k − ICL_{ω}) ∩ (Co − k − ICL_{ω}). And the relation d_{w}(A^{d}) = d_{c}(A) implies that the Wadge hierarchy of ωlanguages in C_{k}^{d} has length ω(k + 2).

b) follows from a) and the definition of the ordinal ε_{0}. □

Remark 7.3 In fact the ω-languages in C_{k}^{d} are non self dual hence the wadge hierarchy of non self dual sets in CF L_{ω} ∩Co−CF L_{ω} has length ≥ ε_{0}. And we can generate self dual omega context free languages from non self dual ones:

Definition 7.4 Let A ⊆ X_{A}^{ω} and let {X_{+}, X_{−}} be a partition of X_{A} into two non empty sets. The ω-language S(A) is defined by: S(A) = X_{+}.A∪X_{−}.A^{−}.

Proposition 7.5 ([Dup99]) Let A ⊆ X_{A}^{ω} be a non self dual Borel set. Then S(A) is a self dual Borel set and it is the <_{W} -least above A (and A^{−}).

And, with regard to iterated counter languages, it holds that:

Proposition 7.6 If A ⊆ X_{A}^{ω} is in (k −ICL_{ω})∩(Co−k −ICL_{ω}), then S(A) and S(A)^{−} are in (k − ICL_{ω}) ∩ (Co − k − ICL_{ω}).

Proof. Assume A ⊆ X_{A}^{ω} is in (k − ICL_{ω}) ∩ Co − k − ICL_{ω}). By definition S(A) = X_{+}.A ∪ X_{−}.A^{−} but k − ICL_{ω} is closed under left concatenation by regular languages and union hence S(A) is in k − ICL_{ω} and S(A)^{−} = X_{+}.A^{−} ∪ X_{−}.A hence by a similar argument S(A)^{−} is in k − ICL_{ω}. □

Then we can deduce the following:

Theorem 7.7 a) For each integer k ≥ 0, the length of the Wadge hierarchy of non self dual ω-languages in (k − ICL_{ω}) ∩ (Co − k − ICL_{ω}) is an ordinal greater than ω(k + 2).

b) For each integer k ≥ 0, the length of the Wadge hierarchy of self dual ω-languages in (k − ICL_{ω}) ∩ (Co − k − ICL_{ω}) is an ordinal greater than ω(k + 2).

Corollary 7.8 a) The length of the Wadge hierarchy of non self dual context free ω-languages is greater than ε_{0}.

b) The length of the Wadge hierarchy of self dual context free ω-languages is greater than ε_{0}.

Remark 7.9 Up to now we have just used the operations A, B → A + B, A → A^{+} and A → A^{∼} to obtain our results on the length of the studied hierarchies. So natural questions now arise: what about the operation of multiplication by an ordinal < ω^{ω}? Could we improve the preceding results by considering this new operation?

In fact we can obtain many more Wadge degrees in such a way. For example there exists in 1 − ICL_{ω}, i.e. in the class of one counter ω-languages, an ω-language of Wadge degree α, for each ordinal α < ω^{ω}. But without this operation we can only obtain some ω-languages of Wadge degree < ω or of Wadge degree ≥ ω_{1}. Recall that a Borel set has Wadge degree ≥ ω_{1} if and only if it is not in Σ_{2}^{0} ∩ Π_{2}^{0}, [Dup99]. Then we deduce the following:

Proposition 7.10 The length of the Wadge hierarchy of one counter ωlanguages which are in Σ_{2}^{0} ∩ Π_{2}^{0} is greater than ω^{ω}.

And in a similar manner we can obtain many more Wadge degrees for greater ordinals.

On the other hand, the Wadge hierarchy of deterministic context free ωlanguages has been determined: it has length ω^{(ω^{2})}, [DFR99] [Dup99][Fin99b].

And the Wadge degrees of deterministic context free ω-languages are in the following form:

d_{w}(A) = ω_{1}^{n_{j}}.δ_{j} + ω_{1}^{n_{j−1}}.δ_{j−1} + … + ω_{1}^{n_{1}}.δ_{1}

where j > 0 is an integer, n_{j} > n_{j−1} > … > n_{1} are integers ≥ 0, and δ_{j}, δ_{j−1}, …, δ_{1} are non null ordinals < ω^{ω}.

Then we see that one can obtain non self dual one counter ω-languages of each such degree and the self dual ones are generated by the preceding operation A → S(A). Then the hierarchy of one counter ω-languages is strictly larger than the hierarchy of deterministic context free ω-languages: there exists some one counter ω-languages which are not in Σ_{3}^{0}, for example an ω-language of Wadge degree ω_{1}^{ω_{1}^{2}} (because a Borel set is in Σ_{3}^{0} ∪Π_{3}^{0} iff its Wadge degree is ≤ ω_{1}^{ω_{1}}, [Dup99]) but deterministic context free ω-languages are boolean combinations of Σ_{2}^{0}-sets, hence in Σ_{3}^{0}. And the lengths of the hierarchies are respectively ω^{(ω^{2})} and ≥ ω^{ω^{ω}}. So we can state the:

Proposition 7.11 For each deterministic context free ω-language L, there exists a one counter ω-language L_{1} which is Wadge equivalent to L. But the converse is not true.

Consider now the lower bounds for the lengths of the hierarchies we have studied. Can we get better results?

Recall we have inductively defined in section 6 the class C_{k+1} ⊆ ((k + 1) − ICL_{≤ω}) ∩ (Co − (k + 1) − ICL_{≤ω}) as the family containing all conciliating sets in the following form and their complements:

(A_{j})^{∼}.n_{j} + (A_{j−1})^{∼}.n_{j−1} + … + (A_{1})^{∼}.n_{1}

where j is an integer ≥ 1, for each i, 1 ≤ i ≤ j, A_{i} ∈ C_{k}, and n_{1}, n_{2}, …, n_{j} are integers ≥ 1. Then for A ∈ C_{k+1}, d_{c}(A) was in the following form:

d_{c}(A) = ω_{1}^{α_{j}}.m_{j} + ω_{1}^{α_{j−1}}.m_{j−1} + … + ω_{1}^{α_{1}}.m_{1}

where j > 0 is an integer, α_{j} > α_{j−1} > … > α_{1} are in {d_{c}(A) / A ∈ C_{k}}∪{0} and m_{j}, m_{j−1}, …, m_{1} are integers > 0.

By using the operation of multiplication by an ordinal < ω^{ω}: A → A.α, we could have replaced in the definition of C_{k+1} the integers n_{1}, n_{2}, …, n_{j} by some non null ordinals ν_{1}, ν_{2}, …, ν_{j} < ω^{ω}. In such a way we generate many more Wadge degrees but the lower bounds for the lengths of the hierarchies remain unchanged.

As an example consider first the case of C_{1} defined from the class C_{0}. Call C′_{1} the family containing all conciliating sets in the following form and their complements:

(A_{j})^{∼}.ν_{j} + (A_{j−1})^{∼}.ν_{j−1} + … + (A_{1})^{∼}.ν_{1}

where j is an integer ≥ 1, for each i, 1 ≤ i ≤ j, A_{i} ∈ C_{0}, and ν_{1}, ν_{2}, …, ν_{j} are some non null ordinals < ω^{ω}.

We used in the previous proof the Cantor normal form of an ordinal. It was in fact the Cantor normal form of base ω, but there exist some extensions: in particular every non null ordinal α has a Cantor normal form of base ω^{ω}, i.e. α may be written in the form [Sie65]:

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

where j > 0 is an integer, δ_{j} > δ_{j−1} > … > δ_{1} are ordinals and ν_{j}, ν_{j−1}, …, ν_{1} are non null ordinals < ω^{ω}.

Remark now that:

ω^{ω^{ω}} = (ω^{ω})^{ω^{ω}}

This follows from properties of arithmetical operations over ordinals. Indeed it holds that:

ω.ω^{ω} = ω^{1+ω} = ω^{ω}

and then we can infer that:

ω^{ω^{ω}} = ω^{(ω.ω^{ω})} = (ω^{ω})^{ω^{ω}}

Then the above normal form of base ω^{ω} describes an ordinal α < ω^{ω^{ω}} iff every ordinal δ_{i} is < ω^{ω}.

Remark that for A ∈ C′_{1}, d_{c}(A) is in the following form:

d_{c}(A) = ω_{1}^{α_{j}}.ν_{j} + ω_{1}^{α_{j−1}}.ν_{j−1} + … + ω_{1}^{α_{1}}.ν_{1}

where j > 0 is an integer, α_{j} > α_{j−1} > … > α_{1} are in {d_{c}(A) / A ∈ C_{0}}∪{0} and ν_{j}, ν_{j−1}, …, ν_{1} are non null ordinals < ω^{ω}.

Consider now a non null ordinal α < ω^{ω^{ω}} = ω(3) written in the Cantor normal form of base ω^{ω}:

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

where j > 0 is an integer, δ_{j} > δ_{j−1} > … > δ_{1} are ordinals < ω^{ω} and ν_{j}, ν_{j−1}, …, ν_{1} are non null ordinals < ω^{ω}.

Now it is easy to see that there exists a strictly increasing isomorphism:

ϕ′_{1} : {d_{c}(A) / A ∈ C′_{1}} ⟶ ω^{ω^{ω}} − {0}

ω_{1}^{α_{j}}.ν_{j}+ω_{1}^{α_{j−1}}.ν_{j−1}+…+ω_{1}^{α_{1}}.ν_{1} ⟶ (ω^{ω})^{ϕ̄_{0}(α_{j})}.ν_{j}+(ω^{ω})^{ϕ̄_{0}(α_{j−1})}.ν_{j−1}+…+(ω^{ω})^{ϕ̄_{0}(α_{1})}.ν_{1}

where j > 0 is an integer, α_{j} > α_{j−1} > … > α_{1} are in {d_{c}(A) / A ∈ C_{0}}∪{0} and ν_{j}, ν_{j−1}, …, ν_{1} are non null ordinals < ω^{ω}. And where ϕ̄_{0} is the strictly increasing isomorphism:

ϕ̄_{0} : {0} ∪ {d_{c}(A) / A ∈ C_{0}} ⟶ ω^{ω}

defined in section 6.

Hence the length of the conciliating hierarchy of infinitary languages in C′_{1} and also in (1 − ICL_{≤ω}) ∩ (Co − 1 − ICL_{≤ω}) is greater than ω^{ω^{ω}} but we cannot get a better result.

The case of C_{k} for k ≥ 2 is very similar. We first remark that for each integer n ≥ 2, it holds that ω.ω(n) = ω(n), and then:

ω(n + 1) = ω^{ω(n)} = ω^{ω.ω(n)} = (ω^{ω})^{ω(n)}

Hence every ordinal α < ω(n + 1) admits a Cantor normal form of base ω^{ω}:

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

where j > 0 is an integer, δ_{j} > δ_{j−1} > … > δ_{1} are ordinals < ω(n) and ν_{j}, ν_{j−1}, …, ν_{1} are non null ordinals < ω^{ω}.

The proof is now similar to the case k = 1 but with a sligth modification: For k ≥ 1 we define C′_{k+1} as the family containing all conciliating sets in the following form and their complements:

(A_{j})^{∼}.ν_{j} + (A_{j−1})^{∼}.ν_{j−1} + … + (A_{1})^{∼}.ν_{1}

where j is an integer ≥ 1, for each i, 1 ≤ i ≤ j, A_{i} ∈ C′_{k}, and ν_{1}, ν_{2}, …, ν_{j} are some non null ordinals < ω^{ω}.

But for k ≥ 1 there exist in C′_{k} some conciliating sets A which degrees are in the form α + n, with α a limit ordinal of cofinality ω, and n an integer ≥ 0. Hence for these sets:

d_{c}(A^{∼}) = (ω_{1})^{d_{c}(A)+1}

by Theorem 5.21. Nevertheless the order type of

{d_{c}(A^{∼}) / A ∈ C′_{k}}

remains unchanged and is equal to the order type of {d_{c}(A) / A ∈ C_{k}}. Further details are left to the reader. □

8 Concluding remarks and further work

We proved in [Fin99a] that the class CF L_{ω} exhausts the hierarchy of Borel sets of finite rank. We have proved above that the length of the Wadge hierarchy of ω-CFL is greater than ε_{0}.

On the other hand, deterministic ω-CFL are all boolean combinations of Σ_{2}^{0}-sets therefore they are (Σ_{3}^{0} ∩ Π_{3}^{0})-sets. And the Wadge hierarchy of deterministic ω-CFL has length ω^{(ω^{2})}. This hierarchy is studied by J. Duparc in [Dup99] using methods of descriptive set theory and game theory. We shall present in future papers a study of this hierarchy which is analogous to Wagner’s study of the Wadge hierarchy of ω-regular languages, [Fin99b].

Thus our results show that, with regard to their topological complexity, non deterministic pushdown automata have a much stronger expressive power than deterministic pushdown automata, when reading ω-words with a Büchi or Muller acceptance condition.

And this is in big contrast with the case of finite automata, because deterministic and non deterministic Muller automata have exactly the same expressive power and define boolean combinations of Σ_{2}^{0}-sets.

Further, it remains to determine the exact length of the Wadge hierarchy of ω-CFL (and of the other hierarchies we have studied here) and all the degrees of ω-CFL. And, although the Wadge hierarchy of ω-CFL is not effective, it seems possible, as stated in [DFR99], to find some subclass of CF L_{ω} which would strictly contain the class of deterministic ω-CFL but would have an effective Wadge hierarchy.

Acknowledgements. Thanks to Jean-Pierre Ressayre, Jacques Duparc and Gilles Amiot for many useful and stimulating discussions about Wadge and Wagner Hierarchies, and to the anonymous referee for indicating some errors on a previous 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.

[Bar92] R. Barua, The Hausdorff-Kuratowski hierarchy of ω-regular languages and a hierarchy of Muller automata, Theoretical Computer Science 96 (1992), 345-360.

[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).

[Ber79] J. Berstel, Transductions and Context Free Languages, Teubner Studienbücher Informatik, 1979.

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

[Büc60a] J.R. Büchi, Weak Second Order Arithmetic and Finite Automata, Zeitschrift fur Mathematische Logik und Grundlagen der Mathematik, 6 (1960), pp 66-92.

[Büc60b] J.R. Büchi, On a Decision Method in Restricted Second Order Arithmetic, Logic Methodology and Philosophy of Science, ( Proc. 1960 Int. Congr. ). Stanford University Press, 1962, 1-11.

[BL69] J.R. Büchi and L. H. Landweber, Solving sequential conditions by finite state strategies. Trans. Amer. Math. Soc. 138 (1969).

[BS73] J.R. Büchi, D. Siefkes, The Monadic Second Order Theory of All Countable ordinals, Decidable Theories 2, 1973, S.L.N.M. , number 328.

[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.

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

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

[CP98] O. Carton and D. Perrin, The Wagner Hierarchy of ω-Rational sets, To appear in International Journal of Algebra and Computation.

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

[Dup95b] J. Duparc, The Normal form of Borel sets, Part 1: Borel sets of finite rank, C.R.A.S. Paris, t.320, Série 1, p.651-656, 1995.

[Dup99] J. Duparc, Wadge Hierarchy and Veblen hierarchy: part 1: Borel sets of finite rank, To appear in the Journal of Symbolic Logic. Available from http://www.logigue.jussieu.fr/www.duparc

[Dup99] J. Duparc, A Hierarchy of Context Free ω-Languages, Submitted to Theoretical Computer Science.

[DFR99] J. Duparc, O. Finkel and J-P. Ressayre, Computer Science and the Fine Structure of Borel Sets, to appear in Theoretical Computer Science. Available from http://www.logigue.jussieu.fr/www.duparc

[Eil74] S. Eilenberg, Automata, Languages and Machines, Vol. A, Academic Press, New York, 1974.

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

[Fin99a] O. Finkel, Topological Properties of Omega Context Free Languages, to appear in Theoretical Computer Science.

[Fin99b] O. Finkel, Wadge Hierarchy of Omega Deterministic Context Free Languages, in preparation.

[Fin00] O. Finkel, Borel Hierarchy and Omega Context Free Languages, submitted to Theoretical Computer Science.

[Gin66] S. Ginsburg, The Mathematical Theory of Context Free Languages, Mc Graw-Hill Book Company, New York, 1966.

[HU69] J.E. Hopcroft and J.D. Ullman, Formal Languages and their Relation to Automata, Addison-Wesley Publishing Company, Reading, Massachussetts, 1969.

[Kam85] M. Kaminsky, A classification of ω-regular languages , Theoretical Computer Science 36 (1985), 217-229.

[Kur66] K. Kuratowski, Topology, Academic Press, New York 1966.

[Lan69] L. H. Landweber, Decision problems for ω-automata, Math. Syst. Theory 3 (1969) 4,376-384.

[Lat83] M. Latteux, Langages à un Compteur, Journal of Computer and System Sciences, Vol 26, number 1, February 1983.

[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.

[PP98] D. Perrin and J.-E. Pin, Infinite Words, Book in preparation, available from http://www.liafa.jussieu.fr/jep/InfiniteWords.html

[MaN66] R. Mac Naughton, Testing and Generating infinite sequences by a finite automaton, Information and Control 9 (1966), 521-530.

[Sel98] V. Selivanov, Fine hierarchy of regular ω-languages, Theoretical Computer Science 191(1998) p.37-59.

[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.

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

[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.