BOREL HIERARCHY AND OMEGA CONTEXT FREE LANGUAGES

Olivier Finkel ∗

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

Abstract

We give in this paper additional answers to questions of Lescow and Thomas [Logical Specifications of Infinite Computations, In:”A Decade of Concurrency”, Springer LNCS 803 (1994), 583-621], proving topological properties of omega context free languages (ω-CFL) which extend those of [O. Finkel, Topological Properties of Omega Context Free Languages, Theoretical Computer Science, Vol. 262 (1-2), 2001, p. 669-697]: there exist some ω-CFL which are non Borel sets and one cannot decide whether an ω-CFL is a Borel set. We give also an answer to a question of Niwinski [Problem on ω-Powers Posed in the Proceedings of the 1990 Workshop ”Logics and Recognizable Sets”] and of Simonnet [Automates et Théorie Descriptive, Ph.D. Thesis, Université Paris 7, March 1992] about ω-powers of finitary languages, giving an example of a finitary context free language L such that L^{ω} is not a Borel set. Then we prove some recursive analogues to preceding properties: in particular one cannot decide whether an ω-CFL is an arithmetical set. Finally we extend some results to context free sets of infinite trees.

Key words: Context free ω-languages; topological complexity; Borel hierarchy; analytic sets. 1991 MSC: 03D05, 03E15, 68Q45

1 Introduction

Since Büchi studied the ω-languages recognized by finite automata to prove the decidability of the monadic second order theory of one successor over

∗ Corresponding author Email address: finkel@logique.jussieu.fr (Olivier Finkel).

Preprint submitted to Elsevier Science

the integers [Büc60a] the so called ω-regular languages have been intensively studied. See [Tho90] and [PP01] for many results and references.

As pushdown automata are a natural extension of finite automata, Cohen and Gold [CG77] , [CG78] and 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 Nivat [Niv77], [Niv78] and Boasson and Nivat [BN80]. These languages were then called the omega context free languages (ω-CFL). See also Staiger’s paper [Sta97a] for a survey of general theory of ω-languages.

Topological properties of ω-regular languages were first studied by Landweber in [Lan69] where he showed that these languages are boolean combinations of G_{δ} sets. He also characterized the ω-regular languages in each of the Borel classes F, G, F_{σ}, G_{δ}, and showed that one can decide, for an effectively given ω-regular language L, whether L is in the Borel class F, G, F_{σ}, or G_{δ}. It turned out that an ω-regular language is in the class G_{δ} iff it is accepted by a deterministic Büchi automaton. These results were extended to deterministic ω-CFL by Linna [Lin77]. In the non deterministic case, Cohen and Gold proved in [CG78] that one cannot decide whether an ω-CFL is in the class F, G or G_{δ}.

We have begun a similar study for ω-CFL in [Fin01a]. we proved that ω-CFL exhaust the finite ranks of the Borel hierarchy and that, for any Borel class Σ_{n}^{0} or Π_{n}^{0}, n being an integer, one cannot decide whether an ω-CFL is in Σ_{n}^{0} or Π_{n}^{0}. Our proof used the Wadge game and the operation of exponentiation of sets defined by Duparc [Dup01].

We pursue this study in this paper. We first show that there exist some ω-CFL which are analytic but non Borel sets. Then we extend the preceding undecidability result to every Borel class (of finite or infinite rank) and we prove that one cannot even decide whether an ω-CFL is a Borel set.

The question of the topological complexity of the ω-power of a finitary language is mentioned in [Sta97a] [Sta97b]. Niwinski asked in [Niw90] for an example of a (finitary) language L such that L^{ω} is not a Borel set. Simonnet asked in [Sim92] for the topological complexity of L^{ω} where L is a context free language. We proved in [Fin01a] that there exist context free languages L_{n} such that (L_{n})^{ω} is a Π_{n}^{0}-complete set for each integer n ≥ 1.

We give here an example of a context free language L such that L^{ω} is an analytic but not Borel set, answering to questions of Niwinski and Simonnet.

Then we derive some new arithmetical properties of omega context free languages from the preceding topological properties. We prove that one cannot decide whether an ω-CFL is an arithmetical set in ⋃_{i≥1} Σ_{n}. Then we show that one cannot decide whether the complement of an ω-CFL is accepted by a (non deterministic) Turing machine (or more generally by a non deterministic Xautomaton as defined in [EH93]) with Büchi (respectively Muller) acceptance condition. The above results give additional answers to questions of Thomas and Lescow [LT94].

Finally we extend some undecidability results to context free sets of infinite trees, as defined by Saoudi [Sao92].

The paper is organized as follows. In sections 2 and 3, we first review some above definitions and results about ω-regular, ω-context free languages, and topology. Then in section 4 we prove our main topological results from which we deduce in section 5 the result about ω-powers and in section 6 arithmetical properties of ω-CFL. Section 7 deals with context free languages of infinite trees.

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| . we write x(i) = x_{i} and x[i] = x(1) … x(i) for i ≤ k. If |x| = 0 , x is the empty word denoted by λ. Σ^{⋆} 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) … σ[n] = σ(1)σ(2) … σ(n) is 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^{−}.

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 languages accepted by MA by means of the ”ω-Kleene closure” of 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. The class of ω-regular languages will be denoted by REG_{ω}.

We now define pushdown machines and the class 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 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 [Sta97a].

Cohen and Gold and independently Linna established a characterization Theorem for ω-CFL:

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

(1) L ∈ ω − KC(CF L).

(2) There exists a BP DA that accepts L.

(3) There exists a MP DA that accepts L.

In [CG77] are also studied ω-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.9 An ω-language is an ω-context free language (ω-CFL) (or context free ω-language ) iff it satisfies one of the conditions of the above Theorem.

3 Topology

