TOPOLOGICAL PROPERTIES OF OMEGA CONTEXT FREE

LANGUAGES

Olivier Finkel Equipe de Logique Mathématique CNRS URA 753 et Université Paris 7 U.F.R. de Mathématiques 2 Place Jussieu 75251 Paris cedex 05, France. E Mail: finkel@logique.jussieu.fr

Abstract

This paper is a study of topological properties of omega context free languages (ω-CFL). We first extend some decidability results for the deterministic ones (ω-DCFL), proving that one can decide whether an ω-DCFL is in a given Borel class, or in the Wadge class of a given ω-regular language . We prove that ω-CFL exhaust the hierarchy of Borel sets of finite rank, and that one cannot decide the borel class of an ω-CFL, giving an answer to a question of [LT94]. We give also a (partial) answer to a question of [Sim92] about omega powers of finitary languages. We show that Büchi-Landweber’s Theorem cannot be extended to even closed ω-CFL: in a Gale-Stewart game with a (closed) ω-CFL winning set, one cannot decide which player has a winning strategy. From the proof of topological properties we derive some arithmetical properties of ω-CFL.

Keywords: omega context free languages; topological properties; Wadge class; Borel class; decide the Borel class; omega powers; Gale-Stewart game; arithmetical properties.

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 [PP98] for much results and references.

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

McNaughton’s Theorem implies that ω-regular languages are boolean combination of G_{δ} sets, [MaN66]. Topological properties of ω-regular languages were first studied by L. H. Landweber in [Lan69] where he showed that one can decide whether a given ω-regular language is in a given Borel class.

The hierarchy induced on ω-regular languages by the Borel Hierarchy was refined in [Bar92] and [Kam85] but Wagner had found the most refined one, now called the Wagner hierarchy and which is the hierarchy induced on ωregular languages by the Wadge Hierarchy of Borel sets [Wag79].

This paper is mainly a study of similar results for ω-context free languages.

In sections 2 and 3, we first review some above definitions and results about ω-regular, ω-context free languages, and topology.

In section 4, we study the ω-languages accepted by deterministic omega pushdown automata, called the omega deterministic context free languages ( ω-DCFL ). Walukiewicz proved in [Wal96] that in a Gale-Stewart game with an ω-DCFL as winning set, one can decide which player has a winning strategy. We give a new proof, based on this result, that one can decide whether an ω-DCFL is in a given Borel class, which leads to a much stronger result: one can decide whether an effectively given ω-DCFL is in the Wadge class of an effectively given ω-regular language .

In sections 5, 6 and 7, we next study the class of ω-CFL. We first restate some previous undecidability results. Then we prove that there are ω-CFL in each Borel class of finite order. And that, for any class Σ_{n}^{0} or Π_{n}^{0}, n being an integer, one cannot decide whether an ω-CFL is in Σ_{n}^{0} or Π_{n}^{0} . Our proofs rely on the recent work of J. Duparc about the Wadge hierarchy of Borel sets [Dup99a]. We use the Wadge game, [Wad84], and the operation of exponentiation of sets defined by J. Duparc [Dup99a].

These results give partial answers to questions of W. Thomas and H. Lescow [LT94].

In section 8, we study ω-powers of finitary languages. The ω-power of a language W ⊆ X^{⋆} is a fundamental operation over finitary languages which leads to ω-languages. Whenever W is a regular language (respectively a context free language), then W^{ω} is an ω-regular language , (respectively an ω-CFL). Then the question of the topological complexity of W^{ω} naturally arises and it is posed in [Niw90] [Sim92] [Sta97a] [Sta97b]. When W is a regular language, W^{ω} is a boolean combination of G_{δ} sets because it is an ω-regular set. We prove results on omega powers of finitary context free languages, giving examples of context free languages (L_{n}) such that (L_{n})^{ω} is a Borel set of finite rank n for every integer n ≥ 1.

In section 9 we consider Gale-Stewart games and we prove that Büchi-Landweber Theorem cannot extend to ω-CFL: in Gale Stewart games with closed ω-CFL winning set, one cannot decide which player has a winning stategy.

In section 10 we derive some arithmetical properties of omega context free languages from the preceding topological properties. We prove that one cannot decide whether an ω-CFL is in the arithmetical class Σ_{n} or Π_{n}, for an integer n ≥ 1. Then we show that one cannot decide whether an ω-CFL is accepted by a deterministic Turing machine (or more generally by a deterministic X-automaton as defined in [EH93]) with Büchi (respectively Muller) acceptance condition.

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.

Unlike the case of finite automata, deterministic MP DA do not define the same class of ω-languages as non deterministic MP DA. Let us now define deterministic pushdown machines.

Definition 2.10 A P DM M = (K, Σ, Γ, δ, q_{0}, Z_{0}) is said deterministic (DP DM) iff for each q ∈ K, Z ∈ Γ, and a ∈ Σ:

1. δ(q, a, Z) contains at most one element,

2. δ(q, λ, Z) contains at most one element, and

3. if δ(q, λ, Z) is non empty, then δ(q, a, Z) is empty for all a ∈ Σ.

It turned out that the class of ω-languages accepted by deterministic BP DA is strictly included into the class of ω-languages accepted by deterministic MP DA. Let us denote DCF L_{ω} this latest class, the class of omega deterministic context free languages (ω-DCFL), and DCF L the class of deterministic context free (finitary) languages. Then recall the following:

Proposition 2.11 1. DCF L_{ω} is closed under complementation, but not under union, neither under intersection.

2. DCF L_{ω} ⊊ ω − KC(DCF L) ⊊ CF L_{ω} (these inclusions are strict).

Remark 2.12 If M is a deterministic pushdown machine , then for every σ ∈ Σ^{ω}, there exists at most one run r of M on σ determined by the starting configuration. The DP DM has the continuity property iff for every σ ∈ Σ^{ω}, there exists a unique run of M on σ and this run is complete. It is shown in [CG78] that each ω-language accepted by a DBP DA (respectively DMP DA ) can be accepted by a DBP DA (respectively DMP DA ) with the continuity property. So we shall assume now that all DP DA have the continuity property.

3 Topology

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

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^{ω}. Σ_{3}^{0} or G_{δσ} is the class of countable unions of Π_{2}^{0}-subsets of X^{ω}.

Π_{3}^{0} or F_{σδ} is the class of countable intersections of Σ_{2}^{0} subsets 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^{ω}.

Recall some basic results about these classes:

Proposition 3.3 ([Mos80]) a) Σ_{n}^{0}∪Π_{n}^{0} ⊊ Σ_{n+1}^{0}∩Π_{n+1}^{0}, for each integer n ≥ 1.

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

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

We shall say that a subset of X^{ω} is a Borel set of rank 1 iff it is in Σ_{1}^{0} ∪ Π_{1}^{0} and that it is a Borel set of rank n ≥ 2 iff it is in Σ_{n}^{0} ∪ Π_{n}^{0} but not in Σ_{n−1}^{0} ∪ Π_{n−1}^{0}.

Remark 3.4 The hierarchy defined above is the hierarchy of Borel sets of finite rank. The Borel Hierarchy is also defined for transfinite levels but this will not be useful in the sequel. It may be found in [Mos80] [LT94]

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

Definition 3.5 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.6 A subset L of X^{ω} is a Π_{2}^{0}-subset of X^{ω} iff there exists a set W ⊆ X^{⋆} such that L = W^{δ}.

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

Introduce now the Wadge Hierarchy:

Definition 3.7 For E ⊆ X^{ω} and F ⊆ Y^{ω}, E is said Wadge reducible to F (E ≤_{W} F) iff there exists a continuous function f : X^{ω} → Y^{ω}, such that E = f^{−1}(F). E and F are Wadge equivalent iff E ≤_{W} F and F ≤_{W} E. this will be denoted by E ≡_{W} F. And we shall say that E <_{W} F iff E ≤_{W} F but not F ≤_{W} E.

