ON OMEGA CONTEXT FREE LANGUAGES WHICH ARE BOREL SETS

OF INFINITE RANK

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

This paper is a continuation of the study of topological properties of omega context free languages (ω-CFL). We proved in [Topological Properties of Omega Context Free Languages, Theoretical Computer Science, Volume 262 (1-2), 2001, p. 669-697] that the class of ω-CFL exhausts the finite ranks of the Borel hierarchy, and in [Borel Hierarchy and Omega Context Free Languages, Theoretical Computer Science, to appear] that there exist some ω-CFL which are analytic but non Borel sets. We prove here that there exist some omega context free languages which are Borel sets of infinite (but not finite) rank, giving additional answer to questions of Lescow and Thomas [Logical specifications of infinite computations, In:”A Decade of Concurrency” (J. W. de Bakker et al., eds), Springer LNCS 803 (1994), 583-621].

Key words: omega context free languages; topological properties; Borel hierarchy.

Contents

1 Introduction 1

2 ω-regular and ω-context free languages 3

3 Topology 6

4 Operation ” exponentiation of sets ” 9

5  ω-CFL which are Borel of infinite rank  12

6 Concluding remarks and further work 20

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

Preprint submitted to Elsevier Science

References 21

1 Introduction

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

Pushdown automata are a natural extension of finite automata. R. S. Cohen and A. Y. Gold [CG77] , [CG78] and M. Linna [Lin76] studied the ω-languages accepted by omega pushdown automata, considering various acceptance conditions for omega words. It turned out that the omega languages accepted by omega pushdown automata were also those generated by context free grammars where infinite derivations are considered, also studied by M. Nivat [Niv77]

[Niv78] and L. Boasson and M. Nivat [BN80]. These languages were then called the omega context free languages (ω-CFL). See also Staiger’s paper [Sta97a] for a survey of general theory of ω-languages, including more powerful accepting devices, like Turing machines, and the fundamental study of J. Engelfriet and H. J. Hoogeboom on X-automata, i.e. finite automata equipped with a storage type X, reading infinite words [EH93].

Topology is a useful tool for classifying ω-languages by the study of their complexity, particularly with regard to the Borel hierarchy.

McNaughton’s Theorem implies that ω-regular languages ( ω-languages accepted by deterministic Muller automata) are boolean combination of Π_{2}^{0}-sets, [MaN66]. Topological properties of ω-regular languages were first studied by L. H. Landweber in [Lan69] where he characterized ω-regular languages in a given Borel class.

J. Engelfriet and H. J. Hoogeboom proved that all ω-languages accepted by deterministic X-automata with a Muller acceptance condition are also boolean combinations of Π_{2}^{0}-sets hence (Σ_{3}^{0} ∩ Π_{3}^{0})-sets.

When considering non deterministic finite machines, as X-automata, a natural question, posed by H. Lescow and W. Thomas in [LT94], now arises: what is the topological complexity of ω-languages accepted by automata equipped with a given storage type X? Are they all Borel sets of finite rank, Borel sets, analytic sets?

It is well known that every ω-language accepted by a Turing machine (hence also by a X-automaton) with a Muller acceptance condition is an analytic set [Sta97a] (i.e. is obtained as a continuous image of a Borel set or as the projection of a Borel set [Mos80]).

We consider in this paper the storage type ”pushdown”. We pursue the investigation of topological properties of omega context free languages. We proved that the class of ω-CFL exhausts the finite ranks of the Borel hierarchy, giving examples of Π_{n}^{0}-complete (respectively Σ_{n}^{0}-complete) ω-CFL for each integer n ≥ 1, [Fin01a]. We showed in [Fin00a] that there exist some omega context free languages which are analytic but non Borel sets. There exist such ωlanguages in the form L^{ω}, with L a context free finitary language; this gave an answer to questions of D. Niwinski and P. Simonnet about omega powers of finitary languages [Niw90] [Sim92].

But the question was still open whether there exist some omega context free languages which are Borel sets of infinite rank.

We answer to this question in this paper giving examples of ω-CFL which are Borel sets of infinite rank.

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. In section 4 we introduce the operation of exponentiation of sets defined by J. Duparc in his recent study of the Wadge hierarchy of Borel sets, which is a great refinement of the Borel hierarchy [Dup01], and recall preceding results of [Fin01a]. In section 5, we prove our main result about ω-CFL, using an iteration of Duparc’s operation and give additional answer to questions of W. Thomas and H. Lescow [LT94].

2 ω-regular and ω-context free languages

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

An ω-word over Σ is an ω -sequence a_{1} … a_{n} …, where a_{i} ∈ Σ, ∀i ≥ 1. When σ is an ω-word over Σ, we write σ = σ(1)σ(2) … σ(n) … and σ[n] = σ(1)σ(2) … σ(n) the finite word of length n, prefix of σ. The set of ω-words over the alphabet Σ is denoted by Σ^{ω}. An ω-language over an alphabet Σ is a subset of Σ^{ω}.

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

For V ⊆ Σ^{⋆}, V^{ω} = {σ = u_{1} … u_{n} … ∈ Σ^{ω}/u_{i} ∈ V, ∀i ≥ 1} is the ω-power of V. For V ⊆ Σ^{⋆}, the complement of V (in Σ^{⋆}) is Σ^{⋆} − V denoted V^{−}. For a subset A ⊆ Σ^{ω}, the complement of A is Σ^{ω} − A denoted A^{−}.

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

