Theoretical Informatics and Applications Will be set by the publisher

Informatique Théorique et Applications

UNDECIDABILITY OF TOPOLOGICAL AND ARITHMETICAL PROPERTIES OF INFINITARY

RATIONAL RELATIONS

Olivier Finkel^{1}

Abstract. We prove that for every countable ordinal α one cannot decide whether a given infinitary rational relation is in the Borel class Σ_{α}^{0} (respectively Π_{α}^{0}). Furthermore one cannot decide whether a given infinitary rational relation is a Borel set or a Σ_{1}^{1}-complete set. We prove some recursive analogues to these properties. In particular one cannot decide whether an infinitary rational relation is an arithmetical set. We then deduce from the proof of these results some other ones, like: one cannot decide whether the complement of an infinitary rational relation is also an infinitary rational relation.

Résumé. Nous prouvons que pour tout ordinal dénombrable α on ne peut pas décider si une relation rationnelle infinitaire donnée est dans la classe borélienne Σ_{α}^{0} (respectivement Π_{α}^{0}). De plus on ne peut pas décider si une relation rationnelle infinitaire donnée est un ensemble Borélien ou un ensemble Σ_{1}^{1}-complet. Des analogues récursifs sont aussi prouvés: en particulier on ne peut pas décider si une relation rationnelle infinitaire donnée est un ensemble arithmétique. De la preuve des résultats précédents nous en déduisons d’autres, comme l’indécidabilité du problème suivant: “le complémentaire d’une relation rationnelle infinitaire donnée est-il aussi une relation rationnelle infinitaire?”.

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

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

Keywords and phrases: Infinitary rational relations; topological properties; Borel and analytic sets; arithmetical properties; decision problems.

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

1. Introduction

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. So the class RAT_{ω} of infinitary rational relations extends the class RAT of finitary rational relations and the class of ω-regular languages (firstly considered by Büchi in order to study the decidability of the monadic second order theory of one successor over the integers [Büc62], see [Tho90] [Sta97] [PP01] for many results and references). Infinitary rational relations and rational functions over infinite words they may define have been much studied, see for example [CG99] [BCPS00] [Sim92] [Sta97]

[Pri00] [Pri01] 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. We have shown in [Fin01b] that there exist some infinitary rational relations which are Σ_{3}^{0}-complete and some others which are Π_{3}^{0}-complete and in [Fin01a] that there exist some infinitary rational relations which are Σ_{1}^{1}-complete hence non Borel sets.

The question of the decidability of the topological complexity of infinitary rational relations also naturally arises. Mac Naughton’s Theorem implies that every ω-regular language is a boolean combination of Π_{2}^{0}-sets, [Tho90] [Sta97] [PP01] and Landweber proved that one can decide, for a given ω-regular language R , whether R is in the Borel class Σ_{1}^{0} (respectively, Π_{1}^{0}, Σ_{2}^{0}, Π_{2}^{0}), [Lan69]. We show in this paper that the above decidability results can not be extended to rational relations over infinite words: for every countable ordinal α one cannot decide whether a given infinitary rational relation is in the Borel class Σ_{α}^{0} ( respectively Π_{α}^{0}). Furthermore one cannot even decide whether a given infinitary rational relation is a Borel set or a Σ_{1}^{1}-complete set. Then we prove some recursive analogues to these properties. In particular one cannot decide whether an infinitary rational relation is an arithmetical set. The proof of the above results implies some other properties like the undecidability of the rationality of the complement of an infinitary rational relation.

The paper is organized as follows. In section 2 we introduce the notion of rational relations over finite or infinite words. We prove our main results about undecidability of topological and arithmetical properties in section 3. Other results are proved in section 4.

2. Rational relations

Let us now introduce notations for words. 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 n ≥ 1 and ∀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 ≥ 1 and ∀i ∈ [1; n] v_{i} ∈ V } ∪ {λ}. The complement Σ^{⋆} − L of a finitary language L ⊆ Σ^{⋆} will be denoted L^{−}.

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. The complement Σ^{ω} − L of an ω-language L ⊆ Σ^{ω} will be denoted L^{−}.