The relation ≤_{W} is reflexive and transitive, and ≡_{W} is an equivalence relation. The equivalence classes of ≡_{W} are called wadge degrees. W H is the class of Borel subsets of finite rank of a set X^{ω}, where X is a finite set, equipped with ≤_{W} and with ≡_{W}. For E ⊆ X^{ω} and F ⊆ Y^{ω}, if E ≤_{W} F and E = f^{−1}(F) where f is a continuous function from X^{ω} into Y^{ω}, then f is called a continuous reduction of E to F. Intuitively it means that E is less complicated than F because to check whether x ∈ E it suffices to check whether f(x) ∈ F where f is a continuous function. Hence the Wadge degree of an ω-language is a measure of its topological complexity.

Remark 3.8 In the above definition, we consider that a subset E ⊆ X^{ω} is given together with the alphabet X.

Then we can define the Wadge class of a set F:

Definition 3.9 Let F be a subset of X^{ω}. The wadge class of F is [F] defined by: [F] = {E/E ⊆ Y^{ω} for a finite alphabet Y and E ≤_{W} F }.

Recall that each Borel class Σ_{n}^{0} and Π_{n}^{0} is a Wadge class. And that a set F ⊆ X^{ω} is a Σ_{n}^{0} (respectively Π_{n}^{0})-complete set iff for any set E ⊆ Y^{ω}, E is in Σ_{n}^{0} (respectively Π_{n}^{0}) iff E ≤_{W} F. Σ_{n}^{0} (respectively Π_{n}^{0})-complete sets are thoroughly characterized in [Sta86].

There is a close relationship between Wadge reducibility and games which we now introduce. Define first the Wadge game W (A, B) for A ⊆ X_{A}^{ω} and B ⊆ X_{B}^{ω}:

Definition 3.10 The Wadge game W (A, B) is a game with perfect information between two players, player 1 who is in charge of A and player 2 who is in charge of B. Player 1 first writes a letter a_{1} ∈ X_{A}, then player 2 writes a letter b_{1} ∈ X_{B}, then player 1 writes a letter a_{2} ∈ X_{A}, and so on … The two players alternatively write letters a_{n} of X_{A} for player 1 and b_{n} of X_{B} for player 2. After ω steps, the player 1 has written an ω-word a ∈ X_{A}^{ω} and the player 2 has written an ω-word b ∈ X_{B}^{ω}. The player 2 is allowed to skip, even infinitely often, provided he really write an ω-word in ω steps. The player 2 wins the play iff [a ∈ A ↔ b ∈ B], i.e. iff [(a ∈ A and b ∈ B) or (a ∉ A and b ∉ B and b is infinite)].

Recall that a strategy for player 1 is a function σ : (X_{B} ∪ {s})^{⋆} → X_{A}. And a strategy for player 2 is a function f : X_{A}^{+} → X_{B} ∪ {s}. σ is a winning stategy (w.s.) for player 1 iff he always wins a play when he uses the strategy σ, i.e. when the n^{th} letter he writes is given by a_{n} = σ(b_{1} … b_{n−1}), where b_{i} is the letter written by player 2 at step i and b_{i} = s if player 2 skips at step i. A winning strategy for player 2 is defined in a similar manner.

Martin’s Theorem states that every Gale-Stewart Game G(X) (see section 9 below for more details), with X a borel set, is determined and this implies the following :

Theorem 3.11 (Wadge) Let A ⊆ X_{A}^{ω} and B ⊆ X_{B}^{ω} be two Borel sets, where X_{A} and X_{B} are at most countable alphabets. Then the Wadge game W (A, B) is determined : one of the two players has a winning strategy. And A ≤_{W} B iff the player 2 has a winning strategy in the game W (A, B).

Recall that a set X is well ordered by a binary relation < iff < is a linear order on X and there is not any strictly decreasing (for <) infinite sequence of elements in X.

Theorem 3.12 (Wadge) Up to the complement and ≡_{W}, the class of Borel subsets of finite rank of X^{ω}, for X a finite alphabet, is a well ordered hierarchy. There is an ordinal |W H|, called the length of the hierarchy, and a map d_{W}^{0} from W H onto |W H|, such that for all A, B ∈ W H: d_{W}^{0} A < d_{W}^{0} B ↔ A <_{W} B and d_{W}^{0} A = d_{W}^{0} B ↔ [A ≡_{W} B or A ≡_{W} B^{−}].

Remark 3.13 We do not give here the ordinal |W H|. Details may be found in [Dup99a].

It is natural to ask for the restriction of the Wadge Hierarchy to ω-regular languages. In fact there is an effective version of the Wadge Hierarchy restricted to ω-regular languages:

Theorem 3.14 (Corollary of Büchi-Landweber’s Theorem [BL69]) For A and B some ω-regular sets, one can effectively decide which player has a w.s. in the game W (A, B) and the winner has a w.s. given by a transducer.

The hierarchy obtained on ω-regular languages is now called the Wagner hierarchy and has length ω^{ω}. Wagner [Wag79] gave an automata structure characterization, based on notion of chain and superchain, for an automaton to be in a given class. And one can also compute the Wadge degree of any ω-regular language. Wilke and Yoo proved in [WY95] that this can be done in polynomial time. The Wagner hierarchy is also recently studied in [CP97],

[CP98] and [Sel98].

4 Deterministic omega context-free languages

We now study topological properties of the languages in DCF L_{ω}. These are boolean combination of G_{δ} sets. Cohen and Gold proved that one can decide whether an effectively given ω-DCFL in an open or a closed set [CG77]. Linna characterized the ω-languages accepted by DBPDA as the G_{δ} languages in DCF L_{ω} and proved in [Lin77] that one can decide whether an effectively given ω − DCF L is a G_{δ} or a F_{σ} set. We give an essentially different proof of these results, which is heavily based on a recent result of Walukiewicz, [Wal96] and which leads to a much finer result: Not only one can decide whether an effectively given ω − DCF L A (given by a DMPDA accepting A) is in the Borel class F, G, G_{δ} or F_{σ} , but one can decide whether A is in the wadge class of any ω-regular language B.

Let A ⊆ X_{A}^{ω} be an ω−DCF L given by a DMPDA A = (Q_{A}, X_{A}, Γ_{A}, δ_{A}, q_{A,0}, Z_{A,0}, F_{A}) and B ⊆ X_{B}^{ω} be an ω-regular language accepted by a DMA B = (Q_{B}, X_{B}, δ_{B}, q_{B,0}, F_{B}). We define the set C ⊆ (X_{A} ∪ X_{B} ∪ {s})^{ω} by: For σ = a_{1}b_{1}a_{2}b_{2}a_{3}b_{3} … ∈ (X_{A} ∪ X_{B} ∪ {s})^{ω}, let a = a_{1}a_{2}a_{3} … and b = b_{1}b_{2}b_{3} … and (b/s) = b where letters s are removed.

Then σ ∈ C iff [(a ∉ A or (b/s) ∉ B) and (a ∈ A or (b/s) is a finite word or (b/s) ∈ B)].

And σ ∉ C iff [(a ∈ A and (b/s) ∈ B) or (a ∉ A and (b/s) is an infinite word and (b/s) ∉ B)].

The Gale Stewart game G(C) is defined as followed: Player 1 writes a letter a_{1} ∈ X_{A}, then player 2 writes a letter b_{1} ∈ X_{B} ∪ {s} (s for skip), then player 1 writes a letter a_{2} ∈ X_{A}, and player 2 writes a letter b_{2} ∈ X_{B} ∪ {s}… After ω steps, the two players have composed an infinite word: σ ∈ (X_{A} ∪ X_{B} ∪ {s})^{ω}, and player 2 wins the play iff σ ∉ C. We easily see that player 2 has a w.s. in the Wadge game W (A, B) iff he has a w.s. in the game G(C).

It is now easy to show that C is accepted by a deterministic Muller pushdown automaton C: C is essentially the product of the two machines A and B, where suitable accepting conditions are chosen. (The exact definition of these conditions is left to the reader).

In a recent paper, I. Walukiewicz proved that in a pushdown game, one of the two players has a w.s., given by a pushdown transducer which is effectively constructible [Wal96]. He considered pushdown games where each of the two players alternatively plays a move in the graph of configurations of a deterministic pushdown automaton. This result implies that in our game G(C), one of the two players has a w.s. and this strategy is effectively constructible. So we can decide which player has a w.s. in the game W (A, B) , i. e. whether A ≤_{W} B. With a similar construction, we see that one can decide whether B ≤_{W} A.