Definition 2.1 : A finite state machine (FSM) is a quadruple M = (K, Σ, δ, q_{0}), where K is a finite set of states, Σ is a finite input alphabet, q_{0} ∈ K is the initial state and δ is a mapping from K × Σ into 2^{K} . A FSM is called deterministic (DFSM) iff : δ : K × Σ → K. A Büchi automaton (BA) is a 5-tuple M = (K, Σ, δ, q_{0}, F) where M′ = (K, Σ, δ, q_{0}) is a finite state machine and F ⊆ K is the set of final states. A Muller automaton (MA) is a 5-tuple M = (K, Σ, δ, q_{0}, F) where M′ = (K, Σ, δ, q_{0}) is a FSM and F ⊆ 2^{K} is the collection of designated state sets. A Büchi or Muller automaton is said deterministic if the associated FSM is deterministic. Let σ = a_{1}a_{2} … a_{n} … be an ω-word over Σ. A sequence of states r = q_{1}q_{2} … q_{n} … is called an (infinite) run of M = (K, Σ, δ, q_{0}) on σ, starting in state p, iff: 1) q_{1} = p and 2) for each i ≥ 1, q_{i+1} ∈ δ(q_{i}, a_{i}). In case a run r of M on σ starts in state q_{0}, we call it simply ”a run of M on σ ” . For every (infinite) run r = q_{1}q_{2} … q_{n} … of M, In(r) is the set of states in K entered by M infinitely many times during run r: In(r) = {q ∈ K/{i ≥ 1/q_{i} = q} is infinite }. For M = (K, Σ, δ, q_{0}, F) a BA , the ω-language accepted by M is L(M) = {σ ∈ Σ^{ω} / there exists a run r of M on σ such that In(r) ∩ F ≠ ∅}.

For M = (K, Σ, δ, q_{0}, F) a MA, the ω-language accepted by M is L(M) = {σ ∈ Σ^{ω} / there exists a run r of M on σ such that In(r) ∈ F}.

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

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

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

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

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

(2) There exists a DMA that accepts L.

(3) There exists a MA that accepts L.

(4) There exists a BA that accepts L.

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

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

Definition 2.4 A pushdown machine (PDM) is a 6-tuple M = (K, Σ, Γ, δ, q_{0}, Z_{0}), where K is a finite set of states, Σ is a finite input alphabet, Γ is a finite pushdown alphabet, q_{0} ∈ K is the initial state, Z_{0} ∈ Γ is the start symbol, and δ is a mapping from K × (Σ ∪ {λ}) × Γ to finite subsets of K × Γ^{⋆} . If γ ∈ Γ^{+} describes the pushdown store content, the leftmost symbol will be assumed to be on ” top” of the store. A configuration of a PDM is a pair (q, γ) where q ∈ K and γ ∈ Γ^{⋆}. For a ∈ Σ ∪ {λ}, γ, β ∈ Γ^{⋆} and Z ∈ Γ, if (p, β) is in δ(q, a, Z), then we write a : (q, Zγ) ↦_{M} (p, βγ). ↦_{M}^{⋆} is the transitive and reflexive closure of ↦_{M}. (The subscript M will be omitted whenever the meaning remains clear). Let σ = a_{1}a_{2} … a_{n} … be an ω-word over Σ. An infinite sequence of configurations r = (q_{i}, γ_{i})_{i≥1} is called a 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 either a_{1}a_{2} … a_{n} … = b_{1}b_{2} … b_{n} … or b_{1}b_{2} … b_{n} … is a finite prefix of a_{1}a_{2} … a_{n} …

The run r is said to be complete when 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].

R.S. Cohen and A.Y. Gold, and independently M. 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 the ω-languages generated by ω-context free grammars and it is shown that each of the conditions 1), 2), and 3) of the above Theorem is also equivalent to: 4) L is generated by a context free grammar G by leftmost derivations. These grammars are also studied in [Niv77] , [Niv78]. Then we can let the following definition:

Definition 2.9 An ω-language is an ω-context free language (ω-CFL) 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 [Mos80] [LT94] [Sta97a] [PP02] and with the elementary theory of (countable) ordinals.

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}. Closed sets are characterized by the following:

Proposition 3.1 A set L ⊆ X^{ω} is a closed set of X^{ω} iff for every σ ∈ X^{ω},

[∀n ≥ 1, ∃u ∈ X^{ω} such that σ(1) … σ(n).u ∈ L] implies that σ ∈ L.

Define now the next classes of the Borel Hierarchy:

Definition 3.2 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.3

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

(e) For every ordinal α ≥ 1, the class Σ_{α}^{0} is closed under countable unions and the class Π_{α}^{0} is closed under countable intersections.

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

There is a nice characterization of Π_{2}^{0}-subsets of X^{ω}. First define the notion of W^{δ}:

Definition 3.4 For W ⊆ X^{⋆}, let: W^{δ} = {σ ∈ X^{ω}/∃^{ω}i such that σ[i] ∈ W }. (σ ∈ W^{δ} iff σ has infinitely many prefixes in W).

Then we can state the following Proposition:

Proposition 3.5 (see [Sta97a]) A subset L of X^{ω} is a Π_{2}^{0}-subset of X^{ω} iff there exists a set W ⊆ X^{⋆} such that L = W^{δ}.

For X a finite set, (and this is also true if X is an infinite alphabet) 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. We denote (x, y) 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. Let α be a countable ordinal. A set F ⊆ X^{ω} is a Σ_{α}^{0} (respectively Π_{α}^{0})-complete set iff for any set E ⊆ Y^{ω} (with Y a finite alphabet): E ∈ Σ_{α}^{0} (respectively E ∈ Π_{α}^{0}) iff there exists a continuous function f : Y^{ω} → X^{ω} such that E = f^{−1}(F). A similar notion exists for the 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 such that E = f^{−1}(F).

A Σ_{α}^{0} (respectively Π_{α}^{0})-complete set is a Σ_{α}^{0} (respectively Π_{α}^{0})- set which is in some sense a set of the highest topological complexity among the Σ_{α}^{0} (respectively Π_{α}^{0})- sets. Σ_{n}^{0} (respectively Π_{n}^{0})-complete sets, with n an integer ≥ 1, are thoroughly characterized in [Sta86].

