Theoretical Informatics and Applications Will be set by the publisher

Informatique Théorique et Applications

ON THE TOPOLOGICAL COMPLEXITY OF INFINITARY RATIONAL RELATIONS

Olivier Finkel^{1}

Abstract. We prove in this paper that there exists some infinitary rational relations which are analytic but non Borel sets, giving an answer to a question of Simonnet [Sim92].

Résumé. We prove in this paper that there exists some infinitary rational relations which are analytic but non Borel sets, giving an answer to a question of Simonnet [Sim92].

1991 Mathematics Subject Classification. 68Q45; 03D05; 03D55; 03E15.

1. Introduction

Acceptance of infinite words by finite automata was firstly considered by Büchi in order to study decidability of the monadic second order theory of one successor over the integers [Büc62]. Then the so called ω-regular languages have been intensively studied and many applications have been found, see [Tho90] [Sta97] [PP01] for many results and references. Rational relations on finite words were studied in the sixties and played a fundamental role in the study of families of context free languages [Ber79]. Their extension to rational relations on infinite words was firstly investigated by Gire and Nivat [Gir81] [GN84]. Infinitary rational relations are subsets of Σ_{1}^{ω} × Σ_{2}^{ω}, where Σ_{1} and Σ_{2} are finite alphabets, which are recognized by Büchi transducers or by 2-tape finite Büchi automata with asynchronous reading heads (there exists an extension to subsets of Σ_{1}^{ω}×Σ_{2}^{ω}×…×Σ_{n}^{ω} recognized by n-tape Büchi automata, with Σ_{1}, …, Σ_{n} some finite alphabets, but we shall not need to consider it). Since then they have been much studied, in particular in connection with the rational

\begin{matrix}c \\ ◯ \end{matrix} EDP Sciences 1999

Keywords and phrases: Infinitary rational relations; topological properties; Borel and analytic

sets.

1 Equipe de Logique Mathématique, U.F.R. de Mathématiques, Université Paris 7, 2 Place

Jussieu, 75251 Paris cedex 05, France; e-mail: finkel@logique.jussieu.fr

functions they may define, see for example [CG99] [BC00] [Sim92] [Sta97] [Pri00] for many results and references.

The question of the complexity of such relations on infinite words naturally arises. A way to investigate the complexity of infinitary rational relations is to consider their topological complexity and particularly to locate them with regard to the Borel and the projective hierarchies. It is well known that every ω-language accepted by a Turing machine with a Büchi or Muller acceptance condition is an analytic set, [Sta97], thus every infinitary rational relation is an analytic set. Simonnet asked in [Sim92] whether there exists some infinitary rational relation which is an analytic but non Borel set. We give in this paper a positive answer to this question showing that there exists some non Borel (and even Σ_{1}^{1}-complete) infinitary rational relation. The paper is organized as follows. In section 2 we introduce the notion of transducers and of infinitary rational relations. In section 3 we recall definitions of Borel and analytic sets, and we prove our main result in section 4.

2. Infinitary rational relations

Let Σ be a finite alphabet whose elements are called letters. A non-empty finite word over Σ is a finite sequence of letters: x = a_{1}a_{2} … a_{n} where ∀i ∈ [1; n] a_{i} ∈ Σ. We shall denote x(i) = a_{i} the i^{th} letter of x and x[i] = x(1) … x(i) for i ≤ n. The length of x is |x| = n. The empty word will be denoted by λ and has 0 letter. Its length is 0. The set of finite words over Σ is denoted Σ^{⋆}. Σ^{+} = Σ^{⋆} − {λ} is the set of non empty words over Σ. A (finitary) language L over Σ is a subset of Σ^{⋆}. The usual concatenation product of u and v will be denoted by u.v or just uv. For V ⊆ Σ^{⋆}, we denote V^{⋆} = {v_{1} … v_{n}/n ∈ ℕ and v_{i} ∈ V ∀i ∈ [1; n]}.