When this result is applied with B a Π_{2}^{0} complete ω-regular set, for example B = {σ ∈ {0, 1}^{ω}/ there are infinitely many letters 1 in σ} , [Sta86], one can decide whether an effectively given ω-DCFL is a G_{δ} set. The same result holds for the classes F, G, F_{σ}, because there are some Π_{1}^{0} (respectively Σ_{1}^{0}, Σ_{2}^{0} )-complete ω-regular sets, [Sta86].

But when we apply this result to an ω-regular set B, we can decide whether A is in the wadge class of B. And we can decide whether B ≡_{W} A, because we can decide whether A ≤_{W} B and B ≤_{W} A.

5 Decision problems for ω-CFL

We shall say that an ω-CFL A is effectively given when a MPDA accepting A is given. We shall say that an ω-DCFL A is effectively given when a DMPDA accepting A is given.

We now state some undecidability results. Remark that some of these results are not new, but we shall reprove them in order to rely on this proof in the sequel.

Theorem 5.1 Let Σ be an alphabet having at least two letters. It is undecidable, for some effectively given ω-context free languages

A and B in Σ^{ω}, whether:

1. A ∩ B is empty.

2. A ∩ B is infinite.

3. A ∩ B has the continuum power.

4. A^{−} is infinite.

5. A^{−} has the continuum power.

6. A = Σ^{ω}.

Proof. let us first return to the Post correspondance Theorem :

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

Let then Γ = {a, b} and x, y some n-tuples of non empty words of Γ^{⋆}. Let L(x).c = L_{X} = {ba^{i_{k}} … ba^{i_{1}}cx_{i_{1}} … x_{i_{k}}c/k ≥ 1, 1 ≤ i_{j} ≤ n for j ∈ [1, k]}, where c ∉ Γ and Σ = Γ ∪ {c}.

It is well known that L(x) is a deterministic context free language [Gin66], and so is L_{X}. Then L_{X}^{ω} is an ω-CFL, and L_{Y}^{ω} is also an ω-CFL. Remark that L_{X}^{ω} is a G_{δ}-subset of Σ^{ω}, because L_{X}^{ω} = ⋂_{n≥1} L_{X}^{n}.Σ^{ω}. L_{X}^{ω} ∩ L_{Y}^{ω} is non empty iff [∃i_{1}, …, i_{k}, with k ≥ 1, such that x_{i_{1}} … x_{i_{k}} = y_{i_{1}} … y_{i_{k}}] iff [L_{X}^{ω} ∩ L_{Y}^{ω} is infinite] iff [L_{X}^{ω} ∩ L_{Y}^{ω} has the continuum power].

These assertions are undecidable, because of the Post Theorem. Let τ be the morphism {a, b, c}^{⋆} → {a, b}^{⋆} defined by: a → bab, b → ba^{2}b, c → ba^{3}b. τ transforms L_{X}^{ω} into an ω-CFL τ(L_{X}^{ω}) = [τ(L_{X})]^{ω}, because the family CFL is closed under morphism. τ(L_{X}^{ω}) codes with two letters the language L_{X}^{ω}. And the same holds for L_{Y}^{ω}. Then 1), 2) and 3) of the Theorem are proved.

To prove 4), now consider the ω-language Σ^{ω} −(L_{X}^{ω} ∩L_{Y}^{ω}) =(L_{X}^{ω})^{−} ∪(L_{Y}^{ω})^{−}. We shall first prove that (L_{X}^{ω})^{−} = Σ^{ω} − (L_{X}^{ω}) is an ω-CFL. For that prove the following:

Lemma 5.3 ([Gin66]) With the above notations L = L(x)^{−}∩{a, b}^{⋆}c{a, b}^{⋆} is a context free language.

this language L is the union of L_{1} and L_{2}, where L_{1} = L′_{1}.c.{a, b}^{⋆}, L′_{1} being the complement in {a, b}^{⋆} of {ba^{i_{k}} … ba^{i_{1}}/k ≥ 1, 1 ≤ i_{j} ≤ n}. This set is rational, therefore L′_{1} is also rational and by concatenation product, L_{1} is also rational.

Now define L_{2}, following [Gin66]: For each non empty word w ∈ {a, b}^{⋆}, we define: D(w) = {u ≠ λ /u ∈ {a, b}^{⋆}, |u| < |w|}, and J(w) = {u ≠ λ /u ∈ {a, b}^{⋆}, u ≠ w and |u| = |w|} Then for each n-tuple w = (w_{1}, …, w_{n}) of non empty words, we let: M(w) = c{a, b}^{⋆}{a, b} ∪ b{a, b}^{⋆}c ∪ ∪_{1≤i≤n} ∪_{u∈D(w_{i})} (ba^{i}cu ∪ ba^{i}b{a, b}^{⋆}cu) ∪ ∪_{1≤i≤n} ∪_{u∈J(w_{i})} (ba^{i}c{a, b}^{⋆}u ∪ ba^{i}b{a, b}^{⋆}c{a, b}^{⋆}u). M(x) is a rational language, because each set D(w_{i}) and J(w_{i}) is finite. Let the substitution h : {a, b, c}^{⋆} → P ({a, b, c}^{⋆}) defined by a → {a}, b → {b}, and c → M(x), and let L_{2} = h(L(x)). The class CFL being closed under substitution, L(x) and M(x), (and also {a} and {b}) being CFL, the language L_{2} is context free.

L_{2} contains {ba^{i_{k}} … ba^{i_{1}}cw/w ≠ x_{i_{1}} … x_{i_{k}}, w ∈ {a, b}^{⋆}}, and L_{2} ⊆ L(x)^{−} ∩ {a, b}^{⋆}c{a, b}^{⋆}. Then L_{1} ∪ L_{2} = L(x)^{−} ∩ {a, b}^{⋆}c{a, b}^{⋆}, and this language, union of two CFL, is a CFL.

Now consider (L_{X}^{ω})^{−} = [L(x).c]^{⋆}.L.c.Σ^{ω} ∪ C_{fin}, where C_{fin} = {σ ∈ Σ^{ω}/σ contains only a finite number of c}. C_{fin} is an ω-regular language then it is an ω-CFL. [L(x).c]^{⋆}.L.c is a context free language because the class CFL is closed under star operation and concatenation product, so [L(x).c]^{⋆}.L.c.Σ^{ω} is an ω-CFL. The class CF L_{ω} is closed under union [CG77] , then (L_{X}^{ω})^{−} is an ω-CFL, and so is (L_{Y}^{ω})^{−}.

Therefore the union (L_{X}^{ω})^{−} ∪ (L_{Y}^{ω})^{−} =(L_{X}^{ω} ∩ L_{Y}^{ω})^{−} is also an ω-CFL. Denote it by L_{X,Y}. Then it holds that

(L_{X,Y})^{−} = (L_{X}^{ω} ∩ L_{Y}^{ω})

But we have proved that one cannot decide whether (L_{X}^{ω} ∩ L_{Y}^{ω}) is empty, infinite, or has the continuum power. Hence one cannot decide whether the ω-language (L_{X,Y})^{−} is empty (i.e. L_{X,Y} = Σ^{ω}), infinite or has the continuum power. Then 4) 5) and 6) of the Theorem are proved for an alphabet having three letters.

To prove these results for an alphabet having two letters, consider the above morphism τ. Then

{a, b}^{ω}−(τ[L_{X}^{ω}]∩τ[L_{Y}^{ω}]) = ({a, b}^{ω}−τ({a, b, c}^{ω}))∪(τ({a, b, c}^{ω})−(τ[L_{X}^{ω}]∩τ[L_{Y}^{ω}]))

But {a, b}^{ω} −τ({a, b, c}^{ω}) is an ω-regular language therefore it is an ω-CFL. And τ({a, b, c}^{ω}) − (τ[L_{X}^{ω}] ∩ τ[L_{Y}^{ω}]) = τ[{a, b, c}^{ω} − (L_{X}^{ω} ∩ L_{Y}^{ω})] = τ[L_{X,Y}]. Then it is also an ω-CFL because the family CF L_{ω} is closed under λ-free morphism [CG77]. Then the union {a, b}^{ω} − (τ[L_{X}^{ω}] ∩ τ[L_{Y}^{ω}]) is an ω-CFL. Denote