Landweber studied first the topological properties of ω-regular languages. He proved that every ω-regular language is a boolean combination of G_{δ}- sets. and 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 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.

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

First recall the following previous result, [Sta97a]:

Theorem 3.6 Every ω-CFL over a finite alphabet X is an analytic subset of X^{ω}.

We showed the following

Theorem 3.7 ([Fin00a])

(a) There exist some ω-CFL which are Σ_{1}^{1}-complete sets hence non Borel sets.

(b) It is undecidable whether an effectively given ω-CFL is a Borel set.

Next the ω-CFL exhaust the finite ranks of the Borel hierarchy.

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

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, and next to all Borel classes in [Fin00a]. (We say that an ω-CFL A is effectively given when a MPDA accepting A is given).

But the question was still open whether there exist some omega context free languages which are Borel sets of infinite (but not finite) rank. We shall show below that there exist such omega context free languages.

4 Operation ” exponentiation of sets ”

In order to construct omega context free languages of every finite rank, we used recent results of J. Duparc about the Wadge hierarchy. The Wadge hierarchy of Borel sets is a huge refinement of the Borel hierarchy. Wadge gave first a description of this hierarchy [Wad84] and Duparc recently got a new proof of Wadge’s results and he gave a normal form of Borel sets, i.e. an inductive construction of a Borel set of every given degree [Dup95a] [Dup01]. In fact we shall need in this paper only some of his results. So we shall recall only these results and refer to [Dup95a] [Dup01] for more details.

Duparc’s proof relies on set theoretic operations which are the counterpart of arithmetical operations over ordinals needed to compute the Wadge degrees. In fact we shall only use in this paper the operation of exponentiation over sets of infinite words. Moreover we shall consider a slight modification of Duparc’s operation A → A^{∼} we introduced in [Fin01a] and which we recall now:

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

Remark 4.2 For x ∈ X^{≤ω}, x^{↞} denotes the string x, once every ^{↞} occuring in x has been ”evaluated” to the back space operation ( the one familiar to your computer!), proceeding from left to right inside x. In other words x^{↞} = x from which every interval of the form ”a ↞ ” (a ∈ X_{A}) is removed. We add the convention that (u. ↞)^{↞} is undefined if |u^{↞}| = 0, i.e. when the last letter ↞ can not be used as an eraser (because every letter of X_{A} in u has already been erased by some erasers ↞ placed in u). Remark that the resulting word x^{↞} may be finite or infinite.

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

We can now define the variant A → A^{≈} of the operation of exponentiation of sets:

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

The following result is then another formulation of a property of the operation A → A^{∼} proved in [Dup01] and which was applied in [Fin01a] to study the ω-powers of finitary context free languages.

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

We proved that the class CF L_{ω} is closed under this operation A → A^{≈}.

Theorem 4.5 ([Fin01a]) Whenever A ⊆ X_{A}^{ω} is an ω-CFL, then A^{≈} ⊆ (X_{A} ∪ {↞})^{ω} is an ω-CFL.

Proof. An ω-word σ ∈ A^{≈} may be considered as an ω-word σ^{↞} ∈ A to which we possibly add, before the first letter σ^{↞}(1) of σ^{↞} (respectively between two consecutive letters σ^{↞}(n) and σ^{↞}(n + 1) of σ^{↞}), a finite word v_{1} (respectively v_{n+1} ) where: for all integers i ≥ 1, v_{i} belongs to the context free (finitary) language L_{3} generated by the context free grammar with the following production rules: S → aS ↞ S with a ∈ X_{A}, S → λ (λ being the empty word). this language L_{3} corresponds to words where every letter of X_{A} has been removed after using the back space operation.

Remark 4.6 Recall that a one counter automaton is a pushdown automaton with a pushdown alphabet in the form Γ = {Z_{0}, z} where Z_{0} is the bottom symbol and always remains at the bottom of the pushdown store. And a one counter language is a (finitary) language which is accepted by a one counter automaton by final states. It is easy to see that in fact L_{3} is a deterministic one-counter language, i.e. L_{3} is accepted by a deterministic one-counter automaton. And for a ∈ X_{A}, the language L_{3}.a is also accepted by a deterministic one-counter automaton.

Then we can see that whenever A ⊆ X_{A}^{ω}, the ω-language A^{≈} ⊆ (X_{A} ∪ {↞})^{ω} is obtained by substituting in A the language L_{3}.a for each letter a ∈ X_{A}, where L_{3} is the CFL defined above.

Let now A be an ω-CFL given by A = ⋃_{i=1}^{n} U_{i}.V_{i}^{ω} where U_{i} and V_{i} are context free languages. Then A^{≈} = ⋃_{i=1}^{n}(U′_{i}).V_{i}^{′ω}, where U′_{i} (respectively V′_{i}) is obtained by substituting the language L_{3}.a to each letter a ∈ X_{A} in U_{i} (respectively V_{i}). The class CFL is closed under substitution, so U′_{i} and V′_{i} are CFL. Hence the ω-language A^{≈} is an ω-CFL because ω − KC(CF L) ⊆ CF L_{ω}.

We have also given in [Fin01a] an effective construction of a MPDA accepting the ω-language A^{≈} ⊆ (X_{A} ∪ {↞})^{ω} from a MPDA accepting an ωlanguage A ⊆ X_{A}^{ω}. Recall now the idea of this construction.

Let A be an ω-CFL which is accepted by a Muller pushdown automaton A = (K, X_{A}, Γ, δ, q_{0}, Z_{0}, F). The ω-language accepted by A is L(A) = A = {σ ∈ X_{A}^{ω} / there exists a run r of A on σ such that In(r) ∈ F}.