The first infinite ordinal is ω. An ω-word over Σ is an ω -sequence a_{1}a_{2} … 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 Σ^{ω}. For V ⊆ Σ^{⋆}, V^{ω} = {σ = u_{1} … u_{n} … ∈ Σ^{ω}/u_{i} ∈ V, ∀i ≥ 1} is the ω-power of V. The concatenation product is extended to the product of a finite word u and an ω-word v: the infinite word u.v is then the ω-word such that: (u.v)(k) = u(k) if k ≤ |u| , and (u.v)(k) = v(k − |u|) if k > |u|. The prefix relation is denoted ⊑: the finite word u is a prefix of the finite word v (respectively, the infinite word v), denoted u ⊑ v, if and only if there exists a finite word w (respectively, an infinite word w), such that v = u.w.

We assume the reader to be familiar with the theory of formal languages and of ω-regular languages, see [Büc62] [Tho90] [EH93] [Sta97] [PP01] for many results and references. We recall that ω-regular languages form the class of ω-languages accepted by finite automata with a Büchi acceptance condition and this class is the omega Kleene closure of the class of regular finitary languages.

We are going now to introduce the notion of infinitary rational relation which extends the notion of ω-regular language, via definition by Büchi transducers: Definition 2.1. A Büchi transducer is a sextuple T = (K, Σ, Γ, Δ, q_{0}, F), where K is a finite set of states, Σ and Γ are finite sets called the input and the output alphabets, Δ is a finite subset of K × Σ^{⋆} × Γ^{⋆} × K called the set of transitions, q_{0} is the initial state, and F ⊆ K is the set of accepting states. A computation C of the transducer T is an infinite sequence of transitions

(q_{0}, u_{1}, v_{1}, q_{1}), (q_{1}, u_{2}, v_{2}, q_{2}), … (q_{i−1}, u_{i}, v_{i}, q_{i}), (q_{i}, u_{i+1}, v_{i+1}, q_{i+1}), …

The computation is said to be successful iff there exists a final state q_{f} ∈ F and infinitely many integers i ≥ 0 such that q_{i} = q_{f}. The input word of the computation is u = u_{1}.u_{2}.u_{3} … The output word of the computation is v = v_{1}.v_{2}.v_{3} … Then the input and the output words may be finite or infinite. The infinitary rational relation R(T ) ⊆ Σ^{ω} × Γ^{ω} recognized by the Büchi transducer T is the set of couples (u, v) ∈ Σ^{ω} × Γ^{ω} such that u and v are the input and the output words of some successful computation C of T . The set of infinitary rational relations will be denoted RAT. Remark 2.2. An infinitary rational relation is a subset of Σ^{ω} × Γ^{ω} for two finite alphabets Σ and Γ. One can also consider that it is an ω-language over the finite alphabet Σ × Γ. If (u, v) ∈ Σ^{ω} × Γ^{ω}, one can consider this couple of infinite words as a single infinite word (u(1), v(1)).(u(2), v(2)).(u(3), v(3)) … over the alphabet Σ × Γ. We shall use this fact to investigate the topological complexity of infinitary rational relations.

3. Borel and analytic sets

We assume the reader to be familiar with basic notions of topology which may be found in [Kur66] [Mos80] [Kec95] [LT94] [Sta97] [PP01]. For a finite alphabet X having at least two letters we shall 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. We define now the next classes of the Borel Hierarchy: Definition 3.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^{ω}. 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: Σ_{α}^{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}. There are also some subsets of X^{ω} which are not Borel sets. In particular the class of Borel subsets of X^{ω} is strictly included into the class Σ_{1}^{1} of analytic subsets of X^{ω}. A subset A of X^{ω} is an analytic set iff there exists another finite set Y and a Borel subset B of (X × Y)^{ω} such that x ∈ A ↔ ∃y ∈ Y^{ω} such that (x, y) ∈ B, where (x, y) is the infinite word over the alphabet X × Y such that (x, y)(i) = (x(i), y(i)) for each integer i ≥ 1.

Recall also the notion of completeness with regard to reduction by continuous functions. If α be a countable ordinal, 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}, Σ_{1}^{1}) iff there exists a continuous function f : Y^{ω} → X^{ω} such that E = f^{−1}(F). A Σ_{α}^{0} (respectively Π_{α}^{0}, Σ_{1}^{1})-complete set is a Σ_{α}^{0} (respectively Π_{α}^{0}, Σ_{1}^{1})- set which is in some sense a set of the highest topological complexity among the Σ_{α}^{0} (respectively Π_{α}^{0}, Σ_{1}^{1})- sets. Σ_{n}^{0} (respectively Π_{n}^{0})-complete sets, with n an integer ≥ 1, are thoroughly characterized in [Sta86].