T_{X,Y} = {a, b}^{ω} − (τ[L_{X}^{ω}] ∩ τ[L_{Y}^{ω}])

The 4) 5) and 6) of the Theorem then follow from 1) 2) and 3) already proved, because (T_{X,Y})^{−} = (τ[L_{X}^{ω}] ∩ τ[L_{Y}^{ω}]) and then one cannot decide whether the complement of the ω-CFL T_{X,Y} over the alphabet {a, b} is empty (i.e. T_{X,Y} = {a, b}^{ω}), infinite or has the continuum power.

Remark 5.4 We have defined L_{X,Y} = (L_{X}^{ω} ∩ L_{Y}^{ω})^{−}. This ω-language is an ω-CFL. And one cannot decide whether L_{X,Y} = Σ^{ω}. Two cases may happen. In the first case L_{X,Y} = Σ^{ω} and then it is an open and closed set. And in the second case we shall prove in section 7 that L_{X,Y} is neither open nor closed in Σ^{ω} and we shall deduce further undecidability results about the topological complexity of omega context free languages.

6 Operation ” exponentiation of sets ”

Wadge gave first a description of the Wadge hierarchy of Borel sets, [Wad84]. 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] [Dup99a]. His proof relies on set theoretic operations which are the counterpart of arithmetical operations over ordinals needed to compute the Wadge degrees.

In fact J. Duparc studied the Wadge hierarchy via the study of the conciliating hierarchy. He introduced in [Dup95a] [Dup99a] conciliating sets which are sets of finite or infinite words over an alphabet X, i.e. subsets of X^{⋆} ∪ X^{ω} = X^{≤ω}. It turned out that the conciliating hierarchy is isomorphic to the Wadge hierarchy of non self dual Borel sets, via the following correspondance:

For A ⊆ X_{A}^{≤ω} and d a letter not in X_{A}, define

A^{d} = {x ∈ (X_{A} ∪ {d})^{ω} / x(/d) ∈ A}

where x(/d) is the sequence obtained from x when removing every occurrence of the letter d.

The set theoretic operations are then defined over concilating sets. We shall only need in this paper the operation of exponentiation. We first recall the following:

Definition 6.1 Let X_{A} be a finite alphabet and ↞∉ X_{A}, let X = X_{A} ∪{↞}. Let x be a finite or infinite word over the alphabet X = X_{A} ∪ {↞}. 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. ↞)^{↞} = λ if |u^{↞}| = 0, and for u infinite: (u)^{↞} = lim_{n∈ω}(u[n])^{↞}, where, given β_{n} and u in X_{A}^{⋆}, u ⊑ lim_{n∈ω} β_{n} ↔ ∃n∀p ≥ n β_{p}[|u|] = u.

Remark 6.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.

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.

We can now define the operation A → A^{∼} of exponentiation of conciliating sets:

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

The operation ∼ is monotone with regard to the Wadge ordering and produce some sets of higher complexity, in the following sense:

Theorem 6.4 (Duparc [Dup99a] ) a) For A ⊆ X_{A}^{≤ω} and B ⊆ X_{B}^{≤ω}, A^{d} and B^{d} borel sets, A^{d} ≤_{W} B^{d} ↔ (A^{∼})^{d} ≤_{W} (B^{∼})^{d}.

b) If A^{d} ⊆ (X_{A} ∪ {d})^{ω} is a Σ_{n}^{0}-complete (respectively Π_{n}^{0}-complete) set ( for an integer n ≥ 1 ), then (A^{∼})^{d} is a Σ_{n+1}^{0}-complete (respectively Π_{n+1}^{0}-complete) set.

c) If A ⊆ X_{A}^{ω} is a Π_{n}^{0}-complete set ( for an integer n ≥ 2 ), then (A^{∼}) is a Π_{n+1}^{0}-complete set.

Remark 6.5 c) of preceding Theorem follows b) because whenever A ⊆ X_{A}^{ω} is a Π_{n}^{0}-complete set ( for an integer n ≥ 2 ), then A^{d} is also a Π_{n}^{0}-complete set. And because whenever, for A ⊆ X_{A}^{ω}, A^{d} ⊆ (X_{A} ∪ {d})^{ω} is a Π_{n}^{0}-complete set ( for an integer n ≥ 3 ), then A is also a Π_{n}^{0}-complete set. This property will be useful only in section 8 when we study the ω-powers of finitary languages.

We now prove that the class CF L_{ω} is closed under this operation ∼.

Theorem 6.6 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: v_{n+1} 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 → a ↞ 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. And v_{1} belongs to the finitary language L_{4} = (↞)^{⋆}.(L_{3}.(↞)^{⋆})^{⋆}. This language corresponds to words where every letter of X_{A} has been removed after using the back space operation and this operation maybe has been used also when there was not any letter to erase. L_{4} is a context free language because the class CF L is closed under star operation and concatenation product.

Remark 6.7 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} and L_{4} are deterministic one-counter languages, i.e. L_{3} and L_{4} are accepted by deterministic one-counter automata. And for a ∈ X_{A}, the language L_{3}.a is also accepted by a deterministic one-counter automaton.

Then we can state the following:

Lemma 6.8 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, and then making a left concatenation by the language L_{4}.

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}(L_{4}.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, and so is the language (L_{4}.U′_{i}) by concatenation product. Hence the ω-language A^{∼} is an ω-CFL because ω − KC(CF L) ⊆ CF L_{ω}.

Proposition 6.9 From a MPDA accepting the ω-language A ⊆ X_{A}^{ω}, one can effectively construct a MPDA which accepts the ω-language A^{∼} ⊆ (X_{A}∪ {↞})^{ω}.

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

We shall construct another MPDA M^{∼} which accepts the ω-language A^{∼} over the alphabet X = X_{A} ∪ {↞}. Describe first informally the behaviour of the machine M^{∼} 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_{1} belongs to the context free language L_{4} and v_{n+1} belongs to the context free language L_{3}.

M^{∼} starts the reading as a pushdown automaton accepting the language L_{4}. Then M^{∼} begins to read as M, 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 M. Then , after the reading of v, M^{∼} simulates again the machine M and so on.

More formally M^{∼} = (K^{∼}, X_{A} ∪ {↞}, Γ ∪ {E}, δ^{∼}, q′_{0}, Z_{0}, F^{∼}). where

K^{∼} = K ∪ {q′_{0}} ∪ {q^{1}/q ∈ K}

q′_{0} is a new state not in K

E is a new letter not in Γ

F^{∼} = {P ⊆ K^{∼} / P ∩ K ∈ F }

And the transition relation δ^{∼} is defined by the following cases (where the transition rules (a)-(d) are used to simulate a pushdown automaton accepting L_{4} and the MPDA M^{∼} enters in a state q^{1}, for q ∈ K, when it simulates a one counter automaton accepting L_{3}):

(a) δ^{∼}(q′_{0}, ↞, Z_{0}) = (q′_{0}, Z_{0}).

(b) (q′_{0}, EZ_{0}) ∈ δ^{∼}(q′_{0}, a, Z_{0}), for each a ∈ X_{A}.

(c) δ^{∼}(q′_{0}, ↞, E) = (q′_{0}, λ).

(d) δ^{∼}(q′_{0}, a, E) = (q′_{0}, EE), for each a ∈ X_{A}.

(e) (q, ν) ∈ δ^{∼}(q′_{0}, a, Z_{0}) iff (q, ν) ∈ δ(q_{0}, a, Z_{0}), for each a ∈ X_{A} ∪ {λ} and ν ∈ Γ^{⋆} and q ∈ K.

(f) (q′, ν) ∈ δ^{∼}(q, a, γ) iff (q′, ν) ∈ δ(q, a, γ), for each a ∈ X_{A} ∪ {λ} and γ ∈ Γ and ν ∈ Γ^{⋆} and q, q′ ∈ K.

(g) (q^{1}, Eγ) ∈ δ^{∼}(q, a, γ), for each a ∈ X_{A} and γ ∈ Γ and q ∈ K.

(h) δ^{∼}(q^{1}, a, E) = (q^{1}, EE), for each a ∈ X_{A} and q ∈ K.

(i) δ^{∼}(q^{1}, ↞, E) = (q^{1}, λ).

(j) (q′, ν) ∈ δ^{∼}(q^{1}, a, γ) iff (q′, ν) ∈ δ(q, a, γ), for each a ∈ X_{A} and γ ∈ Γ and ν ∈ Γ^{⋆} and q, q′ ∈ K.

(k) (q^{1}, Eγ) ∈ δ^{∼}(q^{1}, a, γ), for each a ∈ X_{A} and γ ∈ Γ and q ∈ K.

Consider now subsets of X^{≤ω} in the form A∪B, where A is a finitary context free language and B is an ω-CFL. Remark that A and B should not be accepted by the same pushdown automaton (but it may be). Prove then the following.

Proposition 6.10 If C = A∪B, where A is a finitary context free language and B is an ω-CFL over the same alphabet X_{A} = X_{B}, then C^{∼} is also the union of a finitary context free language and an ω-CFL over the alphabet X_{A} ∪ {↞}.

Proof. It is easy to see from the definition of the operation of exponentiation of sets that if C = A ∪ B then: C^{∼} = A^{∼} ∪ B^{∼}. But if B is an ω-CFL over X_{B} = X_{A}, then by Theorem 6.6 B^{∼} is an ω-CFL D_{1}.

Consider now the set A^{∼}: This subset of (X_{A} ∪ {↞})^{≤ω} is constituted of finite and infinite words. Let h be the substitution: X → P ((X_{A} ∪ {↞})^{⋆}) defined by a → a.L_{3} where L_{3} is the context free language defined above. Then it is easy to see that the finite words are obtained by substituting in A the language a.L_{3} for each letter a ∈ X_{A} and concatenating on the left by the language L_{4}. But CF L is closed under substitution and concatenation [Ber79], then this language is a context free finitary language D_{2}.

The infinite words in A^{∼} constitutes the ω-language D_{2}.(L_{3} − {λ})^{ω} if λ ∉ A, and D_{2}.(L_{3} − {λ})^{ω} ∪ (L_{4} − {λ})^{ω} if λ ∈ A,

The languages L_{4} −{λ} and L_{3} −{λ} are context free, thus the set of infinite words in A^{∼} is an ω-CFL D_{3} because ω − KC(CF L) ⊆ CF L_{ω} by Theorem 2.8. Then:

A^{∼} = D_{1} ∪ D_{2} ∪ D_{3}

But CF L_{ω} is closed under union hence D_{1} ∪ D_{3} is an ω-CFL. This ends the proof.

Proposition 6.11 a) if A ⊆ Σ^{⋆} is a context free language, then A^{d} is an ω-CFL.