We can construct another MPDA A^{≈} which accepts the ω-language A^{≈} over the alphabet X = X_{A} ∪ {↞}. Let us describe informally the behaviour of the machine A^{≈} when it reads an ωword σ ∈ A^{≈}. Recall that this word may be considered as an ω-word σ^{↞} ∈ A to which we possibly add, before the first letter σ^{↞}(1) of σ^{↞} (respectively between two consecutive letters σ^{↞}(n) and σ^{↞}(n + 1) of σ^{↞}), a finite word v_{1} (respectively v_{n+1} ) where v_{i} belongs to the context free language L_{3}.

A^{≈} starts the reading as a pushdown automaton accepting the language L_{3}. Then A^{≈} begins to read as A, but at any moment of the computation it may guess (using the non determinism) that it reads a finite segment v of L_{3} which will be erased (using the eraser ↞). It reads v using an additional stack letter E which permits to simulate a one counter automaton at the top of the stack while keeping the memory of the stack of A. Then, after the reading of v, A^{≈} simulates again the machine A and so on.

5 ω-CFL which are Borel of infinite rank

A well known example of Π_{2}^{0}-complete ω-regular language is B_{2} = {α ∈ {0, 1}^{ω}/∃^{ω}i α(i) = 1} = (0^{⋆}.1)^{ω}, where ∃^{ω}i means: ” there exist infinitely many i such that …”. B_{2} is an omega context free language because it is an ω-regular language.

We can now get some Π_{n+2}^{0}-complete set, for an integer n ≥ 1, from the Π_{2}^{0}- complete set B_{2} by applying n ≥ 1 times the operation of exponentiation of sets.

More precisely, we define, for a set A ⊆ X_{A}^{ω}: A^{≈.0} = A A^{≈.1} = A^{≈} and A^{≈.(k+1)} = (A^{≈.k})^{≈}, where we apply k + 1 times the operation A → A^{≈} with different new letters ↞_{1}, ↞_{2}, ↞_{3}, …, ↞_{k+1}.

We can now infer from Theorems 4.4 and 4.5 that, for an integer n ≥ 1, (B_{2})^{≈.n} is an omega context free language which is a Π_{n+2}^{0}-complete subset of {0, 1, ↞_{1}, …, ↞_{n}}^{ω}. Similarly, if A ⊆ X_{A}^{ω} is a Π_{2}^{0}-complete regular or context free ω-language over the alphabet X_{A}, the ω-language (A)^{≈.n} is a Π_{n+2}^{0}- complete subset of (X_{A} ∪ {↞_{1}, …, ↞_{n}})^{ω}.

A way to obtain a Borel set of infinite rank, as we shall show below, is to define, for two letters a, b in X_{A}, the supremum of the sets A^{≈.i}:

sup_{i∈ℕ}A^{≈.i} = ⋃_{i∈ℕ}a^{i}.b.A^{≈.i}

But this set is defined over an infinite alphabet, and any omega context free ω-language is defined over a finite alphabet. So we have first to code this set over a finite alphabet. We shall first code every set A^{≈.n}. The ω-language A^{≈.n} is defined over the alphabet X_{A} ∪ {↞_{1}, …, ↞_{n}} hence we have to code every eraser ↞_{j} by a finite word over a fixed finite alphabet. We shall code the eraser ↞_{j} by the finite word α.B^{j}.C^{j}.D^{j}.E^{j}.β over the alphabet {α, B, C, D, E, β}. The reason of the coding we choose will be clear later, when we construct a Muller pushdown automaton accepting an ω-language close to the coding of sup_{i∈ℕ} A^{≈.i}. In fact this MPDA needs to read four times the integer j characterizing the eraser ↞_{j}.

Remark first that one can define the morphism

F_{n} : (X_{A} ∪ {↞_{1}, …, ↞_{n}})^{⋆} → (X_{A} ∪ {α, β, B, C, D, E})^{⋆}

by F (c) = c for each c ∈ X_{A} and F (↞_{j}) = α.B^{j}.C^{j}.D^{j}.E^{j}.β for each integer j ∈ [1, n], where B, C, D, E, α, β are new letters not in X_{A}. This morphism is naturally extended to a continuous function

F̄_{n} : (X_{A} ∪ {↞_{1}, …, ↞_{n}})^{ω} → (X_{A} ∪ {α, β, B, C, D, E})^{ω}

Then F̄_{n}((X_{A}∪{↞_{1}, …, ↞_{n}})^{ω}) is the continuous image by F̄_{n} of the compact set (X_{A} ∪ {↞_{1}, …, ↞_{n}})^{ω}, hence it is also a compact set, and a closed subset of (X_{A} ∪{α, β, B, C, D, E})^{ω}. We can now state the following lemma. Its proof is easy and left to the reader.

Lemma 5.1 Let A ⊆ X_{A}^{ω} be a Π_{2}^{0}-complete subset of X_{A}^{ω}. Then for each integer n ≥ 1, the ω-language F̄_{n}(A^{≈.n}) is a Π_{n+2}^{0}-complete subset of (X_{A} ∪ {α, β, B, C, D, E})^{ω}.

We shall prove now that the supremum of the sets F̄_{n}(A^{≈.n}) is a Borel set of infinite rank.

Lemma 5.2 Let A ⊆ X_{A}^{ω} be a Π_{2}^{0}-complete subset of X_{A}^{ω}. Then the set

sup_{n≥1} F̄_{n}(A^{≈.n}) = ⋃_{n≥1} a^{n}.b.F̄_{n}(A^{≈.n})

is a Σ_{ω}^{0}-subset of (X_{A} ∪ {α, β, B, C, D, E})^{ω} which is not a Borel set of finite rank.