A relation over finite words is a subset of Σ^{⋆} × Γ^{⋆} where Σ and Γ are two finite alphabets, so it is a set of couples of words. The complement (Σ^{⋆} × Γ^{⋆}) − R of a relation R ⊆ Σ^{⋆} × Γ^{⋆} will be denoted R^{−}. The usual concatenation product can be extended to couples of words: if (u, v) ∈ Σ^{⋆} × Γ^{⋆} and (w, t) ∈ Σ^{⋆} × Γ^{⋆} then (u, v).(w, t) = (u.w, v.t). Then the star operation is defined for U ⊆ Σ^{⋆} × Γ^{⋆} by U^{⋆} = ∪_{n≥1}U^{n} ∪ {(λ, λ)} where U^{n} = {(u_{1}.u_{2} … u_{n}, v_{1}.v_{2} … v_{n}) | ∀i ≥ 1 (u_{i}, v_{i}) ∈ U}. The set RAT (Σ^{⋆} × Γ^{⋆}) of rational relations is the smallest family of subsets of Σ^{⋆} ×Γ^{⋆} which contains the emptyset, the singletons {(a, λ)} and {(λ, b)} for a ∈ Σ and b ∈ Γ, and which is closed under finite union, concatenation product and star operation. We call RAT the union of the sets RAT (Σ^{⋆} × Γ^{⋆}) where Σ and Γ are two finite alphabets.

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, [Tho90] [Sta97] [PP01]. A relation over infinite words (or infinitary relation) is a subset of Σ^{ω} × Γ^{ω} where Σ and Γ are two finite alphabets, so it is a set of couples of infinite words. The complement (Σ^{ω} × Γ^{ω}) − R of an infinitary relation R ⊆ Σ^{ω} × Γ^{ω} will be denoted R^{−}.

We refer for example to [GN84] or to [Fin01a] for the definition of infinitary rational relations via Büchi transducers. As in the case of ω-regular languages it turned out that an infinitary relation R ⊆ Σ^{ω} × Γ^{ω} is rational if and only if it is in the form R = ∪_{1≤i≤n}S_{i}.R_{i}^{ω} where for all integers i ∈ [1, n] S_{i} and R_{i} are rational relations over finite words and the ω-power U^{ω} of a finitary rational relation U is naturally defined by U^{ω} = {u_{1}.u_{2} … u_{n} … | ∀i u_{i} ∈ U}.

Infinitary rational relations are also characterized as images of ω-regular languages by bimorphisms, [GN84]. This implies the following property which will be useful in the sequel. Proposition 2.1. Let Σ, Σ_{1}, Γ and Γ_{1} be finite alphabets and h : Σ^{⋆} → Σ_{1}^{⋆} and g : Γ^{⋆} → Γ_{1}^{⋆} be two morphisms such that for all u ∈ Σ (respectively, u ∈ Γ) h(u) ≠ λ (respectively, g(u) ≠ λ). So h and g may be naturally extended to some functions h̄ : Σ^{ω} → Σ_{1}^{ω} and ḡ : Γ^{ω} → Γ_{1}^{ω}. Let then R ⊆ Σ^{ω} × Γ^{ω} be an infinitary rational relation, then

R′ = {(h̄(w), ḡ(t)) ∈ Σ_{1}^{ω} × Γ_{1}^{ω} | (w, t) ∈ R}

is an infinitary rational relation.

3. Undecidability of topological and arithmetical properties

An infinitary rational relation R ⊆ Σ^{ω} × Γ^{ω} may be seen as an ω-language over the finite alphabet Σ × Γ.

For a finite alphabet X we shall consider the set X^{ω} equipped with the usual Cantor topology for which open sets are in the form W.X^{ω} with W ⊆ X^{⋆}.

Recall that closed sets are characterized by the following: Proposition 3.1. A set L ⊆ X^{ω} is a closed subset of X^{ω} iff for every σ ∈ X^{ω}, [∀n ≥ 1, ∃u ∈ X^{ω} such that σ(1) … σ(n).u ∈ L] implies that σ ∈ L. We refer to [Fin01a] or to [Sta97] [PP01] [Kec95] for the definition of Borel and analytic subsets of X^{ω}.

We shall say that an infinitary rational relation is effectively given if a Büchi transducer recognizing it or a rational expression defining it is given.

We shall firstly prove that one cannot decide whether an infinitary rational relation is a closed (respectively, open) set even if we consider only open (respectively, closed) infinitary rational relations. Proposition 3.2. Let X and Y be finite alphabets having at least two letters, then there exists a family F_{1} of infinitary rational relations which are closed subsets of X^{ω} × Y^{ω}, such that one cannot decide whether a given R ∈ F_{1} is an open subset of X^{ω} × Y^{ω}.