b) if A ⊆ Σ^{ω} is an ω-CFL, then A^{d} is an ω-CFL.

c) If A is the union of a finitary context free language and of an ω-CFL over the same alphabet Σ, then A^{d} is an ω-CFL over the alphabet Σ ∪ {d}.

Proof of a). Let A ⊆ Σ^{⋆} be a finitary context free language. Substitute first the language (d^{⋆}).a for each letter a ∈ Σ. In such a way we obtain another finitary context free language A′ because CF L is closed under substitution and the languages (d^{⋆}).a are context free. Indeed A^{d} = A′.d^{ω} hence A^{d} is an ω-CFL because ω − KC(CF L) ⊆ CF L_{ω} by Theorem 2.8.

Proof of b). Let A ⊆ Σ^{ω} be an ω-CFL. The ω-language A^{d} is obtained from A by substituting the language (d^{⋆}).a for each letter a ∈ Σ in the words of A. But the class CF L_{ω} is closed under λ-free context free substitution [CG77], hence A^{d} is an ω-CFL.

Proof of c). Let A and B be subsets of Σ^{≤ω} for a finite alphabet Σ. Then we easily see that if C = A ∪ B, C^{d} = A^{d} ∪ B^{d} holds. c) is now an easy consequence of a) and b) because CF L_{ω} is closed under union.

7 topological properties of ω-CFL

From preceding theorems we first deduce that the ω-CFL exhaust the hierarchy of Borel sets of finite rank.

Theorem 7.1 For each non negative integer n ≥ 1, there exist Σ_{n}^{0}-complete ω-CFL A_{n} and Π_{n}^{0}-complete ω-CFL B_{n}.

Proof. For n = 1 consider the Σ_{1}^{0}-complete ω-regular language A_{1} = {α ∈ {0, 1}^{ω}/∃i α(i) = 1} and the Π_{1}^{0}-complete ω-regular language B_{1} = {α ∈ {0, 1}^{ω}/∀i α(i) = 0}. These languages are omega context free languages because REG_{ω} ⊆ CF L_{ω}. Now consider the Σ_{2}^{0}-complete ω-regular language A_{2} = {α ∈ {0, 1}^{ω}/∃^{<ω}i α(i) = 1} and the Π_{2}^{0}-complete ω-regular language B_{2} = {α ∈ {0, 1}^{ω}/∃^{ω}i α(i) = 0}, where ∃^{<ω}i means: ” there exist only finitely many i such that …” , and ∃^{ω}i means: ” there exist infinitely many i such that …”. A_{2} and B_{2} are omega context free languages because they are ω-regular languages.

To obtain omega context free languages further in the Borel hierarchy, consider now O_{1} (respectively C_{1} ) subsets of {0, 1}^{≤ω} such that (O_{1})^{d} (respectively (C_{1})^{d} ) are Σ_{1}^{0}-complete ( respectively Π_{1}^{0}-complete ) . For example O_{1} = {x ∈ {0, 1}^{≤ω} / ∃ i x(i) = 1} and C_{1} = {λ}.

We shall have to apply 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^{∼.(n+1)} = (A^{∼.n})^{∼} .

Now apply n times (for an integer n ≥ 1) the operation ∼ (with different new letters ↞_{1}, ↞_{2}, ↞_{3}, …, ↞_{n}) to O_{1} and C_{1}.

By Theorem 6.4, it holds that for an integer n ≥ 1: (O_{1}^{∼.n})^{d} is a Σ_{n+1}^{0}-complete subset of {0, 1, ↞_{1}, …, ↞_{n}, d}^{ω}. (C_{1}^{∼.n})^{d} is a Π_{n+1}^{0}-complete subset of {0, 1, ↞_{1}, …, ↞_{n}, d}^{ω}.

And it is easy to see that O_{1} and C_{1} are in the form E ∪ F where E is a finitary context free language and F is an omega context free language. Then it follows from Propositions 6.10 and 6.11 that the ω-languages (O_{1}^{∼.n})^{d} and (C_{1}^{∼.n})^{d} are context free. Hence the class CF L_{ω} exhausts the hierarchy of Borel sets of finite rank: we obtain the omega context free languages A_{n} = (O_{1}^{∼.(n−1)})^{d} and B_{n} = (C_{1}^{∼.(n−1)})^{d}, for n ≥ 3.

This gives a partial answer to questions of Thomas and Lescow [LT94] about the hierarchy of ω-CFL: This hierarchy exhausts the hierarchy of Borel sets of finite rank. A natural question now arises: Do the results of [Lan69] extend to ω-CFL? Unfortunately the answer is no. Cohen and Gold proved that one cannot decide whether an ω-CFL is in the class F, G, or G_{δ}. We extend this result to all classes Σ_{n}^{0} and Π_{n}^{0}, for n an integer ≥ 1.

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

Proof. Recall that, by theorem 5.1, it is undecidable, for an effectively given ω-CFL A over the alphabet Σ, whether A = Σ^{ω}. More precisely, one cannot decide whether L_{X,Y} = (L_{X}^{ω} ∩ L_{Y}^{ω})^{−} is equal to Σ^{ω}. Whenever L_{X,Y} = Σ^{ω}, L_{X,Y} is an open and closed subset of Σ^{ω}. We shall prove the following:

Lemma 7.3 Whenever L_{X,Y} ≠ Σ^{ω}, L_{X,Y} is neither open nor closed in Σ^{ω}.