The ω-language A = (0^{⋆}.1)^{ω} is a well known example of Π_{2}^{0}-complete set which will be used below. It is the set of ω-words over the alphabet {0, 1} with infinitely many occurrences of the letter 1.

4. Σ_{1}^{1}-complete infinitary rational relations

We can now state our main result: Theorem 4.1. There exists some Σ_{1}^{1}-complete (hence non Borel) infinitary rational relations.

Proof. We shall use here results about languages of infinite binary trees whose nodes are labelled in a finite alphabet Σ. A node of an infinite binary tree is represented by a finite word over the alphabet {l, r} where r means ”right” and l means ”left”. Then an infinite binary tree whose nodes are labelled in Σ is identified with a function t : {l, r}^{⋆} → Σ. The set of infinite binary trees labelled in Σ will be denoted T_{Σ}^{ω}.

There is a natural topology on this set T_{Σ}^{ω} [Mos80], [LT94], [Sim92]. It is defined by the following distance. Let t and s be two distinct infinite trees in T_{Σ}^{ω}. Then the distance between t and s is \frac{1}{2^{n}} where n is the smallest integer such that t(x) ≠ s(x) for some word x ∈ {l, r}^{⋆} of length n. The open sets are then in the form T_{0}.T_{Σ}^{ω} where T_{0} is a set of finite labelled trees. T_{0}.T_{Σ}^{ω} is the set of infinite binary trees which extend some finite labelled binary tree t_{0} ∈ T_{0}, t_{0} is here a sort of prefix, an ”initial subtree” of a tree in t_{0}.T_{Σ}^{ω}. For an alphabet Σ having at least two letters the topological space T_{Σ}^{ω} is homeomorphic to the Cantor set Σ^{ω}. Borel and analytic subsets of T_{Σ}^{ω} are defined from open sets in the same manner as in the case of the topological space Σ^{ω}.

Let t be a tree. A branch B of t is a subset of the set of nodes of t which is linearly ordered by the tree partial order ⊑ and which is closed under prefix relation, i.e. if x and y are nodes of t such that y ∈ B and x ⊑ y then x ∈ B. A branch B of a tree is said to be maximal iff there is not any other branch of t which strictly contains B.

Let t be an infinite binary tree in T_{Σ}^{ω}. If B is a maximal branch of t, then this branch is infinite. Let (u_{i})_{i≥0} be the enumeration of the nodes in B which is strictly increasing for the prefix order. The infinite sequence of labels of the nodes of such a maximal branch B, i.e. t(u_{0})t(u_{1})....t(u_{n})..... is called a path. It is an ω-word over the alphabet Σ.

Let then L ⊆ Σ^{ω} be an ω-language over Σ. We denote P ath(L) the set of infinite trees t in T_{Σ}^{ω} such that t has at least one path in L.

It is well known that if L ⊆ Σ^{ω} is an ω-language over Σ which is a Π_{2}^{0}-complete subset of Σ^{ω} (or a Borel set of higher complexity in the Borel hierarchy) then the set P ath(L) is a Σ_{1}^{1}-complete subset of T_{Σ}^{ω}. Hence in particular P ath(L) is not a Borel set, [Niw85] [Sim93] [Sim92].

Whenever B ⊆ Σ^{ω} is a regular ω-language, we shall find a rational relation R ⊆ (Σ ∪ {A})^{ω} × (Σ ∪ {A})^{ω} and a continuous function

h : T_{Σ}^{ω} → ((Σ ∪ {A}) × (Σ ∪ {A}))^{ω}

such that P ath(B) = h^{−1}(R). For that we shall code trees labelled in Σ by words over the finite alphabet (Σ ∪ {A}) × (Σ ∪ {A}) where A is supposed to be a new letter not in Σ.