We assume the reader to be familiar with basic notions of topology which may be found in [LT94] [PP01] [Kur66] [Mos80] [Kec95].

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 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^{ω}. Π_{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: Σ_{α}^{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}.

Recall some basic results about these classes, [Mos80]:

Proposition 3.2

(a) Σ_{α}^{0} ∪ Π_{α}^{0} ⊊ Σ_{α+1}^{0} ∩ Π_{α+1}^{0}, for each countable ordinal α ≥ 1.

(b) ∪_{γ<α}Σ_{γ}^{0} = ∪_{γ<α}Π_{γ}^{0} ⊊ Σ_{α}^{0} ∩ Π_{α}^{0}, for each countable limit ordinal α.

(c) A set W ⊆ X^{ω} is in the class Σ_{α}^{0} iff its complement is in the class Π_{α}^{0}.

(d) Σ_{α}^{0} − Π_{α}^{0} ≠ ∅ and Π_{α}^{0} − Σ_{α}^{0} ≠ ∅ hold for every countable ordinal α ≥ 1.

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

Furthermore, when X is a finite set, there are some subsets of X^{ω} which are not Borel sets. Indeed there exists another hierarchy beyond the Borel hierarchy, which is called the projective hierarchy and which is obtained from the Borel hierarchy by successive applications of operations of projection and complementation. More precisely, a subset A of X^{ω} is in the class Σ_{1}^{1} of analytic sets 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 ≥ 0. Now a subset of X^{ω} is in the class Π_{1}^{1} of coanalytic sets iff its complement in X^{ω} is an analytic set. The next classes are defined in the same manner, Σ_{n+1}^{1}-sets of X^{ω} are projections of Π_{n}^{1}-sets and Π_{n+1}^{1}-sets are the complements of Σ_{n+1}^{1}-sets.

Recall also the notion of completeness with regard to reduction by continuous functions.

A set F ⊆ X^{ω} is a Σ_{α}^{0} (respectively Π_{α}^{0})-complete set iff for any set E ⊆ Y^{ω} (Y a finite alphabet): E ∈ Σ_{α}^{0} (respectively E ∈ Π_{α}^{0}) iff there exists a continuous function f from Y^{ω} into X^{ω} such that E = f^{−1}(F). A similar notion exists for classes of the projective hierarchy: in particular a set F ⊆ X^{ω} is a Σ_{1}^{1} (respectively Π_{1}^{1})-complete set iff for any set E ⊆ Y^{ω} (Y a finite alphabet): E ∈ Σ_{1}^{1} (respectively E ∈ Π_{1}^{1}) iff there exists a continuous function f from Y^{ω} into 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.

4 topological properties of ω-CFL

Recall first previous results. ω-CFL exhaust the finite ranks of the Borel hierarchy.

Theorem 4.1 ([Fin01a]) For each integer n ≥ 1, there exist some Σ_{n}^{0}- complete ω-CFL and some Π_{n}^{0}-complete ω-CFL.

Cohen and Gold proved that one cannot decide whether an ω-CFL is in the class F, G or G_{δ}. We have extended in [Fin01a] this result to all classes Σ_{n}^{0} and Π_{n}^{0}, for n an integer ≥ 1. (We say that an ω-CFL A is effectively given when a MPDA accepting A is given).

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

When considering ω-CFL, natural questions now arise: are all ω-CFL Borel sets of finite rank, Borel sets, analytic sets....? First recall the following:

Theorem 4.3 ([Sta97a]) Every ω-CFL over a finite alphabet X is an analytic subset of X^{ω}.

Proof. we just sketch the proof. Every ω-CFL A ⊆ Σ^{ω} is the projection of a deterministic ω-CFL onto Σ^{ω} but deterministic ω-CFL are Borel sets of rank at most 3, and it is well known that such a projection of a Borel set is an analytic subset of Σ^{ω}. Remark that in fact each ω-CFL is the projection of an ω-CFL which is accepted by a deterministic Büchi pushdown automaton and therefore which is a Π_{2}^{0}-set. □

Remark 4.4 This above theorem is in fact true for ω-languages accepted by Turing machines which are much more powerful accepting devices than pushdown automata [Sta97a].

The following question now arises: are there ω-CFL which are analytic but not Borel sets?

Theorem 4.5 There exist ω-CFL which are Σ_{1}^{1}-complete hence non Borel sets.

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_{Σ}^{ω}.

The Borel hierarchy and the projective hierarchy on 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 Σ. Then 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 set of higher complexity in the Borel hierarchy) then the set P ath(L) is a Σ_{1}^{1}-complete subset of T_{Σ}^{ω}. Hence P ath(L) is not a Borel set, [Niw85] [Sim92] [Sim93].

Whenever B is an ω-CFL we shall find another ω-CFL C and a continuous function

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

such that P ath(B) = h^{−1}(C). For that we will code trees labelled in Σ by words over Σ ∪ {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 letter not in Σ. We construct an ω-word over the alphabet (Σ ∪ {A}) which will code the tree t. We enumerate all the labels of the nodes of a tree in the following manner: firstly the label of the node of C_{0} which is t(u_{1}^{0}), followed by an A, followed by the labels of nodes of C_{1} in the lexicographic order, i.e. t(u_{1}^{1})t(u_{2}^{1}), followed by an A, followed by the labels of the nodes of C_{2} in the reverse lexicographic order, followed by an A, followed by the labels of nodes of C_{3} in the lexicographic order, and so on … For each integer n ≥ 0, the labels of the nodes of C_{n} are enumerated before those of C_{n+1} 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) and the labels of the nodes of C_{2n}, for n ≥ 0, are enumerated in the reverse lexicographic order (for the nodes).

Then for each tree t in T_{Σ}^{ω}, we obtain an ω-word of Σ ∪ {A} which will be denoted h(t). With the preceding notations it holds that:

h(t) = t(u_{1}^{0})At(u_{1}^{1})t(u_{2}^{1})At(v_{1}^{2})t(v_{2}^{2})t(v_{3}^{2})t(v_{4}^{2})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 … Let then h be the mapping from T_{Σ}^{ω} into (Σ∪{A})^{ω} such that for every labelled binary infinite tree t of T_{Σ}^{ω}, h(t) is the code 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, that h is a continuous function from T_{Σ}^{ω} into (Σ ∪ {A})^{ω}.

Assume now that B is an ω-CFL accepted by a Büchi pushdown automaton M = (K, Σ, Γ, δ, q_{0}, Z_{0}, F) where M′ = (K, Σ, Γ, δ, q_{0}, Z_{0}) is a pushdown machine and F ⊆ K is the set of final states.

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

We shall give a first description of such an ω-CFL C by constructing from M another Büchi pushdown automaton M̄ which accepts C. The reader can also skip this description and read a second description of the ω-CFL C which will be given below.

Describe first informally the behaviour of the new machine M̄. When M̄ reads a word in the form h(t), then using the non determinism it guesses a maximal branch of the tree t and simulates on this branch the Büchi pushdown automaton M. Finally the acceptation of h(t) by M̄ is related to the acceptation of the ω-word formed by the labels of this branch by M.

More formally M̄ = (K̄, Σ̄, Γ̄, δ̄, q̄_{0}, Z̄_{0}, F̄), where

K̄ = K∪{q^{1} | q ∈ K}∪{q^{2} | q ∈ K}∪{q^{3} | q ∈ K}∪{q^{4} | q ∈ K}∪{q^{5} | q ∈ K}∪{q_{r}}

Σ̄ = Σ ∪ {A}
Γ̄ = Γ ∪ {E}

where E is a new letter not in Γ,

q̄_{0} = q_{0}
Z̄_{0} = Z_{0}
F̄ = F ∪ {q^{5} | q ∈ F }

and the transition relation δ̄ is defined by the following cases which will be explained below:

(a) (q, ν) ∈ δ̄(q_{0}, a, Z_{0}) iff (q, ν) ∈ δ(q_{0}, a, Z_{0}), for each a ∈ Σ and ν ∈ Γ^{⋆}.

(b) δ̄(q_{0}, A, Z_{0}) = (q_{r}, Z_{0}).

(c) δ̄(q, a, Z) = (q^{1}, EZ), for each a ∈ Σ, Z ∈ Γ ∪ {E} and q ∈ K.

(d) δ̄(q^{1}, a, E) = (q^{1}, EE), for each a ∈ Σ, and q ∈ K.

(e) δ̄(q^{1}, A, Z) = (q^{2}, Z), for each Z ∈ Γ ∪ {E} and q ∈ K.

(f) δ̄(q, A, Z) = (q^{2}, Z), for each Z ∈ Γ ∪ {E} and q ∈ K.

(g) δ̄(q^{2}, a, E) = (q^{3}, E), for each a ∈ Σ, and q ∈ K.

(h) δ̄(q^{3}, a, E) = (q^{2}, λ), for each a ∈ Σ, and q ∈ K.

(i) δ̄(q^{2}, A, E) = (q_{r}, E), for each q ∈ K.

(j) δ̄(q^{3}, A, E) = (q_{r}, E), for each q ∈ K.

(k) δ̄(q_{r}, a, Z) = (q_{r}, Z), for each a ∈ (Σ ∪ {A}) and Z ∈ Γ ∪ {E}.

(l) δ̄(q^{2}, a, Z) ∋ (q′, ν) iff δ(q, a, Z) ∋ (q′, ν), for each a ∈ Σ, q, q′ ∈ K, Z ∈ Γ, and ν ∈ Γ^{⋆}.

(m) δ̄(q^{2}, λ, Z) ∋ (q^{′5}, ν) iff δ(q, λ, Z) ∋ (q′, ν), for each q, q′ ∈ K, Z ∈ Γ, and ν ∈ Γ^{⋆}.

(n) δ̄(q^{5}, λ, Z) ∋ (q^{′5}, ν) iff δ(q, λ, Z) ∋ (q′, ν), for each q, q′ ∈ K, Z ∈ Γ, and ν ∈ Γ^{⋆}.

(o) δ̄(q^{5}, a, Z) ∋ (q′, ν) iff δ(q, a, Z) ∋ (q′, ν), for each a ∈ Σ, q, q′ ∈ K, Z ∈ Γ, and ν ∈ Γ^{⋆}.

(p) δ̄(q^{5}, a, Z) ∋ (q^{4}, Z), for each a ∈ Σ, Z ∈ Γ and q ∈ K.

(q) δ̄(q^{2}, a, Z) ∋ (q^{4}, Z), for each a ∈ Σ, Z ∈ Γ and q ∈ K.

(r) δ̄(q^{4}, a, Z) ∋ (q′, ν) iff δ(q, a, Z) ∋ (q′, ν), for each a ∈ Σ, q, q′ ∈ K, Z ∈ Γ, and ν ∈ Γ^{⋆}.

(s) δ̄(q^{4}, A, Z) = (q_{r}, Z), for each q ∈ K, Z ∈ Γ.

We describe now more precisely the behaviour of M̄. To the set K of states of M, we add sets of states K^{i} = {q^{i} | q ∈ K} for each integer i ∈ [1, 5], and a state q_{r} which will be a rejecting state.

We firstly consider only the reading by M̄ of words in the form h(t) where t ∈ T_{Σ}^{ω}. When M̄ simulates M on the branch it guesses, it enters in a state of K, as indicated by (a), (l), (o), (r), or of K^{5} if it uses a λ-transition, i.e. if it does not read any letter during this transition, as indicated by (m) − (n).