Proof. Return to the Post Correspondence Problem which has been shown to be undecidable.

Theorem 3.3 (Post). Let Γ be an alphabet having at least two elements. Then it is undecidable to determine, for arbitrary n-tuples (x_{1}, x_{2} …, x_{n}) and (y_{1}, y_{2} …, y_{n}) of non-empty words in Γ^{⋆}, whether there exists a non-empty sequence of indices i_{1}, i_{2} …, i_{k} such that x_{i_{1}}x_{i_{2}} … x_{i_{k}} = y_{i_{1}}y_{i_{2}} … y_{i_{k}}.

Let now Σ ⊇ {a, b} and Γ be finite alphabets having at least two letters. Let n be an integer ≥ 1 and x = (x_{1}, x_{2} …, x_{n}) and (y_{1}, y_{2} …, y_{n}) be n-tuples of non-empty words in Γ^{⋆} and call

R(x) = {(ba^{i_{1}}ba^{i_{2}} … ba^{i_{k}}, x_{i_{1}}x_{i_{2}} … x_{i_{k}}) | k is an integer ≥ 1 and i_{1}, i_{2}, …, i_{k} ∈ [1, n]}

R(y) = {(ba^{i_{1}}ba^{i_{2}} … ba^{i_{k}}, y_{i_{1}}y_{i_{2}} … y_{i_{k}}) | k is an integer ≥ 1 and i_{1}, i_{2}, …, i_{k} ∈ [1, n]} Then R(x) ⊆ Σ^{⋆} × Γ^{⋆} is a finitary rational relation and so is its complement (Σ^{⋆} × Γ^{⋆}) − R(x), [Ber79]. Similarly R(y) and its complement are finitary rational relations.

Let now c be a new letter not in Σ ∪ Γ and let

O(x) = R(x).(c, c).((Σ ∪ {c})^{ω} × (Γ ∪ {c})^{ω})

Then O(x) ⊆ (Σ ∪ {c})^{ω} × (Γ ∪ {c})^{ω} is an infinitary rational relation and it is an open subset of (Σ ∪ {c})^{ω} × (Γ ∪ {c})^{ω}. Its complement O(x)^{−} = (Σ ∪ {c})^{ω} × (Γ ∪ {c})^{ω} − O(x) is the union of the three sets C_{1}(x), C_{2}(x) and C_{3}(x) where

C_{1}(x) = ((Σ^{⋆} × Γ^{⋆}) − R(x)).(c, c).((Σ ∪ {c})^{ω} × (Γ ∪ {c})^{ω})
C_{2}(x) = Σ^{ω} × (Γ ∪ {c})^{ω}
C_{3}(x) = (Σ ∪ {c})^{ω} × Γ^{ω}

Thus O(x)^{−} is the union of three infinitary rational relations and it is in RAT_{ω} because the class RAT_{ω} is closed under finite union.

The infinitary rational relation O(y) is defined in a similar manner and its complement O(y)^{−} is in RAT_{ω}.

Consider now

O(x) ∩ O(y) = (R(x) ∩ R(y)).(c, c).((Σ ∪ {c})^{ω} × (Γ ∪ {c})^{ω})

then O(x) ∩ O(y) is non empty if and only if R(x) ∩ R(y) is non empty if and only if there exists a non-empty sequence of indices i_{1}, …, i_{k} such that x_{i_{1}} … x_{i_{k}} = y_{i_{1}} … y_{i_{k}}. Thus one cannot decide whether O(x) ∩ O(y) is empty, i.e. whether (O(x) ∩ O(y))^{−} is equal to (Σ ∪ {c})^{ω} × (Γ ∪ {c})^{ω}.

But (O(x) ∩ O(y))^{−} = O(x)^{−} ∪ O(y)^{−} is the union of two infinitary rational relations hence it is in RAT_{ω}. Moreover it is the union of two closed subsets of (Σ∪{c})^{ω} ×(Γ∪{c})^{ω} therefore it is also a closed subset of (Σ∪{c})^{ω} ×(Γ∪{c})^{ω}.

Then there are two cases.