Consider now the set {l, r}^{⋆} of nodes of binary infinite trees. For each integer n ≥ 0, call C_{n} the set of words of length n of {l, r}^{⋆}. Then C_{0} = {λ}, C_{1} = {l, r}, C_{2} = {ll, lr, rl, rr} and so on. C_{n} is the set of nodes which appear in the (n + 1)^{th} level of an infinite binary tree. The number of nodes of C_{n} is card(C_{n}) = 2^{n}. We consider now the lexicographic order on C_{n} (assuming that l is before r for this order). Then, in the enumeration of the nodes with regard to this order, the nodes of C_{1} will be: l, r; the nodes of C_{3} will be: lll, llr, lrl, lrr, rll, rlr, rrl, rrr. Let u_{1}^{n}, ..., u_{j}^{n}, ..., u_{2^{n}}^{n} be such an enumeration of C_{n} in the lexicographic order and let v_{1}^{n}, ..., v_{j}^{n}, ..., v_{2^{n}}^{n} be the enumeration of the elements of C_{n} in the reverse order. Then for all integers n ≥ 0 and i, 1 ≤ i ≤ 2^{n}, it holds that v_{i}^{n} = u_{2^{n}+1−i}^{n}.

We define now the code of a tree t in T_{Σ}^{ω}. Let A be a new letter not in Σ. The code of the tree t is an ω-word σ over the alphabet (Σ ∪ {A}) × (Σ ∪ {A}) which may be written in the form (σ_{1}, σ_{2}), where σ_{1} and σ_{2} are ω-words over the alphabet (Σ ∪ {A}).

The ω-word σ_{1} enumerates the labels of the nodes of the tree t which appear at levels 1, 3, 5, …, 2n + 1, …, i.e. at odd levels. More precisely the word σ_{1} begins with the label t(v_{1}^{0}) of the node at level 1, followed by an A, followed by the labels of the nodes of the third level enumerated in the reverse lexicographic order, i.e. t(v_{1}^{2})t(v_{2}^{2})t(v_{3}^{2})t(v_{4}^{2}), followed by an A, followed by the labels of the nodes of the 5^{th} level enumerated in the reverse lexicographic order, i.e. t(v_{1}^{4})t(v_{2}^{4})t(v_{3}^{4}) … t(v_{16}^{4}), and so on … For each integer n ≥ 0, the labels of the nodes of C_{2n}, enumerated in the reverse lexicographic order, are placed before those of C_{2n+2} and these two sets of labels are separated by an A.

The construction of the ω-word σ_{2} is very similar but it successively enumerates, in the lexicographic order, the labels of nodes occuring at even levels. So the word σ_{2} is in the form

σ_{2} = t(u_{1}^{1})t(u_{2}^{1})At(u_{1}^{3})t(u_{2}^{3})t(u_{3}^{3})t(u_{4}^{3})t(u_{5}^{3})t(u_{6}^{3})t(u_{7}^{3})t(u_{8}^{3})A …

For each integer n ≥ 0, the labels of the nodes of C_{2n+1} are enumerated before those of C_{2n+3} and these two sets of labels are separated by an A. Moreover the labels of the nodes of C_{2n+1}, for n ≥ 0, are enumerated in the lexicographic order (for the nodes).

Let then h be the mapping from T_{Σ}^{ω} into ((Σ∪{A})×(Σ∪{A}))^{ω} such that for every labelled binary infinite tree t of T_{Σ}^{ω}, h(t) is the code (σ_{1}, σ_{2}) of the tree as defined above. It is easy to see, from the definition of h and of the order of the enumeration of labels of nodes (they are enumerated level after level in the increasing order), that h is a continuous function from T_{Σ}^{ω} into ((Σ ∪ {A}) × (Σ ∪ {A}))^{ω}.

Now we are looking for a rational relation R such that for every tree t ∈ T_{Σ}^{ω}, h(t) ∈ R if and only if t has a path in B. Then we shall have P ath(B) = h^{−1}(R).

We shall first describe the rational relation R which is an ω-language over the alphabet ((Σ ∪ {A}) × (Σ ∪ {A})). Every word of R may be seen as a couple y = (y_{1}, y_{2}) of ω-words over the alphabet Σ ∪ {A}. Now y = (y_{1}, y_{2}) is in R if and only if it is in the form