When M̄ reads the labels of the nodes of t, it reads successively the labels of nodes of C_{0}, C_{1}, C_{2}, …, C_{i}, …

Let B be the branch which is guessed by M̄ during a reading.

After the use of one transition rule of (a), (l), (o) or (r), reading the label of a node u of B in C_{n}, n ≥ 0, M̄ enters in a state q^{1}, keeping the memory of q, and then continues the reading of the (labels of) nodes of C_{n}, pushing an E on the top of the stack for every letter of Σ it reads (transition rules (c), (d)) until it reads an A. Then it enters in state q^{2}, keeping again the memory of q, (transition rules (e), (f)) and reading the labels of nodes of C_{n+1}, it begins to pop an E from the top of the stack for two letters of Σ it reads, as indicated by transition rules (g), (h) (here are used the two sets of states K^{2} and K^{3}). Thus when the letter at the top of the stack is again a letter of Γ (and not an E) the machine M̄ reads the label of one successor of the node u (this is due to the fact that the tree is binary and to the order of the enumeration of the nodes we have chosen in the definition of h(t)). It may choose to simulate M on this label, as indicated by the transition rules (l), (m), (n), (o), (perhaps after some λ-transitions). Otherwise it may choose to wait the next label, entering in state q^{4}, as indicated by the transition rules (p), (q), and then simulates M as indicated by the transition rule (r).

Some other transition rules, (b), (i), (j), (k), (s), lead to the rejecting state q_{r} in which M̄ remains for the rest of the reading. But in fact these transition rules are never used for the reading of ω-words in the form h(t) where t ∈ T_{Σ}^{ω}.

Now we can see that when M̄ simulates M on the branch B, if M enters in a state q ∈ K, then M̄ enters in the state q or in the state q^{5} (when a λ-transition is used). Thus the choice of the set of accepting states F̄ = F ∪ {q^{5} | q ∈ F } implies the property: for a tree t ∈ T_{Σ}^{ω}, h(t) ∈ C if and only if t has a path in B.

We are going now to give a second description of the ω-CFL C.

The ω-language C which we have constructed from the ω-language B can easily be described by means of substitution of context free languages. Let first D be the following finitary language over the alphabet (Σ ∪ {A}):

D = {u.A.v | u, v ∈ Σ^{⋆} and (|v| = 2|u|) or (|v| = 2|u| + 1) }

It is easy to see that D is a context free language.

Now an ω-word σ ∈ C may be considered as an ω-word σ′ ∈ B to which we add, between two consecutive letters σ′(n) and σ′(n + 1) of σ′, a finite word v_{n} belonging to the context free finitary language D.

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)

The substitution f is called λ-free if ∀i ∈ [1; n] L_{i} does not contain the empty word. In that case the mapping f may be extended to ω-words:

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

Let ℂ be a family of languages, if ∀i ∈ [1; n] the language L_{i} belongs to ℂ the substitution f is called a ℂ-substitution.

Let then g be the substitution Σ → P ((Σ∪{A})^{⋆}) defined by: a → a.D where D is the context free language defined above. Then g is a λ-free substitution and g(B) = C holds. But the languages a.D are context free and CF L_{ω} is closed under λ-free context free substitution [CG77]. Then B ∈ CF L_{ω} implies that C ∈ CF L_{ω}.

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}(C) = P ath(B) is a Σ_{1}^{1}-complete subset of T_{Σ}^{ω}. Then the ω-language C is at least Σ_{1}^{1}-complete because h is a continuous function (note that here h is a continuous function: T_{Σ}^{ω} → (Σ_{A})^{ω} and the preceding definition of Σ_{1}^{1}-complete set involves continuous reductions: X^{ω} → Y^{ω}; but the two topological spaces T_{Σ}^{ω} and (Σ_{A})^{ω} have good similar properties which enable to extend the previous definition to this new case [Mos80][Kec95]). And C is in fact a Σ_{1}^{1}-complete subset of (Σ ∪ {A})^{ω} because every ω-CFL is an analytic set by Theorem 4.3. Then in that case C is not a Borel set because a Σ_{1}^{1}-complete set is not a Borel set [Kur66][Mos80]. Indeed this gives infinitely many non Borel ω-CFL , because there exist infinitely many ω-CFL of borel rank > 2. □

Remark that in the above proof, whenever B is an ω-regular language accepted by a Büchi automaton M, the resulting machine M̄ is just a one counter machine, i.e. a pushdown machine having a stack alphabet Γ̄ = {Z_{0}, E}, where Z_{0} is the bottom symbol which always remains at the bottom of the pushdown store and appears only there. Then at any moment of any computation the word in the pushdown store is in the form E^{n}Z_{0} where n is an integer ≥ 0. Thus it holds that:

Corollary 4.6 There exist one counter ω-languages which are Σ_{1}^{1}-complete hence non Borel sets.

Now we can deduce from the preceding proof the following undecidability result:

Theorem 4.7 Let Σ be an alphabet containing at least two letters. It is undecidable, for an effectively given ω-CFL B to determine whether B is a Borel subset of Σ^{ω}.

Proof. Remark first that h(T_{Σ}^{ω}) is the set of ω-words in (Σ_{A})^{ω} which belong to

Σ.A.Σ^{2}.A.Σ^{4}.A.Σ^{8}.A … A.Σ^{2^{n}}.AΣ^{2^{n+1}} …

In other words this is the set of words in (Σ_{A})^{ω} which contain infinitely many occurrences of the letter A, and have 2^{n} letters of Σ between the nth and the (n+1)th occurrences of the letter A. We shall first state the following:

Lemma 4.8 Let Σ be a finite alphabet. Then (Σ_{A})^{ω} − h(T_{Σ}^{ω}) is an omega context free language.