Proof. Suppose L_{X,Y} ≠ Σ^{ω}. Then (L_{X}^{ω} ∩L_{Y}^{ω}) = (L_{X} ∩L_{Y})^{ω} is non empty, so there exists a non empty sequence of indices i_{1}, …, i_{k} such that x_{i_{1}} … x_{i_{k}} = y_{i_{1}} … y_{i_{k}}. And (ba^{i_{k}} … ba^{i_{1}}cx_{i_{1}} … x_{i_{k}}c)^{ω} ∈ (L_{X} ∩ L_{Y})^{ω}. Then each sequence (i_{1} … i_{k})^{n}, where n is an integer ≥ 1, gives another solution of Post correspondance problem. For each n ≥ 1, (ba^{i_{k}} … ba^{i_{1}})^{n} is a prefix of an ω-word of (L_{X}^{ω} ∩ L_{Y}^{ω}). So if (L_{X}^{ω} ∩ L_{Y}^{ω}) was closed, the infinite word (ba^{i_{k}} … ba^{i_{1}})^{ω} should be in (L_{X}^{ω} ∩ L_{Y}^{ω}). This cannot happen because every word in (L_{X}^{ω} ∩ L_{Y}^{ω}) contains an infinite number of letters ”c”. Therefore (L_{X}^{ω} ∩ L_{Y}^{ω}) is not a closed set and L_{X,Y} = (L_{X}^{ω} ∩ L_{Y}^{ω})^{−} is not an open set.

Let us now prove that (L_{X}^{ω} ∩ L_{Y}^{ω}) is not an open subset of Σ^{ω}. Otherwise, this set should be V.Σ^{ω}, for a set V ⊆ Σ^{⋆}.

(L_{X}^{ω} ∩ L_{Y}^{ω}) is supposed to be nonempty, so V ≠ ∅, and for v ∈ V, the word v.a^{ω} should be in (L_{X}^{ω} ∩ L_{Y}^{ω}). This is again not possible because every word in (L_{X}^{ω} ∩ L_{Y}^{ω}) contains an infinite number of letters ”c”. Then (L_{X}^{ω} ∩ L_{Y}^{ω}) is not open and L_{X,Y} = (L_{X}^{ω} ∩ L_{Y}^{ω})^{−} is not closed.

In order to apply precisely the results of J. Duparc, we have here to consider conciliating sets, i.e. subsets of Σ^{≤ω}, for some alphabet Σ. Then we shall prove the following:

Lemma 7.4 a) For each integer n ≥ 1, the language ((L_{X,Y} ∪ Σ^{⋆})^{∼.n})^{d} is an omega context free language.

b) Whenever L_{X,Y} ≠ Σ^{ω}, the language (L_{X,Y} ∪ Σ^{⋆})^{d} is neither open nor closed in (Σ ∪ {d})^{ω}.

c) Whenever L_{X,Y} = Σ^{ω}, it holds that (L_{X,Y} ∪ Σ^{⋆})^{d} = (Σ ∪ {d})^{ω}.

Proof of a). The ω-language L_{X,Y} is context free (see the proof of Theorem 5.1) and Σ^{⋆} is also a context free language. Then a) follows from the propositions 6.10 and 6.11.

Proof of b). To prove that whenever L_{X,Y} ≠ Σ^{ω}, the language (L_{X,Y} ∪ Σ^{⋆})^{d} is neither open nor closed in (Σ∪{d})^{ω}, we use a similar method as for lemma 7.3 with minor modifications.

Proof of c). L_{X,Y} = Σ^{ω} implies (L_{X,Y} ∪ Σ^{⋆})^{d} = (Σ ∪ {d})^{ω} because of the definition of A → A^{d}. And then (L_{X,Y} ∪Σ^{⋆})^{d} is open and closed in (Σ∪{d})^{ω}.

Consider now as above O_{1} (respectively C_{1} ) subsets of {0, 1}^{≤ω} such that (O_{1})^{d} (respectively (C_{1})^{d} ) are Σ_{1}^{0}-complete ( respectively Π_{1}^{0}-complete ): For example O_{1} = {x ∈ {0, 1}^{≤ω} / ∃ i x(i) = 1} and C_{1} = {λ}.

We denote (L_{X,Y} ∪ Σ^{⋆}) = A_{X,Y}.

We cannot decide whether (A_{X,Y})^{d} ≤_{W} (O_{1})^{d} neither whether

(A_{X,Y})^{d} ≤_{W} (C_{1})^{d}, because we cannot decide whether (A_{X,Y})^{d} is open neither whether (A_{X,Y})^{d} is closed.

Now apply the operation ∼, n times, to the sets A_{X,Y} and O_{1} and C_{1}.

Then by Theorem 6.4:

a) (A_{X,Y}^{∼.n})^{d} ≤_{W} (O_{1}^{∼.n})^{d} ↔ (A_{X,Y})^{d} ≤_{W} (O_{1})^{d}

b) (A_{X,Y}^{∼.n})^{d} ≤_{W} (C_{1}^{∼.n})^{d} ↔ (A_{X,Y})^{d} ≤_{W} (C_{1})^{d}

c) (O_{1}^{∼.n})^{d} is Σ_{n+1}^{0}-complete.

d) (C_{1}^{∼.n})^{d} is Π_{n+1}^{0}-complete.

Therefore for each n ≥ 0, one cannot decide whether:

a) (A_{X,Y}^{∼.n})^{d} ≤_{W} (O_{1}^{∼.n})^{d} i.e. (A_{X,Y}^{∼.n})^{d} is in the class Σ_{n+1}^{0}.

b) (A_{X,Y}^{∼.n})^{d} ≤_{W} (C_{1}^{∼.n})^{d} i.e. (A_{X,Y}^{∼.n})^{d} is in the class Π_{n+1}^{0}.

Remark 7.5 We can use standard construction methods to find a (non deterministic) Muller pushdown automaton 𝔸_{X,Y}^{n} which accepts the language (A_{X,Y}^{∼.n})^{d}, because from a MPDA which accepts an ω-language A, we can effectively construct a MPDA which accepts A^{∼}. And it is clear from the proof of proposition 6.10 that if C = A ∪ B where A is a finitary language accepted by a pushdown automaton 𝔸 and B is an ωlanguage accepted by a MPDA 𝔹, then we can construct a pushdown automaton 𝔸′ accepting finite words and a MPDA 𝔹′ such that C^{∼} = L(𝔸′) ∪ L(𝔹′). And the operation A → A^{d} is also effective in the same manner from the proof of proposition 6.11.

From the above proof , we can deduce that one cannot decide whether the intersection of the two deterministic ω-CFL L_{X}^{ω} and L_{Y}^{ω} is open (respectively closed):

Theorem 7.6 One cannot decide whether the intersection of two ω-DCFL is open (respectively closed).

Remark 7.7 The languages L_{X}^{ω} and L_{Y}^{ω} are in fact accepted by Büchi deterministic PDA. In terms of [Sta97a], we can write the above result as: It is undecidable whether the intersection of two effectively given ω-languages in DPDA(inf, ⊓) is in DPDA(ran, ⊓) (respectively DPDA(ran, ⊆))

8 ω-powers of finitary languages

The ω-power of a language W ⊆ X^{⋆} is a fundamental operation over finitary languages which leads to ω-languages. Whenever W is a regular language (respectively a CFL), then W^{ω} is an ω-regular language , (respectively an ω-CFL). The question of the topological complexity of W^{ω} naturally arises. When W is a regular language, W^{ω} is a boolean combination of G_{δ} sets because it is an ω-regular set.

In order to study the topological complexity of W^{ω}, when W is a context free language, we first introduce a variant of the definition of A^{∼}:

Definition 8.1 For A ⊆ X_{A}^{≤ω} and ↞ ∉ X_{A}, let X = X_{A} ∪ {↞} and A^{≈} = {x ∈ (X_{A} ∪ {↞})^{≤ω}/x^{↞} ∈ A}, where 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 u in X_{A}^{⋆}, u ⊑ lim_{n∈ω} β_{n} ↔ ∃n∀p ≥ n β_{p}[|u|] = u.

The only difference is that here: (u. ↞)^{↞} is undefined if |u^{↞}| = 0. It is easy to see ( from Duparc’s proof [Dup99a] ) that if A ⊆ X_{A}^{ω} is a Borel set such that A ≠ X_{A}^{ω}, i.e. A^{−} ≠ ∅, then A^{≈} is wadge equivalent to A^{∼} because:

a) In the Wadge game W (A^{∼}, A^{≈}) the player in charge of A^{≈} has clearly a winning strategy which consists in copying the play of the other player except if player 1 writes the eraser ↞ but he has nothing to erase. In this case player 2 writes for example a letter a ∈ X_{A} and the eraser ↞ at the next step of the play. Now if, in ω steps, player 1 has written the ω-word α and player 2 has written the ω-word β, it is easy to see that [α^{↞} = β^{↞}] and then α ∈ A^{∼} iff β ∈ A^{≈}. Thus player 2 has a winning strategy in the Wadge game W (A^{∼}, A^{≈}).

b) Consider now the Wadge game W (A^{≈}, A^{∼}). The only extra possibility for the player in charge of A^{≈} is to get out of the set A^{≈} by writing the eraser ↞ when in fact there is not any letter of his previous play to erase. But then his final play is surely outside A^{≈}.

If A ≠ X_{A}^{ω}, i.e. A^{−} ≠ ∅, then the player in charge of the set A^{∼} may write a word in (A^{∼})^{−}, (by playing the letter ↞ to erase his previous play and then writing a word in A^{−}) then player 2 has a winning strategy in the Wadge game W (A^{≈}, A^{∼}).

Lemma 8.2 Whenever A ⊆ X_{A}^{ω} is an ω-power of a language L_{A}, i.e. A = L_{A}^{ω}, then A^{≈} is also an ω-power, i.e. there exists a (finitary) language E_{A} such that A^{≈} = E_{A}^{ω}.

Proof. Let h be the substitution: X_{A} → P ((X_{A}∪{↞})^{⋆}) defined by a → L_{3}a where L_{3} is the context free language defined above. Then it is easy to see that now A^{≈} is obtained by substituting in A the language L_{3}.a for each letter a ∈ X_{A}. ( We have not here to consider the language L_{4} which appeared in the expression of A^{∼}). Then E_{A} = h(L_{A}).

Recall now the definition of one counter automata and one counter (and iterated counter) languages: 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. A one counter language is a (finitary) language which is accepted by a one counter automaton by final states. Let OCL be the family of one counter languages. The family ICL of iterated counter languages is the closure under substitution of the family OCL. It is also the class of (finitary) languages which are accepted by a pushdown automaton such that, during any computation, the words in the pushdown store remain in a bounded language in the form (z_{k})^{⋆} … (z_{2})^{⋆}(z_{1})^{⋆}Z_{0}, where {Z_{0}, z_{1}, …, z_{k}} is the pushdown alphabet, [ABB96]. We can now state the following:

Theorem 8.3 For each integer n ≥ 1, there exists a context free language P_{n} such that P_{n}^{ω} is a Π_{n}^{0}-complete set. In fact there is such a language in the subclass of iterated counter languages.

Proof. Let B_{1} = {σ ∈ {0, 1}^{ω}/∀i ≥ 1 σ(i) = 0} = {0^{ω}}. It is a Π_{1}^{0}-complete set of the form P_{1}^{ω} where P_{1} is the singleton containing the only word 0. Remark that P_{1} = {0} is a regular set thus a context free language.

Let then B_{2} = {α ∈ {0, 1}^{ω}/∃^{ω}i α(i) = 1} be the well known Π_{2}^{0}-complete regular ω-language. It holds that B_{2} = (0^{⋆}.1.0^{⋆})^{ω}. Let P_{2} = (0^{⋆}.1.0^{⋆}). Then P_{2} is rational hence context free and then h(P_{2}) ∈ CF L and (h(P_{2}))^{ω} = (P_{2}^{ω})^{≈} is a Π_{3}^{0}-complete set by Theorem 6.4.

Iterating this method n times, we easily obtain a context free language P_{n+2} such that (P_{n+2})^{ω} is a Π_{n+2}^{0}-complete set.

P_{1} and P_{2} are one counter languages because they are rational. The languages L_{3}a, for a ∈ X_{A}, are one counter languages. Then for each integer n ≥ 1 the language P_{n} is an iterated counter language.

Remark 8.4 It is undecidable whether (L_{X} ∩ L_{Y})^{ω} is open (respectively closed). Then it is undecidable, for effectively given CFL L_{1} and L_{2}, whether (L_{1} ∩ L_{2})^{ω} is open (respectively closed).

9 Gale-Stewart games

Recall the following:

Definition 9.1 ([GS53]) Let A ⊆ X^{ω}, where X is a finite alphabet. The game G(A) is a game with perfect information between two players, the player 1 first writes a letter a_{1} ∈ X, then player 2 writes a letter b_{1} ∈ X, then player 1 writes a_{2} ∈ X, and so on … After ω steps, the two players have composed a word σ = a_{1}b_{1}a_{2}b_{2} … of X^{ω}. The player 1 wins the play iff σ ∈ A, otherwise player 2 wins the play.

It follows from Martin’s Theorem that every Gale Stewart game G(A), where A is a Borel set, is determined, i.e. that one of the two players has a winning strategy. And Büchi-Landweber Theorem [BL69] states that whenever A is an ωregular language , one can decide which player has a w.s. and one can effectively construct a w.s. given by a transducer. Walukiewicz’s Theorem extends this result to deterministic pushdown automata [Wal96]. The problem of the synthesis of winning strategies is of practical interest in computer science, because the conditions of a Gale Stewart game may be seen as a specification, while the two players are respectively a non terminating reactive program and the ” environment”.

The question of the effective construction of w.s. is asked in [Tho95] [LT94] and [DFR99].

We show here that for non deterministic ω-CFL A, we cannot even decide which player has a w.s.:

Theorem 9.2 For an effectively given closed ω-CFL A, it is undecidable to determine which player has a winning strategy in the Gale-Stewart game G(A).

Proof. We have shown in section 5 that one cannot decide whether the ω-CFL L_{X,Y}, over the alphabet Σ, is equal to Σ^{ω}. Now define the set B_{X,Y} which is composed of the ω-words σ = a_{1}b_{1}a_{2}b_{2} … such that b_{1}b_{2} … is in L_{X,Y}.

Consider the game G(B_{X,Y}). If L_{X,Y} = Σ^{ω}, player 1 always wins the play, then he has an obvious w.s. If L_{X,Y} ≠ Σ^{ω}, The player 2 has a w.s. which consists in writing a word b_{1}b_{2} … which is not in L_{X,Y}. Then we cannot decide which player has a w.s., because we cannot decide whether L_{X,Y} = Σ^{ω}.

And it is easy to construct, from a MPDA accepting L_{X,Y}, a MPDA accepting B_{X,Y}.

The set L_{X,Y} is a F_{σ}-set, because its complement L_{X}^{ω} ∩ L_{Y}^{ω} is a G_{δ}-set, and we can easily deduce that B_{X,Y} is also a F_{σ}-set.

With a slight modification, we can show that this result remains true where we consider only closed ω-CFL. For that we can replace L_{X}^{ω} ∩ L_{Y}^{ω} by (L_{X} ∩ L_{Y}).Σ^{ω} and call its complement L′_{X,Y}. Then we can show, as in section 5, that L′_{X,Y} is an ω-CFL, and that one cannot decide whether L′_{X,Y} = Σ^{ω}.

But now L′_{X,Y} is a closed ω-CFL, and we can associate a Gale-Stewart game G(B′_{X,Y}), where B′_{X,Y} is another closed ω-CFL, and such that one cannot decide which player has a w.s. in the game G(B′_{X,Y}).

10 Arithmetical properties

In this section we shall deduce from the preceding proofs some results about ω-context free languages and the Arithmetical hierarchy.

First recall 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 10.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 10.2 ([Sta97a]) For each integer n ≥ 1, Σ_{n} ⊊ Σ_{n}^{0} and Π_{n} ⊊ Π_{n}^{0}.

Remark that cardinality arguments suffice to show that the inclusions are strict.

We are now able to prove the following result:

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

Proof. Return to the proof of Theorem 7.2. Let n be an integer ≥ 1. We had found a family of omega context free languages

(A_{X,Y}^{∼.n})^{d} = ((L_{X,Y} ∪ Σ^{⋆})^{∼.n})^{d}