Proof. Assume A ⊆ X_{A}^{ω} is Π_{2}^{0}-complete. Then the preceding lemma implies that, for each n ≥ 1, the ω-language F̄_{n}(A^{≈.n}) is a Π_{n+2}^{0}-complete subset of (X_{A} ∪{α, β, B, C, D, E})^{ω}. Let a, b be two letters in X_{A} then it is easy to show that, for each n ≥ 1, the set a^{n}.b.F̄_{n}(A^{≈.n}) is also a Π_{n+2}^{0}-complete subset of (X_{A} ∪ {α, β, B, C, D, E})^{ω} thus

sup_{n≥1} F̄_{n}(A^{≈.n}) = ⋃_{n≥1} a^{n}.b.F̄_{n}(A^{≈.n})

is in the class Σ_{ω}^{0} by definition of this class.

On the other side this set cannot be a Borel set of finite rank. Because if sup_{n≥1} F̄_{n}(A^{≈.n}) was in the class Π_{j}^{0}, for an integer j ≥ 1, then the set

a^{n}.b.F̄_{n}(A^{≈.n}) = sup_{n≥1} F̄_{n}(A^{≈.n}) ∩ (a^{n}.b.(X_{A} ∪ {α, β, B, C, D, E})^{ω})

would be also in the class Π_{j}^{0}, because (a^{n}.b.(X_{A} ∪ {α, β, B, C, D, E})^{ω}) is a closed hence Π_{j}^{0}-set and the class of Π_{j}^{0}-subsets of (X_{A}∪{α, β, B, C, D, E})^{ω} is closed under finite intersection. But this would lead to a contradiction because we have seen that, for n ≥ j, the set a^{n}.b.F̄_{n}(A^{≈.n}) is Π_{n+2}^{0}-complete, where n + 2 ≥ j + 2 > j hence it is not a Π_{j}^{0}-subset of (X_{A} ∪ {α, β, B, C, D, E})^{ω}. □

We can not show that the ω-language sup_{n≥1} F̄_{n}(A^{≈.n}) is an omega context free language. This is connected to the fact that the finitary language

{B^{j}C^{j}D^{j}E^{j} / j ≥ 1}

is not a context free language. But its complement is easily seen to be context free. Then, instead of considering sup_{n≥1} F̄_{n}(A^{≈.n}), we can add to this ω-language all ω-words in the form a^{n}.b.u where there is in u a segment α.B^{j}.C^{k}.D^{l}.E^{m}.β, with j, k, l, m integers ≥ 1, which does not code any eraser, or codes an eraser ↞_{j} for j > n. Then we add to sup_{n≥1} F̄_{n}(A^{≈.n}) another ωlanguage which is of Borel rank 2 and the resulting ω-language will be still of infinite rank, but we shall show that it is an omega context free language.

So we define now formally this construction in the following way.

Define first the following context free finitary languages over the alphabet X^{□} = (X_{A} ∪ {α, β, B, C, D, E}) :

L^{B} = {a^{n}.b.u.B^{j} / n ≥ 1 and j > n and u ∈ (X^{□})^{⋆}}
L^{C} = {a^{n}.b.u.C^{j} / n ≥ 1 and j > n and u ∈ (X^{□})^{⋆}}
L^{D} = {a^{n}.b.u.D^{j} / n ≥ 1 and j > n and u ∈ (X^{□})^{⋆}}
L^{E} = {a^{n}.b.u.E^{j} / n ≥ 1 and j > n and u ∈ (X^{□})^{⋆}}

L^{(B,C)} = {u.α.B^{j}.C^{k}.D^{l}.E^{m}.β / j, k, l, m ≥ 1 and j ≠ k and u ∈ (X^{□})^{⋆}}

L^{(C,D)} = {u.α.B^{j}.C^{k}.D^{l}.E^{m}.β / j, k, l, m ≥ 1 and k ≠ l and u ∈ (X^{□})^{⋆}}

L^{(D,E)} = {u.α.B^{j}.C^{k}.D^{l}.E^{m}.β / j, k, l, m ≥ 1 and l ≠ m and u ∈ (X^{□})^{⋆}}

Let now

L = L^{B} ∪ L^{C} ∪ L^{D} ∪ L^{E} ∪ L^{(B,C)} ∪ L^{(C,D)} ∪ L^{(D,E)}

It is easy to show that each of the languages L^{B}, L^{C}, L^{D}, L^{E}, L^{(B,C)}, L^{(C,D)}, L^{(D,E)} is a context free finitary language thus L is also context free because the class CFL is closed under finite union. Then the ω-language L.(X^{□})^{ω} is an ω-CFL which is an open subset of (X^{□})^{ω}.

Remark now that any word in sup_{n≥1} F̄_{n}(A^{≈.n}) belongs to the regular ωlanguage

R = a^{+}.b.(X_{A} ∪ (α.B^{+}.C^{+}.D^{+}.E^{+}.β))^{ω}

because every word has an initial segment in the form a^{n}.b with n ≥ 1 and the letters α, B, C, D, E, β are only used to code the erasers ↞_{j} for j ≥ 1.

Consider now the ω-language

L.(X^{□})^{ω} ∩ R

An ω-word σ in this language is a word in R such that σ has an initial word in the form a^{n}.b, with n ≥ 1, and σ contains a segment α.B^{j}.C^{k}.d^{l}.E^{m}.β with j, k, l, m ≥ 1 which does not code any eraser ↞_{j} or codes such an eraser but with j > n. Thus this ω-language is disjoint from the set sup_{n≥1} F̄_{n}(A^{≈.n}). Consider now the ω-language:

A^{•} = sup_{n≥1} F̄_{n}(A^{≈.n}) ∪ L.(X^{□})^{ω} ∩ R]

We can now state the next lemma.