Proof. Let

A_{1} = (A ∪ Σ^{2} ∪ Σ.A.A ∪ Σ.A.Σ.A ∪ Σ.A.Σ^{3}).(Σ_{A})^{ω}

A_{1} is the set of words in (Σ_{A})^{ω} which have not any word of Σ.A.Σ^{2}.A as prefix. A_{1} is clearly an ω-regular language hence it is also an ω-CFL.

Let now B_{1} be the set of finite words over the alphabet Σ_{A} which are in the form A.u.A.v.A where u, v ∈ Σ and |v| < 2|u|. And let B_{2} be the set of finite words over the alphabet Σ_{A} which are in the form A.u.A.v where u, v ∈ Σ and |v| > 2|u|.

Then it is easy to see that B_{1} and B_{2} are context free finitary languages, thus the ω-language

A_{2} = [(Σ_{A})^{⋆}.B_{1}.(Σ_{A})^{ω}] ∪ [(Σ_{A})^{⋆}.B_{2}.(Σ_{A})^{ω}]

is an an omega context free language by Theorem 2.8. But (Σ_{A})^{ω} − h(T_{Σ}^{ω}) = A_{1} ∪ A_{2} and the class of context free ω-languages is closed under union [CG77] therefore (Σ_{A})^{ω} − h(T_{Σ}^{ω}) is an omega context free language. □

We recall now a result established in [Fin01a] in the course of the proof of the above Theorem 4.2. We had seen that:

Lemma 4.9 There exists a family of (effectively given) context free ω-languages (A_{X,Y}^{∼})^{d} over the alphabet {a, b, c, ↞, d} such that (A_{X,Y}^{∼})^{d} is either {a, b, c, ↞ , d}^{ω} or an ω-language which is a Borel set but neither a Π_{2}^{0}-subset nor a Σ_{2}^{0}-subset of {a, b, c, ↞, d}^{ω}. But one cannot decide which case holds.

Consider now these languages. Denote B(X, Y) = (A_{X,Y}^{∼})^{d} and Σ = {a, b, c, ↞ , d}. Then there are two cases. In the first case B(X, Y) = Σ^{ω}. In the second case B(X, Y) is neither a Π_{2}^{0}-subset nor a Σ_{2}^{0}-subset of Σ^{ω}.

Return now to the previous proof. In the first case P ath(B(X, Y)) = P ath(Σ^{ω}) = T_{Σ}^{ω}. In the second case P ath(B(X, Y)) is a Σ_{1}^{1}-complete subset of T_{Σ}^{ω}.

Construct now from B(X, Y) another omega context free language C(X, Y) over the alphabet Σ_{A} in the same manner as we have constructed C from B in the above proof.

Let then D(X, Y) = C(X, Y)∪[(Σ_{A})^{ω} −h(T_{Σ}^{ω})]. D(X, Y) is an ω-CFL because it is the union of two ω-CFL and the class of omega context free languages is closed under union.

Then two cases may happen. In the first case, P ath(B(X, Y)) = T_{Σ}^{ω} hence h(T_{Σ}^{ω}) ⊆ C(X, Y) and D(X, Y) = (Σ_{A})^{ω}. Therefore D(X, Y) is a closed and open subset of (Σ_{A})^{ω}.

In the second case h^{−1}(D(X, Y)) = h^{−1}(C(X, Y)) = P ath(B(X, Y)) holds by construction and then D(X, Y) is a Σ_{1}^{1}-complete subset of (Σ_{A})^{ω}, for the same reason as C(X, Y) is Σ_{1}^{1}-complete .

But one cannot decide which case holds hence one cannot decide whether the context free ω-language is a Borel set.

To see that the result is also true for an alphabet containing two letters, consider the morphism g : {a, b, c, ↞, d, A}^{⋆} → {a, b}^{⋆} defined by: a → bab, b → ba^{2}b, c → ba^{3}b, (↞) → ba^{4}b, d → ba^{5}b, A → ba^{6}b. This morphism is λ-free and may be extended to infinite words in an obvious manner, giving a continuous function ḡ : {a, b, c, ↞, d, A}^{ω} → {a, b}^{ω}.

Let then F (X, Y) = ḡ(D(X, Y)). F (X, Y) is an ω-CFL because D(X, Y) is an ω-CFL and the class of context free ω-languages is closed under λ-free morphism [CG77]. There are again two cases. In the first case, D(X, Y) = (Σ_{A})^{ω}, hence D(X, Y) is a compact set and, the image of a compact set by a continuous function being a compact set, F (X, Y) = ḡ(D(X, Y)) is a compact subset of {a, b}^{ω}, therefore it is a closed subset of {a, b}^{ω}.

In the second case, D(X, Y) = ḡ^{−1}(F (X, Y)) and D(X, Y) is a Σ_{1}^{1}-complete subset of T_{Σ}^{ω}, thus F (X, Y) is also at least a Σ_{1}^{1}-complete subset of {a, b}^{ω}, and in fact it is a Σ_{1}^{1}-complete subset because it is an analytic set as an ω-CFL. □

Remark that we have also extended Theorem 4.2 to all Borel classes:

Theorem 4.10 Let α be a countable ordinal ≥ 1. Then it is undecidable to determine whether an effectively given ω-CFL is in the class Σ_{α}^{0} ( respectively Π_{α}^{0}).

Proof. The result has been proved for every finite ordinal (integer) ≥ 1 in [Fin01a]. Let then α be a countable infinite ordinal. The above defined ω-CFL F (X, Y) is either a Π_{1}^{0}-subset or a Σ_{1}^{1}-complete subset of {a, b}^{ω}. In the first case it is in the class Σ_{α}^{0} ( respectively Π_{α}^{0}) and in the second case it is not a Borel set. But one cannot decide which case holds. □

