IOS Press

An ω-Power of a Finitary Language Which is a Borel Set of Infinite Rank

Olivier Finkel

Equipe de Logique Mathématique

U.F.R. de Mathématiques, Université Paris 7

2 Place Jussieu 75251 Paris cedex 05, France.

finkel@logique.jussieu.fr

Abstract. ω-powers of finitary languages are ω-languages in the form V^{ω}, where V is a finitary language over a finite alphabet Σ. Since the set Σ^{ω} of infinite words over Σ can be equipped with the usual Cantor topology, the question of the topological complexity of ω-powers naturally arises and has been raised by Niwinski [13], by Simonnet [15], and by Staiger [18]. It has been proved in [4] that for each integer n ≥ 1, there exist some ω-powers of context free languages which are Π_{n}^{0}- complete Borel sets, and in [5] that there exists a context free language L such that L^{ω} is analytic but not Borel. But the question was still open whether there exists a finitary language V such that V^{ω} is a Borel set of infinite rank. We answer this question in this paper, giving an example of a finitary language whose ω-power is Borel of infinite rank.

Keywords: Infinite words, ω-languages, ω-powers, Cantor topology, topological complexity, Borel sets, infinite rank

1. Introduction

ω-powers are ω-languages in the form V^{ω}, where V is a finitary language. The operation V → V^{ω} is a fundamental operation over finitary languages leading to ω-languages. This operation appears in the characterization of the class REG_{ω} of ω-regular languages (respectively, of the class CF_{ω} of context free ω-languages) as the ω-Kleene closure of the family REG of regular finitary languages (respectively, of the family CF of context free finitary languages) [17].

Address for correspondence: E Mail: finkel@logique.jussieu.fr

2 Olivier Finkel / An ω-Power of a Finitary Language Which is a Borel Set of Infinite Rank

The set Σ^{ω} of infinite words over a finite alphabet Σ is usually equipped with the Cantor topology which may be defined by a distance, see [17, 14]. One can then study the complexity of ω-languages, i.e. languages of infinite words, by considering their topological complexity, with regard to the Borel hierarchy (and beyond to the projective hierarchy) [17, 14]. The question of the topological complexity of ω-powers of finitary languages naturally arises. It has been posed by Niwinski [13], by Simonnet [15] and by Staiger [18]. The ω-power of a finitary language is always an analytic set because it is the continuous image of a compact set {0, 1, …, n}^{ω} for n ≥ 0 or of the Baire space ω^{ω}, [15, 4]. It has been proved in [4] that for each integer n ≥ 1, there exist some ω-powers of context free languages which are Π_{n}^{0}-complete Borel sets, and in [5] that there exists a context free language L such that L^{ω} is analytic but not Borel. But the question was still open whether there exists a finitary language V such that V^{ω} is a Borel set of infinite rank. We answer this question in this paper, giving an example of a finitary language whose ω-power is Borel of infinite rank. The paper is organized as follows. In Section 2 we recall definitions of Borel sets and previous results and we proved our main result in Section 3.

2. Recall on Borel sets and previous results

We assume the reader to be familiar with the theory of formal ω-languages [19, 17]. We shall use usual notations of formal language theory.

When Σ is a finite alphabet, a non-empty finite word over Σ is any sequence x = a_{1} … a_{k} , where a_{i} ∈ Σ for i = 1, …, k , and k is an integer ≥ 1. The length of x is k, denoted by |x|. The empty word has no letter and is denoted by λ; its length is 0. For x = a_{1} … a_{k}, we write x(i) = a_{i} and x[i] = x(1) … x(i) for i ≤ k and x[0] = λ. Σ^{⋆} is the set of finite words (including the empty word) over Σ.

The first infinite ordinal is ω. An ω-word over Σ is an ω -sequence a_{1} … a_{n} …, where for all integers i ≥ 1, a_{i} ∈ Σ. When σ is an ω-word over Σ, we write σ = σ(1)σ(2) … σ(n) …, where for all i, σ(i) ∈ Σ, and σ[n] = σ(1)σ(2) … σ(n) for all n ≥ 1 and σ[0] = λ.

The prefix relation is denoted ⊑: a finite word u is a prefix of a finite word v (respectively, an infinite word v), denoted u ⊑ v, if and only if there exists a finite word w (respectively, an infinite word w), such that v = u.w. The set of ω-words over the alphabet Σ is denoted by Σ^{ω}. An ω-language over an alphabet Σ is a subset of Σ^{ω}.