Lemma 5.3 Let A ⊆ X_{A}^{ω} be a Π_{2}^{0}-complete subset of X_{A}^{ω}. Then A^{•} is a Σ_{ω}^{0}- subset of (X_{A} ∪ {α, β, B, C, D, E})^{ω} which is not a Borel set of finite rank.

Proof. Let A ⊆ X_{A}^{ω} be a Π_{2}^{0}-complete subset of X_{A}^{ω}. Then we have already seen that sup_{n≥1} F̄_{n}(A^{≈.n}) is a Σ_{ω}^{0}-subset of (X_{A}∪{α, β, B, C, D, E})^{ω}. On the other side it is easy to see, from proposition 3.5, that the ω-regular language R is a Π_{2}^{0}-set because

R = (R′)^{δ}

where R′ is the finitary (regular) language defined by

R′ = a^{+}.b.(X_{A} ∪ (α.B^{+}.C^{+}.D^{+}.E^{+}.β))^{+}

Then the ω-language

L.(X^{□})^{ω} ∩ R

is the intersection of an open set and of a Π_{2}^{0}-set. Thus it is also a Π_{2}^{0}-set because the class Π_{2}^{0} is closed under finite intersection. Then the ω-language

A^{•} = sup_{n≥1} F̄_{n}(A^{≈.n}) ∪ L.(X^{□})^{ω} ∩ R]

is a Σ_{ω}^{0}-subset of (X_{A} ∪ {α, β, B, C, D, E})^{ω} because the class Σ_{ω}^{0} is closed under finite union.

We want now to prove that A^{•} is not a Borel set of finite rank. Assume, on the contrary, that A^{•} is of finite rank J, where J is an integer ≥ 1. Then the intersection of A^{•} and of the complement of L.(X^{□})^{ω} ∩ R would be the intersection of a Π_{J+1}^{0}-set and of a Σ_{2}^{0} hence Π_{3}^{0}-set. Hence

sup_{n≥1} F̄_{n}(A^{≈.n}) = A^{•} ∩ (L.(X^{□})^{ω} ∩ R)^{−}

would be a Π_{k}^{0}-set, with k = max(3, J +1). But this is not possible because we know from the preceding lemma that sup_{n≥1} F̄_{n}(A^{≈.n}) is a Borel set of infinite rank. □

We can now state the following

Theorem 5.4 Let A ⊆ X_{A}^{ω} be an ω-regular language over the alphabet X_{A}. Then the ω-language

A^{•} = sup_{n≥1} F̄_{n}(A^{≈.n}) ∪ L.(X^{□})^{ω} ∩ R]

is an ω-CFL over the alphabet (X_{A} ∪ {α, β, B, C, D, E}).

Proof. We have already seen that L.(X^{□})^{ω} is an ω-CFL, thus

L.(X^{□})^{ω} ∩ R

is also an ω-CFL because the class of omega context free languages is closed under intersection with ω-regular languages, [CG77].

Suppose the ω-regular language A ⊆ X_{A}^{ω} is accepted by the deterministic Muller automaton A = (K, X_{A}, δ, q_{0}, F_{A}) where A′ = (K, X_{A}, δ, q_{0}) is a FSM and F_{A} ⊆ 2^{K} is the collection of designated state sets.

We shall find a MPDA B accepting an ω-CFL L(B) such that

sup_{n≥1} F̄_{n}(A^{≈.n}) ⊆ L(B) ⊆ A^{•} = sup_{n≥1} F̄_{n}(A^{≈.n}) ∪ [L.(X^{□})^{ω} ∩ R]

Thus we shall have

A^{•} = L(B) ∪ [L.(X^{□})^{ω} ∩ R]

And this will imply that A^{•} is an ω-CFL because the class CF L_{ω} is closed under finite union [CG77].

It is easy to have L(B) ⊆ R because if L(B′) is an ω-CFL which is not included into R one can replace it by L(B) = L(B′)∩R which is then an ω-CFL verifying L(B) = L(B′) ∩ R ⊆ R.

Recall now that

L.(X^{□})^{ω} ∩ R

is the set of all ω-words in R having an initial segment in the form a^{n}.b, with n ≥ 1, and containing a segment α.B^{j}.C^{k}.d^{l}.E^{m}.β with j, k, l, m ≥ 1 which does not code any eraser ↞_{j} or codes such an eraser but with j > n.

Thus, in order to define the MPDA B, we have only to consider the behaviour of B when reading ω-words in the form

a^{n}.b.u

where n ≥ 1 and u ∈ (X_{A} ∪ (α.B^{+}.C^{+}.D^{+}.E^{+}.β))^{ω} is such that the letters α, B, C, D, E, β in u are only used to code the erasers ↞_{j} for 1 ≤ j ≤ n. ( In order to simplify our notations, we shall sometimes write in the sequel ↞_{j}= α.B^{j}.C^{j}.D^{j}.E^{j}.β and call eraser either ↞_{j} or its code α.B^{j}.C^{j}.D^{j}.E^{j}.β, with j ≥ 1 ).

And we have to find a MPDA B such that L(B) contains such a word a^{n}.b.u if and only if u ∈ F̄_{n}(A^{≈.n}).

So we have to look first at ω-words in F̄_{n}(A^{≈.n}). In such a word σ ∈ F̄_{n}(A^{≈.n}), there are (codes of) erasers ↞_{1}, …, ↞_{n}. The ω-word σ is in F̄_{n}(A^{≈.n}) if and only if after the operations of erasing ( with the erasers ↞_{1}, ..., ↞_{n} ) have been achieved in σ, then the resulting word is in A.

Because of the inductive definition of the sets A^{≈.n}, the operations of erasing have to be done in a good order: in an ω-word which contains only the erasers ↞_{1}, ..., ↞_{n}, the first operation of erasing uses the last eraser ↞_{n}, then the second one uses the eraser ↞_{n−1}, and so on …