5 ω-powers of finitary languages

We study in this section ω-powers of finitary languages, i.e. ω-languages in the form V^{ω} where V is a finitary language. ω-powers of finitary languages are always analytic sets because whenever V is finite, V^{ω} is an ω-regular language and then it is a boolean combination of Σ_{2}^{0}-sets and whenever V is countably infinite, one can fix an enumeration of V and obtain V^{ω} as a continuous image of ω^{ω} (the set of infinite sequences of integers ≥ 0), [Sim92].

Niwinski asked in [Niw90] for an example of finitary language W such that W^{ω} is an analytic but non Borel set. From the results of preceding section, we can easily find an example of a context free language W such that W^{ω} is not a Borel set.

Consider the construction of the ω-language C from the ω-language B ⊆ Σ^{ω} in the proof of Theorem 4.5. As stated above, if g is the substitution Σ → P ((Σ ∪ {A})^{⋆}) defined by a → a.D where

D = {u.A.v | u, v ∈ Σ^{⋆} and (|v| = 2|u|) or (|v| = 2|u| + 1) }

then D is a context free language over the alphabet (Σ ∪ {A}) and g(B) = C holds.

Assume now that B is an ω-power in the form V^{ω}. Then g(B) = (g(V))^{ω} is also an ω-power.

Let then Σ = {0, 1} be an alphabet containing two letters 0 and 1 and W = 0^{⋆}.1. Then W^{ω} = (0^{⋆}.1)^{ω} is the set of ω-words over the alphabet Σ which contain infinitely many occcurrences of the letter 1. It is a well known example of an ω-regular language which is a Π_{2}^{0}-complete subset of Σ^{ω}.

Thus the language g(W) is a finitary context free language such that (g(W))^{ω} is an analytic but non Borel set. This language g(W) is in fact a one counter language.

This gives an answer to Niwinski’s question and additional answer to questions of Simonnet who asked in [Sim92] for the topological complexity of the ωpowers of context free languages.

6 Arithmetical properties

We are going to deduce from the previous proofs some new results about ω-context free languages and the Arithmetical hierarchy. We recall first the definition of the Arithmetical hierarchy of ω-languages, [Sta97a].

Let X be a finite alphabet. An ω-language L ⊆ X^{ω} belongs to the class Σ_{n} if and only if there exists a recursive relation R_{L} ⊆ (ℕ)^{n−1} × X^{⋆} such that

L = {σ ∈ X^{ω} | ∃a_{1} … Q_{n}a_{n} (a_{1}, …, a_{n−1}, σ[a_{n} + 1]) ∈ R_{L}}

where Q_{i} is one of the quantifiers ∀ or ∃ (not necessarily in an alternating order). An ω-language L ⊆ X^{ω} belongs to the class Π_{n} if and only if its complement X^{ω} − L belongs to the class Σ_{n}. The inclusion relations that hold between the classes Σ_{n} and Π_{n} are the same as for the corresponding classes of the Borel hierarchy.

Proposition 6.1 ([Sta97a]) a) Σ_{n} ∪ Π_{n} ⊊ Σ_{n+1} ∩ Π_{n+1}, for each integer

n ≥ 1.

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

c) Σ_{n} − Π_{n} ≠ ∅ and Π_{n} − Σ_{n} ≠ ∅ hold for each integer n ≥ 1.

The classes Σ_{n} and Π_{n} are strictly included in the respective classes Σ_{n}^{0} and Σ_{n}^{0} of the Borel hierarchy:

Theorem 6.2 ([Sta97a]) For each integer n ≥ 1, Σ_{n} ⊊ Σ_{n}^{0} and Π_{n} ⊊ Π_{n}^{0}.

Recall now preceding results of [Fin01a]:

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

As in the case of the Borel hierarchy, projections of arithmetical sets (of the second Π-class) lead beyond the Arithmetical hierarchy, to the Analytical hierarchy of ω-languages. The first class of this hierarchy is the class Σ_{1}^{1}. An ω-language L ⊆ X^{ω} belongs to the class Σ_{1}^{1} if and only if there exists a recursive relation R_{L} ⊆ (ℕ) × {0, 1}^{⋆} × X^{⋆} such that:

L = {σ ∈ X^{ω} | ∃τ(τ ∈ {0, 1}^{ω} ∧ ∀n∃m((n, τ[m], σ[m]) ∈ R_{L}))}

Then an ω-language L ⊆ X^{ω} is in the class Σ_{1}^{1} iff it is the projection of an ω-language over the alphabet X × {0, 1} which is in the class Π_{2} of the arithmetical hierarchy.

It turned out that an ω-language L ⊆ X^{ω} is in the class Σ_{1}^{1} iff it is accepted by a non deterministic Turing machine (reading ω-words) with a Muller acceptance condition [Sta97a]. This class is denoted NT (inf, =) (where (inf, =) indicates the Muller condition) in [Sta97a] and also called the class of recursive ω-languages REK_{ω}. ^{1}

With the above definitions, one can state the following:

Theorem 6.4 ([Sta97a]) The class CF L_{ω} is strictly included into the class REK_{ω} of recursive ω-languages.

A natural question arises: are there ω-CFL which are in the class Σ_{1}^{1} but in not any class of the arithmetical hierarchy? The answer can be easily derived from the preceding corresponding results about the Borel Hierarchy.

Theorem 6.5 There exist some context free ω-languages in Σ_{1}^{1} − ⋃_{n≥1} Σ_{n}.

Proof. It follows from Theorems 4.5 and 6.2. □

We now obtain a recursive analogue to Theorem 4.7:

Theorem 6.6 Let Σ be an alphabet containing at least two letters. It is undecidable, for an effectively given context free ω-language B to determine whether B is in Σ_{1}^{1} − ⋃_{n≥1} Σ_{n}.