y_{1} = x(1).u_{1}.A.v_{2}.x(3).u_{3}.A.v_{4}.x(5).u_{5}.A. … A.v_{2n}.x(2n + 1).u_{2n+1}.A … y_{2} = v_{1}.x(2).u_{2}.A.v_{3}.x(4).u_{4}.A. … A.v_{2n+1}.x(2n + 2).u_{2n+2}.A … where for all integers i ≥ 1, x(i) ∈ Σ and u_{i}, v_{i} ∈ Σ^{⋆} and

|v_{i}| = 2|u_{i}| or |v_{i}| = 2|u_{i}| + 1

and the ω-word x = x(1)x(2) … x(n) … is in B.

If such an ω-word y = (y_{1}, y_{2}) is the code h(t) of a tree t ∈ T_{Σ}^{ω}, then x(1) = t(v_{1}^{0}) and u_{1} = λ, then |v_{1}| = 2|u_{1}| = 0 or |v_{1}| = 2|u_{1}| + 1 = 1. Therefore if |v_{1}| = 0 then x(2) = t(u_{1}^{1}) and if |v_{1}| = 1 then x(2) = t(u_{2}^{1}). Then the choice of |v_{1}| = 2|u_{1}| or of |v_{1}| = 2|u_{1}| + 1 implies that x(2) is the label of the left or the rigth successor of the root node v_{1}^{0} = λ.

By construction this phenomenon will happen for further levels. The choice of |v_{i}| = 2|u_{i}| or of |v_{i}| = 2|u_{i}| + 1 determines one of the two successor nodes of a node at level i thus the successive choices determine a branch of t and the labels of nodes of this branch form a path x(1)x(2)x(3) … x(n) … which is in B. Thus for a tree t ∈ T_{Σ}^{ω}, h(t) ∈ R if and only if t ∈ P ath(B) then P ath(B) = h^{−1}(R). Remark that R does not contain only codes of trees but such a code h(t) is in R iff t ∈ P ath(B) and this fact suffices for our proof.

Hence if B is a Borel set which is a Π_{2}^{0}-complete subset of Σ^{ω} (or a set of higher complexity in the Borel hierarchy), the language h^{−1}(R) = P ath(B) is a Σ_{1}^{1}- complete subset of T_{Σ}^{ω}. Then the ω-language R is at least Σ_{1}^{1}-complete because h is a continuous function. Note that here h is a continuous function: T_{Σ}^{ω} → ((Σ∪{A})×(Σ∪{A}))^{ω} and the preceding definition of Σ_{1}^{1}-complete set involves continuous reductions: X^{ω} → Y^{ω}; but the two topological spaces T_{Σ}^{ω} and Y^{ω} have good similar properties (they are zero-dimensional polish spaces, see [PP01] [Kec95] [Sim92], in fact they are homeomorphic) which enable to extend the previous definition to this new case. Indeed R is a Σ_{1}^{1}-complete subset of ((Σ ∪ {A}) × (Σ ∪ {A}))^{ω} because every infinitary rational relation is a Σ_{1}^{1}-set. Then in that case R is not a Borel set because a Σ_{1}^{1}-complete set is not a Borel set. This gives infinitely many non Borel infinitary rational relations, because there exist infinitely many Π_{2}^{0}-complete ω-regular languages.

It remains to show that if B is an ω-regular language then R is an infinitary rational relation. In fact this is easy to see from the definition of R. We shall explicitely give a Büchi transducer defining R in the following simple case: Σ = {0, 1} and B = (0^{⋆}.1)^{ω} is a well known example of Π_{2}^{0}-complete ω-regular language.

The infinitary rational relation R is then recognized by the following Büchi transducer T = (K, (Σ ∪ {A}), (Σ ∪ {A}), Δ, q_{0}, F), where

K = {q_{0}, q_{1}, q_{2}, q_{3}, q_{4}, q_{1}^{0}, q_{1}^{1}, q_{2}^{0}, q_{2}^{1}}

is a finite set of states, {0, 1, A} is the input and the output alphabet, q_{0} is the initial state, and F = {q_{1}^{1}, q_{2}^{1}} is the set of accepting states. Moreover Δ ⊆ K × (Σ ∪ {A})^{⋆} × (Σ ∪ {A})^{⋆} × K is the finite set of transitions, containing the following transitions:

(q_{0}, 0, λ, q_{1}) and (q_{0}, 1, λ, q_{1}), (q_{1}, u, v, q_{1}), for all words u, v ∈ Σ^{⋆} with |u| = 1 and |v| = 2, (q_{1}, λ, v, q_{2}), for v ∈ {0, 1, λ}, (q_{2}, A, 0, q_{1}^{0}) and (q_{2}, A, 1, q_{1}^{1}), (q, u, v, q_{3}), for all u, v ∈ Σ^{⋆} with |u| = 2 and |v| = 1 and q ∈ {q_{1}^{0}, q_{1}^{1}, q_{3}}, (q, u, λ, q_{4}), for u ∈ {0, 1, λ} and q ∈ {q_{1}^{0}, q_{1}^{1}, q_{3}}, (q_{4}, 0, A, q_{2}^{0}) and (q_{4}, 1, A, q_{2}^{1}), (q_{2}^{0}, λ, λ, q_{1}) and (q_{2}^{1}, λ, λ, q_{1}). □

Remark 4.2. We could of course have avoided the set of transitions to contain some transitions with both the input and the output words being empty, like the two last ones: (q_{2}^{0}, λ, λ, q_{1}) and (q_{2}^{1}, λ, λ, q_{1}). Remark 4.3. We have shown that there exists some infinitary rational relations which are Σ_{1}^{1}-complete hence non Borel. In particular this implies that these infinitary rational relations are not arithmetical sets because every arithmetical set is a Borel set (of finite rank). We refer to [Sta86] [Sta97] for definitions and results about the arithmetical hierarchy over sets of infinite words over a finite alphabet Σ. Remark 4.4. From the preceding example we can easily find a Σ_{1}^{1}-complete infinitary rational relation in the form S^{ω} where S is a rational relation over finite words, see [Ber79] [Gir81] [Pri00] about finitary rational relations. Acknowledgements. Thanks to Jean-Pierre Ressayre and Pierre Simonnet for useful discussions.

References

[BC00] M.-P. Béal and O. Carton, Determinization of Transducers over Infinite Words, in ICALP’2000 (U. Montanari et al., eds.), vol. 1853 of Lect. Notes in Comput. Sci., pp. 561-570, 2000.

[Ber79] J. Berstel, Transductions and Context Free Languages, Teubner Verlag, 1979. [Büc62] 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.

[Cho77] C. Choffrut, Une Caractérisation des Fonctions Séquentielles et des Fonctions Sous-Séquentielles en tant que Relations Rationnelles, Theoretical Computer Science, Volume 5, 1977, p.325-338.

[CG99] C. Choffrut and S. Grigorieff, Uniformization of Rational Relations, Jewels are Forever 1999, J. Karhumäki, H. Maurer, G. Paun and G. Rozenberg editors, Springer, p.59-71.

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

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

[Gir81] F. Gire, Relations Rationnelles Infinitaires, Thèse de troisième cycle, Université Paris 7, Septembre 1981.

[Gir83] F. Gire, Une Extension aux Mots Infinis de la Notion de Transduction Rationnelle, 6th GI Conf., Lect. Notes in Comp. Sci., Volume 145, 1983, p. 123-139.

[GN84] F. Gire and M. Nivat, Relations Rationnelles Infinitaires, Calcolo, Volume XXI, 1984, p. 91-125.

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

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

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

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

[Niw85] D. Niwinski, An Example of Non Borel Set of Infinite Trees Recognizable by a Rabin Automaton, in Polish, Manuscript, University of Warsaw, 1985.

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

[Pin96] J-E. Pin, Logic, Semigroups and Automata on Words, Annals of Mathematics and Artificial Intelligence 16 (1996), p. 343-384.

[Pri00] C. Prieur, Fonctions Rationnelles de Mots Infinis et Continuité, Thèse de Doctorat, Université Paris 7, Octobre 2000.

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

[Sim93] P. Simonnet, Automate d’ Arbres Infinis et Choix Borélien, C.R.A.S. Paris, t.316, Série 1, p. 97-100, 1993.

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

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

Communicated by (The editor will be set by the publisher).