For V ⊆ Σ^{⋆}, the ω-power of V is the ω-language:

V^{ω} = {σ = u_{1} … u_{n} … ∈ Σ^{ω} | ∀i ≥ 1 u_{i} ∈ V − {λ}}

We assume the reader to be familiar with basic notions of topology which may be found in [12, 11, 8, 17, 14]. For a finite alphabet X, we consider X^{ω} as a topological space with the Cantor topology. The open sets of X^{ω} are the sets of the form W.X^{ω}, where W ⊆ X^{⋆}. A set L ⊆ X^{ω} is a closed set iff its complement X^{ω} − L is an open set. Define now the Borel Hierarchy of subsets of X^{ω}:

Definition 2.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}.

For a countable ordinal α, a subset of X^{ω} is a Borel set of rank α iff it is in Σ_{α}^{0} ∪ Π_{α}^{0} but not in ⋃_{γ<α}(Σ_{γ}^{0} ∪ Π_{γ}^{0}).

There are also some subsets of X^{ω} which are not Borel. In particular the class of Borel subsets of X^{ω} is strictly included into the class Σ_{1}^{1} of analytic sets which are obtained by projection of Borel sets, see for example [17, 11, 14, 8] for more details.

We now define completeness with regard to reduction by continuous functions. For a countable ordinal α ≥ 1, a set F ⊆ X^{ω} is said to be a Σ_{α}^{0} (respectively, Π_{α}^{0}, Σ_{1}^{1})-complete set iff for any set E ⊆ Y^{ω} (with Y a finite alphabet): E ∈ Σ_{α}^{0} (respectively, E ∈ Π_{α}^{0}, E ∈ Σ_{1}^{1}) iff there exists a continuous function f : Y^{ω} → X^{ω} such that E = f^{−1}(F). Σ_{n}^{0} (respectively Π_{n}^{0})-complete sets, with n an integer ≥ 1, are thoroughly characterized in [16].

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

We shall recall the definition of the operation A → A^{≈} over sets of infinite words we introduced in [4] and which is a simple variant of Duparc’s operation of exponentiation A → A^{∼} [3]. For a finite alphabet Σ we denote Σ^{≤ω} = Σ^{ω} ∪ Σ^{⋆}. Let now ↞ a letter not in Σ and X = Σ ∪ {↞}. 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. We add the convention that (u. ↞)^{↞} is undefined if |u^{↞}| = 0, i.e. when the last letter ↞ can not be used as an eraser (because every letter of Σ in u has already been erased by some erasers ↞ placed in u). Remark that the resulting word x^{↞} may be finite or infinite.

For example if u = (a ↞)^{n}, for n ≥ 1, or u = (a ↞)^{ω} then (u)^{↞} = λ, if u = (ab ↞)^{ω} then (u)^{↞} = a^{ω}, if u = bb(↞ a)^{ω} then (u)^{↞} = b, if u =↞ (a ↞)^{ω} or u = a ↞↞ a^{ω} or u = (a ↞↞)^{ω} then (u)^{↞} is undefined.

Definition 2.2. For A ⊆ Σ^{ω}, A^{≈} = {x ∈ (Σ ∪ {↞})^{ω} | x^{↞} ∈ A}.

The following result follows easily from [3] and was applied in [4] to study the ω-powers of finitary context free languages.

Theorem 2.3. Let n be an integer ≥ 2 and A ⊆ Σ^{ω} be a Π_{n}^{0}-complete set. Then A^{≈} is a Π_{n+1}^{0}-complete subset of (Σ ∪ {↞})^{ω}.

For each ω-language A ⊆ Σ^{ω}, the ω-language A^{≈} can be easily described from A by the use of the notion of substitution which we recall now. A substitution is defined by a mapping f : Σ → P (Γ^{⋆}), where Σ = {a_{1}, …, a_{n}} and Γ are two finite alphabets, f : a_{i} → L_{i} where for all integers i ∈ [1; n], f(a_{i}) = L_{i} is a finitary language over the alphabet Γ. Now this mapping is extended in the usual manner to finite words: f(a_{i_{1}} … a_{i_{n}}) = L_{i_{1}} … L_{i_{n}}, and to finitary languages L ⊆ Σ^{⋆}: f(L) = ∪_{x∈L}f(x). If for each integer i ∈ [1; n] the language L_{i} does not contain the empty word, then the mapping f may be extended to ω-words:

f(x(1) … x(n) …) = {u_{1} … u_{n} … | ∀i ≥ 1 u_{i} ∈ f(x(i))}

and to ω-languages L ⊆ Σ^{ω} by setting f(L) = ∪_{x∈L}f(x).

Let L_{1} = {w ∈ (Σ ∪ {↞})^{⋆} | w^{↞} = λ}. L_{1} is a context free (finitary) language generated by the context free grammar with the following production rules: S → aS ↞ S with a ∈ Σ; and S → λ (where λ is the empty word). Then, for each ω-language A ⊆ Σ^{ω}, the ω-language A^{≈} ⊆ (Σ ∪ {↞})^{ω} is obtained by substituting in A the language L_{1}.a for each letter a ∈ Σ.

By definition the operation A → A^{≈} conserves the ω-powers of finitary languages. Indeed if A = V^{ω} for some language V ⊆ Σ^{⋆} then A^{≈} = g(V^{ω}) = (g(V))^{ω} where g : Σ → P ((Σ ∪ {↞})^{⋆}) is the substitution defined by g(a) = L_{1}.a for every letter a ∈ Σ.

3. An ω-power which is Borel of infinite rank

We can now iterate k times this operation A → A^{≈}. More precisely, we define, for a set A ⊆ Σ^{ω}: A_{k}^{≈.0} = A, A_{k}^{≈.1} = A^{≈}, A_{k}^{≈.2} = (A_{k}^{≈.1})^{≈}, and A_{k}^{≈.k} = (A_{k}^{≈.(k−1)})^{≈}, where we apply k times the operation A → A^{≈} with different new letters ↞_{k}, ↞_{k−1}, …,↞_{3}, ↞_{2}, ↞_{1}, in such a way that we have successively:

A_{k}^{≈.0} = A ⊆ Σ^{ω}, A_{k}^{≈.1} ⊆ (Σ ∪ {↞_{k}})^{ω}, A_{k}^{≈.2} ⊆ (Σ ∪ {↞_{k}, ↞_{k−1}})^{ω}, . . . . . . . . . . . . A_{k}^{≈.k} ⊆ (Σ ∪ {↞_{k}, ↞_{k−1}, …, ↞_{1}})^{ω}.

For a reason which will be clear later we have chosen to successively call the erasers ↞_{k}, ↞_{k−1}, …, ↞_{2}, ↞_{1}, in this precise order. We set now A^{≈.k} = A_{k}^{≈.k} so it holds that

A^{≈.k} ⊆ (Σ ∪ {↞_{k}, ↞_{k−1}, …, ↞_{1}})^{ω}

Notice that definitions of A_{k}^{≈.1}, A_{k}^{≈.2}, …, A_{k}^{≈.(k−1)} were just some intermediate steps for the definition of A^{≈.k} and will not be used later.

We can also describe the operation A → A^{≈.k} in a similar manner as in the case of the operation A → A^{≈}, by the use of the notion of substitution.

Let L_{k} ⊆ (Σ ∪ {↞_{k}, ↞_{k−1}, …, ↞_{1}})^{⋆} be the language containing (finite) words u, such that all letters of u have been erased when the operations of erasing using the erasers ↞_{1}, ↞_{2}, …, ↞_{k−1}, ↞_{k}, are successively applied to u. Notice that the operations of erasing have to be done in a good order: the first operation of erasing uses the eraser ↞_{1}, then the second one uses the eraser ↞_{2}, and so on … So an eraser ↞_{j} may only erase a letter of Σ or an other “eraser” ↞_{i} for some integer i > j. It is easy to see that L_{k} is a context free language. In fact L_{k} belongs to the subclass of iterated counter languages which is the closure under substitution of the class of one counter languages, see [1, 4] for more details.

Let now h_{k} be the substitution: Σ → P ((Σ ∪ {↞_{k}, ↞_{k−1}, …, ↞_{1}})^{⋆}) defined by h_{k}(a) = L_{k}.a for every letter a ∈ Σ. Then it holds that, for A ⊆ Σ^{ω}, A^{≈.k} = h_{k}(A), i.e. A^{≈.k} is obtained by substituting in A the language L_{k}.a for each letter a ∈ Σ.