Proof. Recall that we had found (see proof of Theorem 4.7) a family of context free ω-languages D(X, Y) over the alphabet Γ = {a, b, c, ↞, d, A} such that D(X, Y) is either a Σ_{1}^{1}-complete subset of Γ^{ω}, or equal to Γ^{ω}.

Whenever D(X, Y) is Σ_{1}^{1}-complete, it is not in ⋃_{n≥1} Σ_{n} because each arithmetical class Σ_{n} (respectively Π_{n}) is included in the Borel class Σ_{n}^{0} (respectively Π_{n}^{0}).

Whenever D(X, Y) is equal to Γ^{ω}, D(X, Y) is in the class Σ_{1} because of the characterization of ω-languages in Σ_{1} [Sta97a]: an ω-language L ⊆ X^{ω} belongs to the class Σ_{1} if and only if there exists a recursive finitary language W ⊆ X^{⋆} such that L = W.X^{ω}.

But we had proved that one cannot decide which of these two cases holds, hence the result is proved for the alphabet Γ. (And we can use similar methods as in the proof of Theorem 4.7 to obtain the result for an alphabet of cardinal ≥ 2). □

Considering Turing machines, we get the following:

1 In another presentation, as in [Rog67], the recursive ω-languages are those which are in the intersection Σ_{1} ∩ Π_{1}, see also [LT94].

Theorem 6.7 It is undecidable to determine whether the complement of an effectively given ω-CFL is accepted by a non deterministic Turing machine with Büchi (respectively Muller) acceptance condition.

Proof. As in the preceding proof consider the family of context free ωlanguages D(X, Y) over the alphabet Γ = {a, b, c, ↞, d, A} such that D(X, Y) is either a Σ_{1}^{1}-complete subset of Γ^{ω}, or equal to Γ^{ω}.

Whenever D(X, Y) is Σ_{1}^{1}-complete, its complement is Π_{1}^{1}-complete thus it is not a Σ_{1}^{1} set (because a set which is both Σ_{1}^{1} and Π_{1}^{1} is a Borel set) and therefore it is not a Σ_{1}^{1}-set (because the class Σ_{1}^{1} is included in the class Σ_{1}^{1}) then it is not accepted by any Turing machine with Büchi (respectively Muller) acceptance condition.

In the other case D(X, Y) is equal to Γ^{ω}, then its complement is the emptyset and it is accepted by a Turing machine with Büchi (respectively Muller) acceptance condition.

But we had proved that one cannot decide which of these two cases holds, hence the result is proved for the alphabet Γ. (And we can use similar methods as in the proof of Theorem 4.7 to obtain the result for an alphabet of cardinal ≥ 2). □

In fact this result can be extended to other deterministic machines. Consider X-automata as defined in [EH93] which are automata equipped with a storage type X.

Theorem 6.8 Let X be a storage type as defined in [EH93]. Then it is undecidable to determine whether the complement of an effectively given ω-CFL is accepted by a non deterministic X-automaton with Büchi (respectively Muller) acceptance condition.

Proof. It is similar to the previous one because every X-automaton is less expressive than a Turing machine hence it cannot accept any Π_{1}^{1}-complete set. And conversely Γ^{ω} is accepted by every X-automaton. □

7 Context free languages of infinite trees

The theory of automata reading infinite words have been extended to automata reading infinite binary trees labelled in a finite alphabet, i.e. trees in a space T_{Σ}^{ω} where Σ is a finite alphabet (and one may also consider infinite k-ary trees labelled in Σ but we shall restrict ourselves here to binary trees), see [Tho90][Tho96][LT94][Sim92] for many results and references.

It is known that regular languages of infinite binary trees exhaust the hierarchy of Borel sets of finite rank as shown by Skurczynski [Sku93]. Niwinski proved that there exist some regular set of trees which are non Borel sets, [Niw85].

Some regular sets of trees are Σ_{1}^{1}-complete, as P ath(B) where B is any Π_{2}^{0}- complete regular subset of Σ^{ω}. P ath(B) (defined in the proof of Theorem 4.5) is accepted by a non deterministic tree automaton which guesses a branch of a tree (using the non determinism) and then simulates a finite automaton on the path associated with this branch. One can also define, for each ω-language B ⊆ Σ^{ω}, the following sets of trees. Let

∀ − P ath(B)

be the set of trees t in T_{Σ}^{ω} such that every path of t is in B, and let

Left − P ath(B)

be the set of trees t in T_{Σ}^{ω} such that the leftmost path of t is in B (the nodes of the leftmost branch are the words of {l, r}^{⋆} which are in the form l^{n} for an integer n ≥ 0).

It is then well-known that whenever B ⊆ Σ^{ω} is an ω-regular language , the sets ∀ − P ath(B) and Left − P ath(B) are regular sets of trees. Then if B is a Π_{2}^{0}-complete subset of Σ^{ω} it holds that:

∀ − P ath(B^{−}) = T_{Σ}^{ω} − (P ath(B))

hence ∀ − P ath(B^{−}) is a Π_{1}^{1}-complete subset of T_{Σ}^{ω}.

The Theorem of complementation of Rabin implies that every regular set of trees is in Σ_{2}^{1} ∩Π_{2}^{1}, and it has been shown that there exist regular sets of trees which are not in Σ_{1}^{1} ∪ Π_{1}^{1}, see [LT94] for a view of a hierarchy of regular sets of trees.

As finite automata have been extended to (top-down) automata on infinite trees, pushdown automata have been extended to (top-down) pushdown automata on infinite trees by Saoudi [Sao92]. Denote, as in [Sao92], CF_{3} the family of languages of infinite (binary) trees accepted by (top-down) pushdown automata with Muller acceptance condition.