Therefore these operations satisfy the following properties:

(a) An eraser ↞_{j} may only erase letters c ∈ X_{A} or other erasers ↞_{k} with k < j.

(b) Assume that in a word u ∈ F̄_{n}(A^{≈.n}), there is a segment c.v.x where c is either in X_{A} or in the set {↞_{1}, …, ↞_{n−1}}, and x is (the code of) an eraser ↞_{k} which erases c when the operations of erasing are successively achieved. Now if there is in the segment v (the code of) an eraser ↞_{j} which erases e, where e ∈ X_{A} or e is (the code of) another eraser, then e must belong to v (it is between c and x in the word u); moreover the operation of erasing using the eraser ↞_{j} has been achieved before that one using the eraser ↞_{k} and this implies that k ≤ j. Thus the integer k must verify:

k ≤ min[ j / an eraser ↞_{j} has been used into v]

We can now informally describe the behaviour of the MPDA B when reading a word a^{n}.b.u such that the letters α, B, C, D, E, β are only used in u to code the erasers ↞_{j} for 1 ≤ j ≤ n.

After the reading of the initial segment in the form a^{n}.b, the MPDA B simulates the Muller automaton A until it guesses, using the non determinism, that it begins to read a segment w which contains erasers which really erase and some letters of X_{A} or some other erasers which are erased when the operations of erasing are achieved in u.

Then, using the non determinism, when B reads a letter c ∈ X_{A} it may guess that this letter will be erased and push it in the pushdown store, keeping in memory the current state of the Muller automaton A.

In a similar manner when B reads the code ↞_{j}= α.B^{j}.C^{j}.D^{j}.E^{j}.β of an eraser, it may guess that this eraser will be erased (by another eraser ↞_{k} with k > j) and then it pushes in the store the finite word γ.E^{j}.ε, where γ, E, ε are in the pushdown alphabet.

But B may also guess that the eraser ↞_{j}= α.B^{j}.C^{j}.D^{j}.E^{j}.β will really be used as an eraser. If it guesses that the code of ↞_{j} will be used as an eraser, B has to pop from the top of the pushdown store either a letter of c ∈ X_{A} or the code γ.E^{i}.ε of another eraser ↞_{i}, with i < j, which is erased by ↞_{j}.

It would be easy for B to check whether i < j when reading the initial segment α.B^{j} of ↞_{j}.

But as we remarked in item (b) above, the MPDA B has also to check that the integer j is smaller or equal than every integer p such that an eraser ↞_{p} has been used since the letter c ∈ X_{A} or the code γ.E^{i}.ε was pushed in the store. Then, after having pushed in the pushdown store some letter x ∈ X_{A} or the code x = γ.E^{i}.ε of an eraser, and before it pops it from the top of the store, B has to keep in the memory of the stack the integer

k = min[p / some eraser ↞_{p} has been used since x was pushed in the stack ]

For that purpose B pushes the finite word L_{2}.S^{k}.L_{1} in the pushdown store (L_{1} is pushed first, then S^{k} and the letter L_{2} are pushed in the stack), where L_{1}, L_{2} and S are new letters added to the pushdown alphabet.

So, when B guesses that ↞_{j}= α.B^{j}.C^{j}.D^{j}.E^{j}.β will be really used as an eraser, there is at the top of the stack either a letter c ∈ X_{A} or a code γ.E^{i}.ε of an eraser which will be erased or a code L_{2}.S^{k}.L_{1}. The behaviour of B is then as follows.

Assume first there is at the top of the stack a code L_{2}.S^{k}.L_{1}. Then B firstly checks that j ≤ k when reading the segment α.B^{j}.C of the eraser α.B^{j}.C^{j}.D^{j}.E^{j}.β. If j ≤ k holds, then B pops completely, using λ-transitions, the word L_{2}.S^{k}.L_{1} from the top of the stack. (B has checked it is allowed to use the eraser ↞_{j}).

Then there is now in every case at the top of the stack either a letter c ∈ X_{A} or a code γ.E^{i}.ε of an eraser which will be erased. The MPDA B pops this letter c or the code γ.E^{i}.ε ( having checked that j > i after reading the segment α.B^{j}.C^{j} of the eraser α.B^{j}.C^{j}.D^{j}.E^{j}.β ). We have to consider what is now at the top of the stack and distinguish three cases:

(1) If there is now at the top of the stack the bottom symbol Z_{0}, then the MPDA B, after having completely read the eraser ↞_{j}, may pursue the simulation of the Muller automaton A or guesses that it begins to read another segment v which will be erased, hence the next letter c ∈ X_{A} or the next code α.B^{m}.C^{m}.D^{m}.E^{m}.β of the word will be erased and then B pushes the letter c ∈ X_{A} or the code γ.E^{m}.ε of ↞_{m} in the pushdown store.

(2) If there is now at the top of the stack either a letter c′ ∈ X_{A} or a code γ.E^{m}.ε, then B pushes the code L_{2}.S^{j}.L_{1} in the pushdown store ( j is then the minimum of the set of integers p such that an eraser ↞_{p} has been used since the letter c′ or the code γ.E^{m}.ε has been pushed into the stack).