(1) First case. R(x) ∩ R(y) is empty thus (O(x) ∩ O(y))^{−} is equal to (Σ ∪ {c})^{ω} × (Γ ∪ {c})^{ω} and it is an open (and closed) subset of (Σ ∪ {c})^{ω} × (Γ ∪ {c})^{ω}.

(2) Second case. R(x) ∩ R(y) is non empty thus there exists a non-empty sequence of indices i_{1}, …, i_{k} such that x_{i_{1}} … x_{i_{k}} = y_{i_{1}} … y_{i_{k}}. Then each sequence (i_{1}, …, i_{k})^{n}, where n is an integer ≥ 1, gives another solution of Post correspondence problem and ((ba^{i_{1}}ba^{i_{2}} … ba^{i_{k}})^{n}, (x_{i_{1}}x_{i_{2}} … x_{i_{k}})^{n}) is in R(x) ∩ R(y). We show now that O(x) ∩ O(y) is not closed. If O(x)∩O(y) = (R(x)∩R(y)).(c, c).((Σ∪{c})^{ω} ×(Γ∪{c})^{ω}) was a closed set it would contain the couple ((ba^{i_{1}}ba^{i_{2}} … ba^{i_{k}})^{ω}, (x_{i_{1}}x_{i_{2}} … x_{i_{k}})^{ω}) of infinite words because each of its prefixes is the prefix of some couple (u, v) ∈ O(x) ∩ O(y). But this is not possible because for all (w, t) ∈ O(x) ∩ O(y) the infinite words w and t contain at least one occurrence of the letter c. So in this case O(x)∩O(y) is not closed and the infinitary rational relation O(x)^{−} ∪ O(y)^{−} is not open.

We have seen that one cannot decide which of these two cases holds and this ends the proof for two alphabets X and Y having at least three letters: the family F_{1} is formed by the infinitary rational relations O(x)^{−} ∪ O(y)^{−}.

An easy coding allows to infer the result for two alphabets X and Y having at least two letters; details are left to the reader but such codings will be used in proof of proposition 3.6. □

Proposition 3.4. Let Σ and Γ be finite alphabets having at least two letters, then there exists a family F_{2} of infinitary rational relations which are open subsets of Σ^{ω} × Γ^{ω}, such that one cannot decide whether a given R ∈ F_{2} is a closed subset of Σ^{ω} × Γ^{ω}.

Proof. Return to the Post Correspondence Problem for infinite words which has been shown undecidable by F. Gire [Gir86].

Theorem 3.5. Let Γ be an alphabet having at least two elements. Then it is undecidable to determine, for arbitrary n-tuples (x_{1}, …, x_{n}) and (y_{1}, …, y_{n}) of nonempty words in Γ^{⋆}, whether there exists an infinite sequence of indices i_{1}, i_{2}, …, i_{k} … such that x_{i_{1}}x_{i_{2}} … x_{i_{k}} … = y_{i_{1}}y_{i_{2}} … y_{i_{k}} …

Let Σ ⊇ {a, b} and Γ be finite alphabets having at least two letters and x = (x_{1}, …, x_{n}) and y = (y_{1}, …, y_{n}) be n-tuples of non-empty words in Γ^{⋆}. The ωpowers R(x)^{ω} and R(y)^{ω}, where R(x) and R(y) are defined as above, are infinitary rational relations and subsets of Σ^{ω} × Γ^{ω}. Moreover their complements are also infinitary rational relations. This can be proved as an extension of the preceding result concerning the complement of R(x). We briefly sketch the proof, as exposed in [Pri00]. Let

U = (Σ^{ω} − {ba^{1}; ba^{2}; …; ba^{n}}^{ω}) × Γ^{ω}

then U is an infinitary rational relation because Σ^{ω} − {ba^{1}; ba^{2}; …; ba^{n}}^{ω} is an ω-regular language. And let W ⊆ Σ^{⋆} × Γ^{⋆} be the finitary rational relation defined by

W = {(w, t) ∈ Σ^{⋆} × Γ^{⋆} | ∃j ∈ [1, n] w = ba^{j}b and |t| = |x_{j}| and t ≠ x_{j}}

then

(R(x)^{ω})^{−} = U ∪ R(x)^{⋆}.W.(Σ^{ω} × Γ^{ω})

Thus (R(x)^{ω})^{−} ∈ RAT_{ω} because it is the union of two infinitary rational relations.