The ω-language R = (0^{⋆}.1)^{ω} = V^{ω}, where V = (0^{⋆}.1), is Π_{2}^{0}-complete. Then, by Theorem 2.3, for each integer p ≥ 1, h_{p}(V^{ω}) = (h_{p}(V))^{ω} is a Π_{p+2}^{0}-complete set.

We can see that the languages L_{k}, for k ≥ 1, form a sequence which is strictly increasing for the inclusion relation:

L_{1} ⊂ L_{2} ⊂ L_{3} ⊂ … ⊂ L_{i} ⊂ L_{i+1} …

In order to construct some ω-power which is Borel of infinite rank, we could try to substitute the language ∪_{k≥1}L_{k}.a to each letter a ∈ Σ. But the language ∪_{k≥1}L_{k}.a is defined over the infinite alphabet Σ∪{↞_{1} , ↞_{2}, ↞_{3}, …}, so we shall first code every eraser ↞_{j} by a finite word over a fixed finite alphabet. The eraser ↞_{j} will be coded by the finite word α.β^{j}.α over the alphabet {α, β}, where α and β are two new letters.

The morphism φ_{p} : (Σ ∪ {↞_{1}, …, ↞_{p}})^{⋆} → (Σ ∪ {α, β})^{⋆} defined by φ_{p}(c) = c for each c ∈ Σ and φ_{p}(↞_{j}) = α.β^{j}.α for each integer j ∈ [1, p], can be naturally extended to a continuous function ψ_{p} : (Σ ∪ {↞_{1}, …, ↞_{p}})^{ω} → (Σ ∪ {α, β})^{ω}.

Let now

L = ⋃_{n≥1} φ_{n}(L_{n})

and h : Σ → P ((Σ ∪ {α, β})^{⋆}) be the substitution defined by

h(a) = L.a

for each a ∈ Σ.

We can now state our main result:

Theorem 3.1. Let V = (0^{⋆}.1). Then the ω-power (h(V))^{ω} ⊆ {0, 1, α, β}^{ω} is a Borel set of infinite rank.

To prove this theorem, we shall proceed by successive lemmas.

Lemma 3.2. For all integers p ≥ 1, the ω-language ψ_{p}(R^{≈.p}) is a Π_{p+2}^{0}-complete subset of (Σ ∪ {α, β})^{ω}.

Proof. First we prove that ψ_{p}(R^{≈.p}) is in the class Π_{p+2}^{0}. For Σ = {0, 1}, ψ_{p}((Σ ∪ {↞_{1}, …, ↞_{p}})^{ω}) is the continuous image by ψ_{p} of the compact set (Σ ∪ {↞_{1} , …, ↞_{p}})^{ω}, hence it is also a compact set. The function ψ_{p} is injective and continuous thus it induces an homeomorphism ψ′_{p} between the two compact sets (Σ ∪ {↞_{1}, …, ↞_{p}})^{ω} and ψ_{p}((Σ ∪ {↞_{1}, …, ↞_{p}})^{ω}). We have already seen that, for each integer p ≥ 1, the ω-language R^{≈.p} is a Π_{p+2}^{0}-complete subset of (Σ ∪ {↞_{1}, …, ↞_{p}})^{ω}. Then ψ′_{p}(R^{≈.p}) is a Π_{p+2}^{0}-subset of ψ_{p}((Σ ∪ {↞_{1}, …, ↞_{p}})^{ω}), because the function ψ′_{p} is an homeomorphism. But one can prove, by induction over the integer j≥ 1, that each Π_{j}^{0} subset K of ψ_{p}((Σ ∪ {↞_{1}, …, ↞_{p} })^{ω}) is also a Π_{j}^{0} subset of (Σ ∪ {α, β})^{ω}. Thus ψ′_{p}(R^{≈.p}) = ψ_{p}(R^{≈.p}) is a Π_{p+2}^{0}-subset of (Σ ∪ {α, β})^{ω}. Remark now that the set R^{≈.p} being Π_{p+2}^{0}-complete, every Π_{p+2}^{0}-subset of X^{ω}, for X a finite alphabet, is the inverse image of R^{≈.p} by a continuous function. But it holds that R^{≈.p} = ψ_{p}^{−1}(ψ_{p}(R^{≈.p})), where ψ_{p} is a continuous function. Thus every Π_{p+2}^{0}-subset of X^{ω}, for X a finite alphabet, is the inverse image of ψ_{p}(R^{≈.p}) by a continuous function. Therefore ψ_{p}(R^{≈.p}) is also a Π_{p+2}^{0}-complete subset of (Σ ∪ {α, β})^{ω}. □