over the alphabet {a, b, c, ↞_{1}, ↞_{2}, …, ↞_{n}, d} such that (A_{X,Y}^{∼.n})^{d} is either {a, b, c, ↞_{1}, ↞_{2}, …, ↞_{n}, d}^{ω} or an ω-language which is neither a Π_{n+1}^{0}- subset nor a Σ_{n+1}^{0}-subset of {a, b, c, ↞_{1}, ↞_{2}, …, ↞_{n}, d}^{ω}. In the first case {a, b, c, ↞_{1}, ↞_{2}, …, ↞_{n}, d}^{ω} is in Σ_{1} ∩ Π_{1} hence also in the class Σ_{n} ( respectively Π_{n}) for each integer n ≥ 1. And in the seccond case it follows from Theorem 10.2 that (A_{X,Y}^{∼.n})^{d} is neither in the class Σ_{n+1} nor in the class Π_{n+1}. But one cannot decide which case holds.

Recall that the ω-languages accepted by deterministic Turing machines with a Büchi (respectively Muller) acceptance condition are exactly the languages which are Π_{2}-languages (respectively boolean combinations of Π_{2}-languages) [Sta97a]. Thus in the above proof we have seen that (A_{X,Y}^{∼.2} )^{d} is either {a, b, c, ↞_{1}, ↞_{2} , d}^{ω} (and in that case it is accepted by a deterministic Büchi or Muller automaton hence also by a Büchi deterministic Turing machine) or an ωlanguage which is neither a Π_{3}^{0}-subset nor a Σ_{3}^{0}-subset of {a, b, c, ↞_{1}, ↞_{2}, d}^{ω}. Hence in this latter case (A_{X,Y}^{∼.2} )^{d} is not a boolean combination of Π_{2}-languages (because Π_{2} ⊆ Π_{2}^{0} and boolean combinations of Π_{2}^{0}-sets are Π_{3}^{0} ∩ Σ_{3}^{0}-sets [Mos80]). As it was proved above, one cannot decide which case holds, so we can deduce the following:

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

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. Then the ω-languages accepted by deterministic X-automata with a Büchi (respectively Muller) acceptance condition are languages which are Π_{2}^{0}-languages (respectively boolean combinations of Π_{2}^{0}-languages) [EH93].

But if Γ is a finite alphabet and X is a storage type, the ω-language Γ^{ω} is accepted by an X-automaton. Hence this provides the following generalization:

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

11 Concluding remarks and further work

This paper is the first of several papers about topological properties of ω-CFL:

1) Omega deterministic CFL.

We have proved that, for any effectively given ω-regular language A and ω-DCFL B, we can decide whether B is in the Wadge class of A, or in the Wadge degree of A. A natural question now arises. Are the Wadge degrees of ω-DCFL also Wadge degrees of ω-regular languages? And can we decide whether A ≡_{W} B, for ω-DCFL A and B? The answer to the first question is in fact an emphatic no: there are many more wadge classes in DCF L_{ω} than in REG_{ω}. Considering the first classes of the Wadge hierarchies of REG_{ω} and of DCF L_{ω}, one get:

The restriction of the Wadge hierarchy to (G_{δ} ∩ F_{σ})-sets in REG_{ω} has only length ω and it is formed by boolean combinations of (regular) closed sets, as it is proved in [SW74] [Wag79]. The restriction of the Wadge hierarchy to (G_{δ} ∩F_{σ})-sets in DCF L_{ω}, (defined by DBPDA) has length ω^{ω}.

J. Duparc gives a proof using descriptive set theory methods [Dup99b].

We shall present in future papers a study of the Wadge hierarchy of ω-DCFL which is analogous to Wagner’s study of ω-regular languages, using notions of chains and superchains, [Fin99b] . This will give an (effective) extension of the Wagner Hierarchy, as announced in [DFR99], although included in the set of boolean combinations of G_{δ}-sets.

We just indicate here how one can generate many more Wadge degrees in DCF L_{ω} than in REG_{ω}. In his study of the Wadge hierarchy of Borel sets, Duparc defined also the operation of multiplication of an ω-language by a countable ordinal. The operation of multiplication by ω is well adapted to the context of ω-DCFL, and it may be defined as follows:

Definition 11.1 ([Dup95a] [Dup99a]) Let A ⊆ Σ^{ω} be an ω-language over the alphabet Σ and O_{+}, O_{−} be two new letters not in Σ, then A.ω is defined over the alphabet Σ ∪ {O_{+}, O_{−}} by:

A.ω = ⋃_{n≥1}(O_{+})^{n}.Σ.(Σ^{⋆}.{O_{+}, O_{−}})^{≤(n−1)}.Σ^{⋆}.(O_{+}.A ∪ O_{−}.A^{−})

Thus an (infinite) word of A.ω has an initial prefix in the form (O_{+})^{n}.a for an integer n ≥ 1 and a ∈ Σ. Then there are at most n more letters from {O_{+}, O_{−}} in the word and the last such letter determines whether the suffix following this last letter O_{+} or O_{−} is in A or in A^{−}. It is not very difficult to show that whenever A is in DCF L_{ω}, (and then A^{−} is also in DCF L_{ω} because DCF L_{ω} is closed under complementation), the ω-language A.ω is also in DCF L_{ω}. But with regard to the Wadge degrees, d_{W}^{0} (A.ω) = d_{W}^{0} (A).ω. Starting with the ω-language Σ^{ω} over the alphabet Σ, of Wadge degree 1, one get languages in DCF L_{ω} which have Wadge degrees ω, ω^{2}, …,ω^{n}, … These languages are (G_{δ}∩F_{σ})-sets because their Wadge degrees are countable ordinals, but they are not boolean combinations of closed sets because their Wadge degrees are ≥ ω (see [Dup99a]).

For instance, the ω-DCFL

⋃_{n≥1}(O_{+})^{n}.Σ.(Σ^{⋆}.{O_{+}, O_{−}})^{≤(n−1)}.Σ^{⋆}.(O_{+}).Σ^{ω}

over the alphabet Σ is not Wadge equivalent to any ω-regular language.

2) Omega CFL.

We have given an answer to a question of [LT94] : CF L_{ω} exhausts the Hierarchy of Borel sets of finite rank. We have shown that the Wadge hierarchy of ω-CFL is not effective: we cannot decide the Wadge class of an ω-CFL, neither its Borel class.

But a lot of questions are still opened: Are all omega context free languages Borel sets of finite rank? Since this paper was written, we have answered to this question, showing that there exist some ω-CFL which are non Borel sets, [Fin00]. What is the length of the Wadge hierarchy of Borel ω-CFL ? In another paper, we show that it is an ordinal ≥ ε_{0}, where ε_{0} is the limit of the ordinals α_{n} defined by α_{0} = ω and α_{n+1} = ω^{α_{n}}, [Fin99a].

Acknowledgements. Thanks to Jean-Pierre Ressayre, Jacques Duparc and Gilles Amiot for many useful and stimulating discussions about Wadge and Wagner Hierarchies. Thanks also 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 Vol. 7, Number 6(1997) p. 673-695.

[CP98] O. Carton and D. Perrin, The Wagner Hierarchy of ω-Rational sets, To appear in International Journal of Algebra and Computation.

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

[Dup99a] J. Duparc, Wadge Hierarchy and Veblen hierarchy: part 1: Borel sets of finite rank, to appear in the Journal of Symbolic Logic. Available from http://www.logigue.jussieu.fr/www.duparc

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

[DFR99] J. Duparc, O. Finkel and J-P. Ressayre, Computer Science and the Fine Structure of Borel Sets, to appear in Theoretical Computer Science. Available from http://www.logigue.jussieu.fr/www.duparc

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

[Fin99a] O. Finkel, Wadge Hierarchy of Omega Context Free Languages, to appear in Theoretical Computer Science.

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

[Fin99b] O. Finkel, Wadge Hierarchy and Deterministic Omega Context Free Languages, in preparation.

[GS53] D. Gale and F. M. Stewart, Infinite Games with Perfect Information, Ann. Math. Studies, Vol 28 (1953) p. 245-266.

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

[PP98] D. Perrin and J.-E. Pin, Infinite Words, Book in preparation, available from http://www.liafa.jussieu.fr/∼jep/synthese.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.

[Tho95] W. Thomas, On the synthesis of strategies in infinite games, in STACS’95, Volume 900 of LNCS, p.1-13, 1995.

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

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

[Wal96] I. Walukiewicz, Pushdown Processes: Games and Model Checking, CAV 96, to appear in Information and Computation.

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