From the characterization of closed sets given in proposition 3.1 we can easily infer that R(x)^{ω} and R(y)^{ω} are closed subsets of Σ^{ω} × Γ^{ω}. Thus R(x)^{ω} ∩ R(y)^{ω} is also a closed set and its complement

(R(x)^{ω} ∩ R(y)^{ω})^{−} = (R(x)^{ω})^{−} ∪ (R(y)^{ω})^{−}

is an open subset of Σ^{ω} × Γ^{ω}.

Two cases may happen.

(1) First case. There exists an infinite sequence of indices i_{1}, i_{2}, …, i_{k} …

such that

x_{i_{1}}x_{i_{2}} … x_{i_{k}} … = y_{i_{1}}y_{i_{2}} … y_{i_{k}} …

Then R(x)^{ω} ∩ R(y)^{ω} is non empty. In that case R(x)^{ω} ∩ R(y)^{ω} is not open otherwise it would contain a set (u, v).(Σ^{ω} × Γ^{ω}) for some finite words u ∈ Σ^{⋆} and v ∈ Γ^{⋆}. So the couple (u.a^{ω}, v.e^{ω}), for e ∈ Γ, would be in R(x)^{ω} ∩ R(y)^{ω} and this is not possible because the first component u.a^{ω} would contain only a finite number of occurrences of the letter b. Then (R(x)^{ω} ∩ R(y)^{ω})^{−} = (R(x)^{ω})^{−} ∪ (R(y)^{ω})^{−} is not closed.

(2) Second case. There is no infinite sequence of indices i_{1}, i_{2}, …, i_{k} … such

that

x_{i_{1}}x_{i_{2}} … x_{i_{k}} … = y_{i_{1}}y_{i_{2}} … y_{i_{k}} …

Then R(x)^{ω}∩R(y)^{ω} is empty hence it is open and its complement (R(x)^{ω}∩ R(y)^{ω})^{−} = (R(x)^{ω})^{−} ∪ (R(y)^{ω})^{−} = Σ^{ω} × Γ^{ω} is a closed subset of Σ^{ω} × Γ^{ω}.

But one cannot decide which of these two cases holds so one cannot decide whether the open infinitary rational relation (R(x)^{ω})^{−} ∪ (R(y)^{ω})^{−} is a closed subset of Σ^{ω} × Γ^{ω}. The family F_{2} is then formed by the infinitary rational relations (R(x)^{ω})^{−} ∪ (R(y)^{ω})^{−}. □

In order to extend these undecidability results to all Borel classes we shall firstly prove the following result. Proposition 3.6. Let X and Y be finite alphabets having at least two letters, then there exists a family F of infinitary rational relations which are subsets of X^{ω} ×Y^{ω}, such that, for R ∈ F, either R = X^{ω} ×Y^{ω} or R is a Σ_{1}^{1}-complete subset of X^{ω} × Y^{ω}, but one cannot decide which case holds.

Proof. We shall rely on a previous result proved in [Fin01a]: there exists some Σ_{1}^{1}-complete infinitary rational relations.

We first describe such a rational relation R which is an ω-language over the alphabet ((Σ ∪ {A}) × (Σ ∪ {A})) where Σ is a finite alphabet having two letters and A is an additionnal letter not in Σ. Every word of R may be seen as a couple y = (y_{1}, y_{2}) of ω-words over the alphabet Σ ∪ {A} and then 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 a given Π_{2}^{0}-complete ω-regular language B ⊆ Σ^{ω}. For example Σ = {0, 1} and B = (0^{⋆}.1)^{ω} is a well known example of Π_{2}^{0}-complete ω-regular language.

Let us now assume that Σ is an alphabet having two letters and R is a Σ_{1}^{1}-complete infinitary rational relation defined as above.

Recall that if Σ is an alphabet having at least two letters then it is undecidable to determine, for a given rational relation (over finite words) S ⊆ Σ^{⋆} × Σ^{⋆}, whether S = Σ^{⋆} × Σ^{⋆}, see [Ber79]. This can be proved by considering the finitary rational relations (R(x) ∩ R(y))^{−} = R(x)^{−} ∪ R(y)^{−} where R(x) and R(y) are defined as above.

We define, from the Σ_{1}^{1}-complete infinitary rational relation R ⊆ ((Σ ∪ {A})^{ω} × (Σ ∪ {A})^{ω}) and a given rational relation S ⊆ Σ^{⋆} × Σ^{⋆}, the following relation:

R^{S} = S_{1} ∪ S_{2} ∪ S_{3}

where

S_{1} = S.(A, A).((Σ ∪ {A})^{ω} × (Σ ∪ {A})^{ω})
S_{2} = (Σ^{⋆} × Σ^{⋆}).(A, A).R
S_{3} = [(Σ ∪ {A})^{ω} × Σ^{ω}] ∪ [Σ^{ω} × (Σ ∪ {A})^{ω}]

R^{S} is the union of three infinitary rational relations thus R^{S} ∈ RAT_{ω} because the class RAT_{ω} is closed under finite union.

Now two cases may happen.

(1) First case. S = Σ^{⋆} × Σ^{⋆} therefore R^{S} = ((Σ ∪ {A})^{ω} × (Σ ∪ {A})^{ω}).

(2) Second case. S ≠ Σ^{⋆} × Σ^{⋆} therefore there is some (u, v) ∈ Σ^{⋆} × Σ^{⋆} such that (u, v) ∉ S. But then, for (w, t) ∈ (Σ ∪ {A})^{ω} × (Σ ∪ {A})^{ω}, (u, v).(A, A).(w, t) ∈ R^{S} if and only if (w, t) ∈ R. Consider now the function

φ_{(u,v)} : ((Σ ∪ {A})^{ω} × (Σ ∪ {A})^{ω}) → ((Σ ∪ {A})^{ω} × (Σ ∪ {A})^{ω})

defined by

φ_{(u,v)}((w, t)) = (u, v).(A, A).(w, t)

It is easy to see that φ_{(u,v)} is a continuous function and that, for all (w, t) ∈ ((Σ ∪ {A})^{ω} × (Σ ∪ {A})^{ω}),

φ_{(u,v)}((w, t)) ∈ R^{S} if and only if (w, t) ∈ R.

This means that R = φ_{(u,v)}^{−1}(R^{S}). But we know that R is Σ_{1}^{1}-complete and this implies that R^{S} is also Σ_{1}^{1}-complete. Remark that we already knew that R^{S} was a Σ_{1}^{1}-set because it is an infinitary rational relation.

But one cannot decide which case holds. So we have got the family F in the case of two alphabets X and Y having both three elements. In fact we had X = Y = Σ ∪ {A} but the result holds also if X ≠ Y as it is easy to see.

Assume we have got the result for X = Y = Σ ∪ {A} = {a, b, A} and consider the morphism h : {a, b, A}^{⋆} → {a, b}^{⋆} defined by h(a) = bab, h(b) = ba^{2}b and h(A) = ba^{3}b. This morphism can be naturally extended to a function h̄ : {a, b, A}^{ω} → {a, b}^{ω} and to a function ¯ h̄ : {a, b, A}^{ω} × {a, b, A}^{ω} → {a, b}^{ω} × {a, b}^{ω}. It is easy to see that the functions h̄ and ¯ h̄ are continuous and injective. Define now, from the infinitary relation R^{S}, the following

W^{S} = ¯ h̄(R^{S}) ∪ [{a, b}^{ω} × {a, b}^{ω} − ¯ h̄({a, b, A}^{ω} × {a, b, A}^{ω})]

Remark that the set

{a, b}^{ω} × {a, b}^{ω} − ¯ h̄({a, b, A}^{ω} × {a, b, A}^{ω})

is equal to

({a, b}^{ω} − h̄({a, b, A}^{ω})) × {a, b}^{ω} ⋃{a, b}^{ω} × ({a, b}^{ω} − h̄({a, b, A}^{ω}))

but it is easy to see that {a, b}^{ω} − h̄({a, b, A}^{ω}) is an ω-regular language (because it is the complement of the ω-regular language h̄({a, b, A}^{ω}) ) thus the set

{a, b}^{ω} × {a, b}^{ω} − ¯ h̄({a, b, A}^{ω} × {a, b, A}^{ω})

is an infinitary rational relation. On the other side ¯ h̄(R^{S}) is an infinitary rational relation by proposition 2.1 because R^{S} ∈ RAT_{ω}. Therefore W^{S} ∈ RAT_{ω} because the class RAT_{ω} is closed under finite union.

We can now state that again two cases may happen.