Lemma 3.3. The set (h(V))^{ω} is not a Borel set of finite rank.

Proof. Consider, for each integer p ≥ 1, the regular ω-language

R_{p} = ψ_{p}({0, 1, ↞_{1}, ↞_{2}, …, ↞_{p}}^{ω}) = {0, 1, α.β.α, α.β^{2}.α, …, α.β^{p}.α}^{ω}

We have seen that R_{p} is compact hence it is a closed set. And by construction it holds that (h(V))^{ω}∩R_{p} = ψ_{p}(h_{p}(V^{ω})) = ψ_{p}(R^{≈.p}) where R = V^{ω}, so by Lemma 3.2 this set is a Π_{p+2}^{0}-complete subset of {0, 1, α, β}^{ω}.

If (h(V))^{ω} was a Borel set of finite rank it would be in the class Π_{J}^{0} for some integer J ≥ 1. But then (h(V))^{ω} ∩ R_{p} would be the intersection of a Π_{J}^{0}-set and of a closed, i.e. Π_{1}^{0}-set. Thus, for each integer p ≥ 1, the set (h(V))^{ω} ∩ R_{p} would be a Π_{J}^{0}-set. This would lead to a contradiction because, for J = p, a Π_{J}^{0}-set cannot be a Π_{p+2}^{0}-complete set. □

Lemma 3.4. Every ω-word x ∈ (h(V))^{ω} has a unique decomposition of the form x = u_{1}.u_{2} … u_{n} … where for all i ≥ 1 u_{i} ∈ h(V).

Proof. Towards a contradiction assume on the contrary that some ω-word x ∈ (h(V))^{ω} = (h(0^{⋆}.1))^{ω} has (at least) two distinct decompositions in words of h(V). So there are some words u_{j}, u′_{j} ∈ h(V), for j ≥ 1, such that

x = u_{1}.u_{2} … u_{n} … = u′_{1}.u′_{2} … u′_{n} …

and an integer J ≥ 1 such that u_{j} = u′_{j} for j < J and u_{J} ⊏ u′_{J}, i.e. u_{J} is a strict prefix of u′_{J}. Then for each integer j ≥ 1, there are integers n_{j}, n′_{j} ≥ 0 such that u_{j} ∈ h(0^{n_{j}}.1) and u′_{j} ∈ h(0^{n′_{j}}.1). Thus there are some finite words v_{i}^{j} ∈ L, where i is an integer in [1, n_{j} + 1], and w_{i}^{j} ∈ L, where i is an integer in [1, n′_{j} + 1], such that

u_{j} = v_{1}^{j}.0.v_{2}^{j}.0 … v_{n_{j}}^{j}.0.v_{n_{j}+1}^{j}.1 and u′_{j} = w_{1}^{j}.0.w_{2}^{j}.0 … w_{n′_{j}}^{j}.0.w_{n′_{j}+1}^{j}.1

We consider now x given by its first decomposition x = u_{1}.u_{2} … u_{n} … Let now x^{(1)} be the ω-word obtained from x by using the (code of the) eraser ↞_{1} as an eraser which may erase letters 0, 1, and (codes of the) erasers ↞_{p} for p > 1. Remark that by construction these operations of erasing occur inside the words v_{i}^{j} for j ≥ 1 and i ∈ [1, n_{j} + 1]. Next let x^{(2)} be the ω-word obtained from x^{(1)} by using the (code of the) eraser ↞_{2} as an eraser which may erase letters 0, 1, and (codes of the) erasers ↞_{p} for p > 2. Again these erasing operations occur inside the words v_{i}^{j}. We can now iterate this process. Assume that, after having successively used the erasers ↞_{1}, ↞_{2}, …, ↞_{n}, for some integer n ≥ 1, we have got the ω-word x^{(n)} from the ω-word x. We can now define x^{(n+1)} as the ω-word obtained from x^{(n)} by using the (code of the) eraser ↞_{n+1} as an eraser which may erase letters 0, 1, and (codes of the) erasers ↞_{p} for p > n + 1.