It is easy to see from the definition of these automata that, as in the case of tree automata, if B is an ω-CFL, then the sets of trees P ath(B) and Left − P ath(B) are accepted by tree pushdown automata. Then we can extend our preceding undecidability results of Theorems 4.7 and 4.10.

Theorem 7.1 (a) Let α be a countable ordinal ≥ 1. Then it is undecidable to determine whether an effectively given language in CF_{3} is in the Borel class Σ_{α}^{0} ( respectively Π_{α}^{0}).

(b) It is undecidable to determine whether an effectively given language in CF_{3} is a Borel set.

(c) It is undecidable to determine whether an effectively given language in CF_{3} is in the class Π_{1}^{1} .

(d) It is undecidable to determine whether an effectively given language in CF_{3} is a Σ_{1}^{1} but non Borel set.

Proof. The proofs are easily derived from the proof of Theorem 4.7. Recall we had got a family of omega context free languages D(X, Y) over the alphabet Σ_{A} such that: either D(X, Y) = (Σ_{A})^{ω}, or D(X, Y) is a Σ_{1}^{1}-complete subset of (Σ_{A})^{ω}. But one cannot decide which case holds. It is easy to see that Left − P ath(D(X, Y)) has the same topological complexity as the ω-language D(X, Y). Indeed let f be the function: (Σ_{A})^{ω} → T_{Σ_{A}}^{ω} defined by f(σ) = t_{σ} where t_{σ} is the tree in T_{Σ_{A}}^{ω} with σ as leftmost path and the letter A labelling the other nodes. Then f is continuous and f^{−1}(Left − P ath(D(X, Y))) = D(X, Y). Assume first that D(X, Y) is a Σ_{1}^{1}-complete subset of (Σ_{A})^{ω}, then Left − P ath(D(X, Y)) is also at least Σ_{1}^{1}-complete and not a Borel set. Now let j be the function T_{Σ_{A}}^{ω} → (Σ_{A})^{ω} defined by: j(t) is the leftmost path of the tree t. Then j is a continuous function and j^{−1}(D(X, Y)) = Left−P ath(D(X, Y)). Hence when D(X, Y) is a Σ_{1}^{1}-complete subset of (Σ_{A})^{ω}, Left−P ath(D(X, Y)) is a Σ_{1}^{1}-set because the class Σ_{1}^{1} is closed under inverse of continuous functions. Thus Left − P ath(D(X, Y)) is a Σ_{1}^{1}-complete subset of T_{Σ_{A}}^{ω} and not a Π_{1}^{1}-set. In the other case D(X, Y) = (Σ_{A})^{ω} and Left − P ath(D(X, Y)) = T_{Σ_{A}}^{ω} then Left − P ath(D(X, Y)) is in every Borel class and also in the class Π_{1}^{1}. But one cannot decide which case holds. This proves (a), (b), (c) and (d). □

8 Concluding remarks and further work

We have proved in [Fin01a] that the class of ω-CFL exhausts the finite ranks of the Borel hierarchy and in this paper (Theorem 4.5) that there exist some analytic but non Borel ω-CFL. The question to know whether there exist some ω-CFL which are Borel sets of infinite rank is still open.

There exists a refinement of the Borel hierarchy which is called the Wadge hierarchy of Borel sets. We proved in [Fin01b] that the length of the Wadge hierarchy of ω-CFL is an ordinal greater than or equal to the Cantor ordinal ε_{0}. And it remains to find the exact length of the Wadge hierarchy of Borel ω-CFL.

Mention that on the other side, the Wadge hierarchy of deterministic ω-CFL has been determined. its length is the ordinal ω^{(ω^{2})}. It has been recently studied in [DFR01] [Dup99] [Fin99].

Acknowledgments. We have previously proved the existence of analytic but non Borel sets in another class of ω-languages, the class of locally finite ωlanguages [Fin01c]. We are indebted to Jean-Pierre Ressayre who suggested the way to adapt the original proof to the context free case.

References

[Bar92] R. Barua, The Hausdorff-Kuratowski Hierarchy of ω-Regular Languages and a Hierarchy of Muller Automata, Theoretical Computer Science 96 (1992), 345-360.

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

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

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

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

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

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

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

[Dup99] J. Duparc, A Hierarchy of Context Free Omega Languages, Theoretical Computer Science, to appear.

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

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

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

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

[Fin01c] O. Finkel, Topological Complexity of Locally Finite Omega Languages, submitted to Annals of Pure and Applied Logic.

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

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

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

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

[Niw90] D. Niwinski, Problem on ω-Powers Posed in the Proceedings of the 1990 Workshop ”Logics and Recognizable Sets” (Univ. Kiel).

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

[Rog67] H. Rogers, Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York, 1967.

[Sao92] A. Saoudi, Pushdown Automata On Infinite Trees and Nondeterministic Context-Free Programs, International Journal of Foundations of Computer Science Vol.3, Number 1, (1992) 21-39.

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

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

[Sku93] Jerzy Skurczynski, the Borel Hierarchy is Infinite in the Class of Regular Sets of Trees, Theoretical Computer Science 112, (1993) 413-418.

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

[Sta97b] L. Staiger, On ω-Power Languages, in New Trends in Formal Languages, Control, Coperation, and Combinatorics, Lecture Notes in Computer Science 1218, Springer-Verlag, Berlin 1997, 377-393.

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

[Tho95] W. Thomas, On the Synthesis of Strategies in Infinite Games, in STACS’95, Volume 900 of LNCS, p.1-13, 1995.

[Tho96] W. Thomas, Languages, Automata and Logic, in Handbook of Formal Languages Theory, Vol 3, Edited by G. Rozenberg and A. Salomaa, Springer Verlag, 1996.

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

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