(1) First case. R^{S} = ((Σ∪{A})^{ω} ×(Σ∪{A})^{ω}) then W^{S} = {a, b}^{ω} ×{a, b}^{ω}.

(2) Second case. R^{S} is a Σ_{1}^{1}-complete subset of (Σ ∪ {A})^{ω} × (Σ ∪ {A})^{ω}. By construction of W^{S} it holds that

¯h̄^{−1}(W^{S}) = R^{S}

But we know that R^{S} is Σ_{1}^{1}-complete, that W^{S} is a Σ_{1}^{1}-set and that the function ¯ h̄ is continuous thus W^{S} is also Σ_{1}^{1}-complete.

Again one cannot decide which case holds and this proves the result for two alphabets X and Y having two elements.

In order to prove now the result for every alphabet, assume, without loss of generality, that we have got the family F in the case of two alphabets X = {c_{1}, c_{2}} and Y = {d_{1}, d_{2}} having two elements and consider two alphabets X′ = {c_{1}, c_{2}, …, c_{k}} having k elements and Y′ = {d_{1}, d_{2}, …, d_{p}} having p elements with k, p ≥ 2. Define now, for F ∈ F, the set

T^{F} = F ∪ [X^{′ω} × Y^{′ω} − X^{ω} × Y^{ω}]

It is easy to see that X^{′ω} × Y^{′ω} − X^{ω} × Y^{ω} is an infinitary rational relation thus T^{F} ∈ RAT_{ω} because the class RAT_{ω} is closed under finite union.

Again only two cases may happen for F ∈ F.

(1) First case. F = X^{ω} × Y^{ω} thus T^{F} = X^{′ω} × Y^{′ω}.

(2) Second case. F is a Σ_{1}^{1}-complete subset of X^{ω} × Y^{ω}. Consider the embedding g : X^{ω} × Y^{ω} → X^{′ω} × Y^{′ω} defined by g(u, v) = (u, v) for all (u, v) ∈ X^{ω} × Y^{ω}. The function g is continuous and

g^{−1}(T^{F}) = F

therefore T^{F} is Σ_{1}^{1}-complete because F is Σ_{1}^{1}-complete and T^{F} is a Σ_{1}^{1}-set (because T^{F} ∈ RAT_{ω}).

But one cannot decide which case holds and this proves the result for two alphabets X and Y having at least two elements. □

We can now state the following results. We refer to [Sta97] for the precise definition of the Arithmetical hierarchy of ω-languages. Theorem 3.7. Let Σ and Γ be finite alphabets having at least two letters, α be a countable ordinal ≥ 1, and j be an integer ≥ 1. Then for an effectively given infinitary rational relation R ⊆ Σ^{ω} × Γ^{ω} it is undecidable to determine whether:

(a) R is in the Borel class Σ_{α}^{0}.

(b) R is in the Borel class Π_{α}^{0}.

(c) R is a Borel subset of Σ^{ω} × Γ^{ω}.

(d) R is a Σ_{1}^{1}-complete subset of Σ^{ω} × Γ^{ω}.

(e) R is in the arithmetical class Σ_{j}.

(f) R is in the arithmetical class Π_{j}.

(g) R is an arithmetical set in ∪_{n≥1}Σ_{n} = ∪_{n≥1}Π_{n}.

Proof. Let Σ and Γ be finite alphabets having at least two letters and F be the family of infinitary rational relations included in Σ^{ω} × Γ^{ω} obtained in the proof of proposition 3.6. Then two cases may happen for F ∈ F: either F = Σ^{ω} × Γ^{ω} or F is a Σ_{1}^{1}-complete subset of Σ^{ω} × Γ^{ω}.

In the first case F is an open and closed subset of Σ^{ω} ×Γ^{ω} thus, for every countable ordinal α ≥ 1, it is in the class Σ_{α}^{0} and also in the class Π_{α}^{0}. Moreover it is in every arithmetical class Σ_{j} or Π_{j}. In the second case F is not a Borel set because a Σ_{1}^{1}-complete set is not Borel. So it is not in any arithmetical class because each arithmetical class Σ_{n} (respectively Π_{n}) is included in the Borel class Σ_{n}^{0} (respectively Π_{n}^{0}). But one cannot decide which case holds and this ends the proof of Theorem 3.7. □

4. Other undecidability results

Proposition 3.6 establishes a strong undecidability result which implies other ones.