We shall denote K_{(i,j)} = min{k ≥ 1 | v_{i}^{j} ∈ φ_{k}(L_{k})}. Then v_{i}^{j} ∈ φ_{K_{(i,j)}}(L_{K_{(i,j)}}) for all integers j ≥ 1 and i ∈ [1, n_{j} + 1]. Thus after K_{j} = max{K_{(i,j)} | i ∈ [1, n_{j} + 1]} steps all words v_{i}^{j}, for i ∈ [1, n_{j} + 1], have been completely erased and, from the finite word u_{j}, it remains only the finite word 0^{n_{j}}.1. After K^{J} = max{K_{j} | j ∈ [1, J]} steps, from the word u_{1}.u_{2} … u_{J}, it remains the word

0^{n_{1}}.1.0^{n_{2}}.1.0^{n_{3}}.1 … 0^{n_{J}} .1

which is a strict prefix of x^{(K^{J})}. In particular the J-th letter 1 of x^{(K^{J})} is the last letter of u_{J}, which has not been erased, and it will not be erased by next erasing operations.

Notice that the successive erasing operations are in fact applied to x independently of the decomposition of x in words of h(V). So consider now the above erasing operations applied to x given by its second decomposition. Let K′_{(i,j)} = min{k ≥ 1 | w_{i}^{j} ∈ φ_{k}(L_{k})}, and K^{′J} = max{K′_{(i,j)} | j ∈ [1, J] and i ∈ [1, n′_{j} + 1]}. K^{j} = K^{′j} holds for 1 ≤ j < J and K^{J} ≤ K^{′J}. We see that, after K^{′J} steps, the word 0^{n_{1}}.1.0^{n_{2}}.1.0^{n_{3}}.1 … 0^{n_{J−1}}.1.0^{n′_{J}} .1 is a strict prefix of x^{(K^{′J})}. The J-th letter 1 of x^{(K^{′J})} is the last letter of u′_{J} (which has not been erased). But we have seen above that it is also the last letter of u_{J} (which has not been erased). Thus we would have u_{J} = u′_{J} and this leads to a contradiction. □

Remark that in terms of code theory Lemma 3.4 states that the language h(V) is an ω-code.

Lemma 3.5. The set (h(V))^{ω} is a Borel set.

Proof. Assume on the contrary that (h(V))^{ω} is an analytic but non Borel set. Recall that lemma 4.1 of [6] states that if X and Y are finite alphabets having at least two letters and B is a Borel subset of X^{ω} × Y^{ω} such that P ROJ_{X^{ω}}(B) = {σ ∈ X^{ω} | ∃ν (σ, ν) ∈ B} is not Borel, then there are 2^{ℵ_{0}} ω-words σ ∈ X^{ω} such that B_{σ} = {ν ∈ Y^{ω} | (σ, ν) ∈ B} has cardinality 2^{ℵ_{0}} (where 2^{ℵ_{0}} is the cardinal of the continuum). We can now reason as in the proof of Fact 4.5 in [6]. Let θ be a recursive enumeration of the set h(V). The function θ : ℕ → h(V) is a bijection and we denote u_{i} = θ(i). Let now D be the set of pairs (σ, ν) ∈ {0, 1}^{ω} × {0, 1, α, β}^{ω} such that:

1. σ ∈ (0^{⋆}.1)^{ω}, so σ may be written in the form

σ = 0^{n_{1}}.1.0^{n_{2}}.1.0^{n_{3}}.1 … 0^{n_{p}}.1.0^{n_{p+1}}.1 …

where ∀i ≥ 1 n_{i} ≥ 0, and

2.

ν = u_{n_{1}}.u_{n_{2}}.u_{n_{3}} … u_{n_{p}}.u_{n_{p+1}} …

D is a Borel subset of {0, 1}^{ω} × {0, 1, α, β}^{ω} because it is accepted by a deterministic Turing machine with a Büchi acceptance condition [17]. But P ROJ_{{0,1,α,β}^{ω}}(D) = (h(V))^{ω} would be a non Borel set thus there would be 2^{ℵ_{0}} ω-words ν in (h(V))^{ω} such that D_{ν} has cardinality 2^{ℵ_{0}}. This means that there would exist 2^{ℵ_{0}} ω-words ν ∈ (h(V))^{ω} having 2^{ℵ_{0}} decompositions in words in h(V). This would lead to a (strong) contradiction with Lemma 3.4. □