(3) If there is now at the top of the stack a code L_{2}.S^{l}.L_{1}, then the MPDA B has to compare the integers j and l and to replace L_{2}.S^{l}.L_{1} by L_{2}.S^{j}.L_{1} if j < l. B achieves this task while reading the segment D^{j}.E^{j}.β of the eraser α.B^{j}.C^{j}.D^{j}.E^{j}.β. The MPDA B pops a letter S for each letter D read. It then determines whether j ≤ l. If j ≤ l then B pushes L_{2}.S^{j}.L_{1} when reading the segment E^{j}.β of the eraser ↞_{j}. If j > l, then when every letter S of the code L_{2}.S^{l}.L_{1} has been popped, there are (j − l) letters D of the eraser α.B^{j}.C^{j}.D^{j}.E^{j}.β which have not yet been read by B. When reading these letters the MPDA B pushes (j−l) letters U in the stack, where U is a new letter in the pushdown alphabet. Then, when reading the segment E^{j} of the eraser α.B^{j}.C^{j}.D^{j}.E^{j}.β, the MPDA B firstly pops U^{j−l} (when reading the first (j − l) letters E); Afterwards B pushes again S^{l} in the stack when reading the rest of the eraser α.B^{j}.C^{j}.D^{j}.E^{j}.β.

When the content of the stack is again just Z_{0}, the initial stack symbol of the MPDA B, then B may pursue the simulation of the Muller automaton A or guesses it begin to read a new segment which will be erased when the operations of erasing will be successively achieved. □

We can now state our main result:

Theorem 5.5 Let A ⊆ X_{A}^{ω} be a Π_{2}^{0}-complete ω-regular language over the alphabet X_{A}. Then A^{•} is an omega context free language which is a Σ_{ω}^{0}-subset of (X_{A} ∪ {α, β, B, C, D, E})^{ω} but is not a Borel set of finite rank.

Proof. It follows directly from Lemma 5.3 and Theorem 5.4 □

In particular if B_{2} = {α ∈ {0, 1}^{ω}/∃^{ω}i α(i) = 1} = (0^{⋆}.1)^{ω}, then (B_{2})^{•} is an omega context free language which is a Borel set of infinite rank.

Theorem 5.5 provides infinitely many such ω-CFL over any finite alphabet X of cardinal ≥ 2, because there exist infinitely many Π_{2}^{0}-complete ω-regular languages over the alphabet X, and for such an ω-regular language A it holds that

A^{•} ∩ X^{ω} = a^{+}.b.A

6 Concluding remarks and further work

We knew that the class of omega context free languages exhausts the finite ranks of the Borel hierarchy and that there exist some ω-CFL which are analytic but non Borel sets. We have proven above that there exist some omega context free languages which are Borel sets of infinite rank.

It is well known that Turing machines, with a Büchi or Muller acceptance condition, accept ω-languages of every Borel rank < ω_{1}^{CK}, where ω_{1}^{CK} is the first non recursive ordinal [Sta97a][Mos80][Sim92]. Then the following problem naturally arises: describe the set of infinite Borel ranks of omega context free languages, and in particular find the ordinal

sup{α / there exist some Borel ω − CF L of rank α}

which is of course ≤ ω_{1}^{CK}. Unfortunately we cannot reach some Borel ranks > ω by iterating our operation A → A^{•}. In fact one cannot even reach some Σ_{ω}^{0}-complete set, as it will be explained in [Fin01c] by considering the Wadge degrees of Borel sets.

Recall that the Wadge hierarchy of Borel sets is a great refinement of the Borel hierarchy. We proved in [Fin01b] that the length of the Wadge hierarchy of Borel ω-CFL is an ordinal greater or equal to the Cantor ordinal ε_{0}, which is the first fixed point of the ordinal exponentiation of base ω. Using the above construction of A^{•}, we have improved this result, showing that this length is an ordinal greater than or equal to ε_{ω}, which is the ω^{th} fixed point of the ordinal exponentiation of base ω, [Fin01c].

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

References

[ABB96] J-M. Autebert, J. Berstel and L. Boasson, Context Free Languages and Pushdown Automata, in Handbook of Formal Languages, Vol 1, Springer Verlag 1996.

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

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

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

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

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

[BL69] J.R. Büchi and L. H. Landweber, Solving Sequential Conditions by Finite State Strategies. Trans. Amer. Math. Soc. 138 (1969).

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

[CG77] R. S. Cohen and A. Y. Gold, Theory of ω-Languages, Parts one and two, J. Computer and System Science 15 (1977) 2, 169-184 and 185-208.

[CG78] R. S. Cohen and A. Y. Gold, ω-Computations on Deterministic Pushdown Machines, J. Computer and System Science (1978) 3, 257-300.

[CP97] O. Carton and D. Perrin, Chains and Superchains for ω-Rational Sets, Automata and semigroups, International Journal of Algebra and Computation V ol. 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.

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

[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), 2001, p.85-105.

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

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

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

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

[Fin01c] O. Finkel, On the Wadge Hierarchy of Omega Context Free Languages, in the Proceedings of the International Workshop Logic and Complexity in Computer Science LCCS 2001 held in honour of A. Slissenko for his 60th birthday, Creteil, September 2001, p.69-79.

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

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

[Kam85] M. Kaminsky, A Classification of ω-Regular Languages, Theoretical Computer Science 36 (1985), 217-229.

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

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

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

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

[PP02] D. Perrin and J.-E. Pin, Infinite Words, Book in preparation, available from http://www.liafa.jussieu.fr/jep/InfiniteWords.html [MaN66] R. Mac Naughton, Testing and Generating Infinite Sequences by a Finite

Automaton, Information and Control 9 (1966), 521-530.

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

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

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

[SW74] L. Staiger and K. Wagner, Automatentheoretische und Automatenfreie Charakterisierungen Topologischer Klassen Regulärer Folgenmengen. Elektron. Informationsverarb. Kybernetik EIK 10 (1974) 7, 379-392.

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

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

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

[WY95] Th. Wilke and H. Yoo, Computing the Wadge Degree, the Lifschitz Degree and the Rabin Index of a Regular Language of Infinite Words in Polynomial Time, in: TAPSOFT’ 95: Theory and Practice of Software Development (eds. P.D. Mosses, M. Nielsen and M.I. Schwartzbach), L.N.C.S. 915, p. 288-302, 1995.