Theorem 4.1. Let Σ and Γ be finite alphabets having at least two letters. Then it is undecidable to determine, for an effectively given infinitary rational relation R ⊆ Σ^{ω} × Γ^{ω}, whether:

(a) R is accepted by a deterministic Büchi (respectively, Muller) 2-tape finite automaton.

(b) R is accepted by a deterministic Büchi (respectively, Muller) Turing machine.

(c) its complement (Σ^{ω} × Γ^{ω}) − R is an infinitary rational relation.

(d) its complement (Σ^{ω} × Γ^{ω}) − R is accepted by a non deterministic Turing machine with a Büchi (respectively Muller) acceptance condition.

Proof. Let Σ and Γ be finite alphabets having at least two letters and F be the family of infinitary rational relations included in Σ^{ω} × Γ^{ω} obtained in the proof of proposition 3.6. Then two cases may happen for F ∈ F: either F = Σ^{ω} × Γ^{ω} or F is a Σ_{1}^{1}-complete subset of Σ^{ω} × Γ^{ω}. In the first case F is obviously accepted by a deterministic Büchi (respectively, Muller) 2-tape finite automaton hence also by a deterministic Büchi (respectively, Muller) Turing machine. Moreover its complement F^{−} = ∅ is in RAT_{ω} and is accepted by a non deterministic Turing machine with a Büchi (respectively Muller) acceptance condition. In the second case F is Σ_{1}^{1}-complete thus it cannot be accepted by any deterministic finite machine with a Büchi (respectively Muller) acceptance condition because otherwise it would be a boolean combination of Π_{2}-sets hence a Δ_{3}^{0}-set. In fact ω-languages accepted by deterministic Büchi Turing machines form the class Π_{2} and ω-languages accepted by deterministic Muller Turing machines form the class of boolean combinations of Π_{2}-sets, see [Sta97]. Moreover its complement F^{−} is a Π_{1}^{1}-complete subset of Σ^{ω} ×Γ^{ω}. It is well known that a Π_{1}^{1}-complete set is not a Σ_{1}^{1}-set thus it is not accepted by any Turing machine with a Büchi or Muller acceptance condition and it cannot be in RAT_{ω}. But one cannot decide which case holds. □

Notice that item (a) was already proved by Frougny and Sakarovitch in [FS93]. They deduced this result from a corresponding one on finitary rational relations. It is also proved in [FS93] that one cannot decide whether an infinitary rational relation R ⊆ Σ^{ω} × Γ^{ω} is synchronized, i.e. is an ω-regular language over the alphabet Σ×Γ. This latter result can also be deduced from Proposition 3.6. So we give here another proof of these results which follows from topological properties of infinitary rational relations. Moreover we have also proved item (b) showing that the “intrinsic determinism” of infinitary rational relations is undecidable.

Acknowledgements. Thanks to the referees for useful comments on a previous version of this paper.

References

[BCPS00] M.-P. Béal , O. Carton, C. Prieur and J. Sakarovitch, Squaring Transducers: An Efficient Procedure for Deciding Functionality and Sequentiality of Transducers, in the Proceedings of LATIN 2000, (G. Gonnet, D. Panario and A. Viola, eds.) Vol. 1776 of Lect. Notes in Comput. Sci., pp. 397-406, 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.

[Fin01a] O. Finkel, On the Topological Complexity of Infinitary Rational Relations, RAIRO-Theoretical Informatics and Applications, to appear.

[Fin01b] O. Finkel, On Infinitary Rational Relations and Borel Sets, in the Proceedings of the Fourth International Conference on Discrete Mathematics and Theoretical Computer Science DMTCS’03, 7 - 12 July 2003, Dijon, France, Lecture Notes in Computer Science, Springer, to appear.

[FS93] C. Frougny and J. Sakarovitch, Synchronized Relations of Finite and Infinite Words, Theoretical Computer Science, Volume 108, 1993, p.45-82.

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

[Gir86] F. Gire, Contribution à l’Etude des Langages et Relations Infinitaires, Thèse d’Etat, Université Paris 7, Janvier 1986.

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

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

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

[Pri01] C. Prieur, How to Decide Continuity of Rational Functions on Infinite Words, Theoretical Computer Science, Volume 250 (1-2), 2001, p. 71-82.

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

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

14 TITLE WILL BE SET BY THE PUBLISHER

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