Theorem 3.1 follows now directly from Lemmas 3.3 and 3.5.

4. Concluding Remarks

We already knew that there are ω-powers of every finite Borel rank [4]. We have proved that there exists some ω-powers of infinite Borel rank. The language h(V) is very simple to describe. It is obtained by substituting in the regular language V = (0^{⋆}.1) the language L.a to each letter a ∈ {0, 1}, where L = ⋃_{n≥1} φ_{n}(L_{n}). Notice that the language L is not context free but it is the union of the increasing sequence of context free languages φ_{n}(L_{n}). Then L is a very simple recursive language and so is h(V). The question is left open whether there is a context free language W such that W^{ω} is Borel of infinite rank. The question also naturally arises to know what are all the possible infinite Borel ranks of ω-powers of finitary languages or of finitary languages belonging to some natural class like the class of context free languages (respectively, languages accepted by stack automata, recursive languages, recursively enumerable languages, …).

Acknowledgements. We thank the anonymous referee for useful comments on a preliminary version of this paper.

References

[1] Autebert, J.-M., Berstel, J., Boasson, L.: Context free languages and pushdown automata, in: Handbook of formal languages, Vol. 1, Springer-Verlag, 1996.

[2] Berstel, J.: Transductions and context free languages, Teubner Studienbücher Informatik, 1979.

[3] Duparc, J.: Wadge hierarchy and Veblen hierarchy: Part 1: Borel sets of finite rank, Journal of Symbolic Logic, 66(1), 2001, 56–86.

[4] Finkel, O.: Topological properties of omega context free languages, Theoretical Computer Science, 262(1–2), 2001, 669–697.

[5] Finkel, O.: Borel hierarchy and omega context free languages, Theoretical Computer Science, 290(3), 2003, 1385–1405.

[6] Finkel, O., Simonnet, P.: Topology and ambiguity in omega context free languages, Bulletin of the Belgian Mathematical Society, 10(5), 2003, 707–722.

[7] Hopcroft, J. E., Ullman, J. D.: Introduction to automata theory, languages, and computation, Addison-Wesley Publishing Co., Reading, Mass., 1979, Addison-Wesley Series in Computer Science.

[8] Kechris, A. S.: Classical descriptive set theory, Springer-Verlag, New York, 1995, ISBN 0-387-94374-9.

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

[10] Lecomte, D.: Sur les ensembles de phrases infinies constructibles a partir d’un dictionnaire sur un alphabet fini, in: Séminaire d’Initiation a l’Analyse, Vol. 1, Université Paris 6, 2001–2002.

[11] Lescow, H., Thomas, W.: Logical specifications of infinite computations, A Decade of Concurrency (J. W. de Bakker, W. P. de Roever, G. Rozenberg, Eds.), 803, Springer, 1994.

[12] Moschovakis, Y. N.: Descriptive set theory, North-Holland Publishing Co., Amsterdam, 1980, ISBN 0-444-85305-7.

[13] Niwinski, D.: A problem on ω-powers, 1990 Workshop on Logics and Recognizable Sets, University of Kiel, 1990.

[14] Perrin, D., Pin, J.-E.: Infinite words, automata, semigroups, logic and games, vol. 141 of Pure and Applied Mathematics, Elsevier, 2004.

[15] Simonnet, P.: Automates et théorie descriptive, Ph.D. Thesis, Université Paris VII, 1992.

[16] Staiger, L.: Hierarchies of recursive ω-languages, Elektronische Informationsverarbeitung und Kybernetik, 22(5-6), 1986, 219–241, ISSN 0013-5712.

[17] Staiger, L.: ω-languages, in: Handbook of formal languages, Vol. 3, Springer, Berlin, 1997, 339–387.

[18] Staiger, L.: On ω-power languages, in: New Trends in Formal Languages, Control, Coperation, and Combinatorics, vol. 1218 of Lecture Notes in Computer Science, Springer-Verlag, Berlin, 1997, 377–393.

[19] Thomas, W.: Automata on infinite objects, in: Handbook of Theoretical Computer Science (J. van Leeuwen, Ed.), vol. B, Formal models and semantics, Elsevier, 1990, 135–191.