Hierarchies over the context-free Languages

Klaus Reinhardt

Wilhelm-Schickhard Institut für Informatik, Universität Tübingen Sand 13, D-72076 Tübingen e-mail: reinhard@informatik.uni-tuebingen.de

Abstract

Alternation is a generalized principle of nondeterminism. The alternating turing machine is used to characterize the polynomial hierarchy. In this paper we show, that a hierarchy can be characterized with alternating pushdown automata, which we expect to be strict in contrast to a hierarchy with alternating finite automata or alternating space bounded automata. We describe a similar oracle hierarchy over the context-free languages, for which we construct complete languages. We show, that each level of the hierarchy with alternating pushdown automata is included in the corresponding level of the oracle hierarchy and that the logarithmic closure over both levels is the corresponding level of the polynomial hierarchy with one alternation less.

The principle of the alternation is also transfered to grammars. Hereby we prove, that the hierarchy with alternating context-free grammars is identical with the oracle hierarchy over the context-free languages and that in case of unbounded alternation context-free and context-sensitive grammars have the same power.

1 Alternating pushdown automata

In [LSL84] 2-way-pushdown automata without additional work tape AΣ_{k}− 2P DA are considered yielding the result co−NT IME(n) ⊆ AΠ_{2}−2P DA ⊆ co−NT IME(n^{p}) for a p and NSPACE(n) ⊆ AΣ_{k}−2P DA ⊆ DSPACE(n^{2}) for k ≥ 2. The reason for this is, that such a pushdown automaton can guess a word with unrestricted length into its pushdown store using an ∞-loop on existential states and after alternation test whether the guessed word is an accepting path of configurations. In contrast to that in this work we consider pushdown automata which stop on every path.

Definition An alternating 1-way-pushdown automaton is a 9-tuple

A = (Z_{e}, Z_{a}, Σ, Γ, δ, z_{0}, $, E, R)

with the set of states Z = Z_{e} ∪ Z_{a} consisting of existential states Z_{e} and universal states Z_{a}, the input alphabet Σ, the pushdown alphabet Γ, the transition relation δ ⊆ (Z × Σ × Γ) × (Z × Γ^{∗}), the start state z_{0}, the bottom symbol $, the final states E, the rejecting states R, the configuration set C_{A} = Z × Σ^{∗} × Γ^{∗}, the start configuration σ_{A}(x) = ⟨z_{0}, x, $⟩ and the configuration transition relation ⟨z, x_{1}x, gk⟩ |_{\overline{A}} ⟨z′, x, g′k⟩ if and only if z, z′ ∈ Z, k, g′ ∈ Γ^{∗}, g ∈ Γ, g′ ∈ Γ^{∗} and ⟨z, x_{1}, g, z′, g′⟩ ∈ δ. Let |\frac{∗}{A} be the reflexive and transitive closure of |_{\overline{A}} . If z ∈ Z_{a}, then a configuration ⟨z, x, k⟩ ∈ C_{A} is called a universal configuration, if z ∈ Z_{e}, then it is called an existential configuration, if z ∈ R and x = λ, then the configuration is called rejecting, if z ∈ E and x = λ, then it is called accepting. Let l^{i} : C_{M} → {0, 1} be the labeling function defined as follows:

l^{0}(α) := \{ \begin{matrix}1 if α is accepting \\ 0 else \end{matrix}

l^{i+1}(α) := \{ \begin{matrix}1 & if α is accepting, \\ 0 & if α is rejecting, \\ ⋀_{α |_{\overline{M}} β} l^{i}(β) & if α an universal configuration, \\ ⋁_{α |_{\overline{M}} β} l^{i}(β) & if α is an existential configuration \end{matrix}

l^{∗} := sup_{i} l^{i}

An automaton M accepts x if l^{∗}(σ_{M}(x)) = 1, that means L(M) := {x ∈ Σ^{∗} | l^{∗}(σ_{M}(x)) = 1}. A1Σ_{k}P DA (A1Π_{k}P DA) is the set of languages which can be recognized by an alternating 1-way-pushdown automaton which starts in an existential (universal) state, changes the kind of states at most k − 1 times and stops on every path. In particular there are no ∞-loops on λtransitions.

It holds that A1Σ_{0}P DA = A1Π_{0}P DA = DCF L and A1Σ_{1}P DA = CF L.

2 An oracle hierarchy with finite transducers

To define an oracle hierarchy over the context-free languages, we need a transducer, which can not calculate too much by itself (otherwise the oracle would be useless). For this reason the finite transducers according to [Ber79] are used:

Definition A finite transducer T = (Z, Σ, Γ, δ, z_{0}) is an automaton with a 1-way input tape with the input alphabet Σ, a 1-way output tape with the output alphabet Γ, a transition function δ : (Z ×Σ) → (Z ×Γ^{∗}) (or transition relation δ ⊂ (Z × Σ) × (Z × Γ^{∗}), if T nondeterministic) and a start state z_{0} ∈ Z. f_{T} (x) is the word, that is on the output tape, when T has scanned the word x on the input tape. (If T is a nondeterministic transducer then f_{T} is a relation.) L ≤^{f} L′ (L ≤^{nf} L′) means, that there is a deterministic (nondeterministic) finite transducer T with 1-way input tape and 1-way output tape with x ∈ L if and only if there is a calculation f_{T} (x) ∈ L′.

Lemma 2.1 ≤^{f} and ≤^{nf} are transitive

Proof: Let L_{1} ≤^{f} L_{2} by T = (Z_{1}, Σ, Γ, δ_{1}, z_{1}) and L_{2} ≤^{f} L_{3} by U = (Z_{2}, Γ, Δ, δ_{2}, z_{2}) so L_{1} ≤^{f} L_{3} by the transducer V := (Z_{1}×Z_{2}, Σ, Δ, δ, ⟨z_{1}, z_{2}⟩) with δ(⟨z, z_{0}⟩, a) := (⟨z′, z_{n}⟩, y) for δ_{1}(z, a) = (z′, x), δ_{2}(z_{i−1}, x_{i}) = (z_{i}, y_{i}), a ∈ Σ, x_{i} ∈ Γ, x ∈ Γ^{∗}, |x| = n, y_{i} ∈ Δ^{∗}, z, z′ ∈ Z_{1}, z_{i} ∈ Z_{2}, i = 1, ...n, x = x_{1}...x_{n} and y = y_{1}...y_{n}, which calculates the funktion f_{V} (x) = f_{U}(f_{T} (x)), because f_{U}(f_{T} (x)) ∈ L_{3} if and only if f_{T} (x) ∈ L_{2} if and only if x ∈ L_{1}. The proof is analogous for ≤^{nf} with δ as relation.

Definition For a language L and a class of languages S we define

AΠ_{0}FT (L) := {L′ | L′ ≤^{f} L},
AΠ_{k}FT (L) := co−AΣ_{k}FT (L) and
AΣ_{k+1}FT (L) := {L′ | ∃L′′ ∈ AΠ_{k}FT (L) with L′ ≤^{nf} L′′}
AΣ_{k}FT (S) := ⋃_{L∈S} AΣ_{k}FT (L).

For a regular language R all languages in AΣ_{k}FT (R) are regular, because a finite automaton can simulate a finite transducer and test the output immediately. For that reason a ground language for a hierarchy with the context-free languages as Σ_{1}-level should be a non-regular, deterministic context-free language, where all context-free languages can be reduced to by a nondeterministic finite transducer. We use L_{pp}, the language of pushdown protocols of computations, which end with an empty pushdown store. In this protocol an e stands before pushed characters and an a stands before popped characters. For an alphabet Σ the language L_{pp}^{Σ} is defined as follows:

Definition λ ∈ L_{pp}^{Σ} and for all x, y ∈ L_{pp}^{Σ} it holds xy ∈ L_{pp}^{Σ} and ewxaw^{R} ∈ L_{pp}^{Σ} for a w ∈ Σ^{∗}. L_{pp} := L_{pp}^{{0,1}}.

Lemma 2.2 L_{pp}^{Σ} ≤^{f} L_{pp} for every alphabet Σ

Proof: Reduction by a transducer, which performs a coding φ : Σ → {0, 1}^{∗} and hereby replaces a character x behind an e by φ(x) and a character behind an a by φ^{R}(x). It holds AΠ_{0}FT (L_{pp})⊆ DCF L, because a deterministic pushdown automaton can simulate a deterministic transducer and test directly wether its output is a pushdown protocol.

Lemma 2.3 AΣ_{1}FT (L_{pp})=CFL

Proof: ’⊆’: A nondeterministic pushdown automaton can simulate the transducer and test its output directly. ’⊇’: Let L ∈ CF L by the nondeterministic pushdown automaton M = (Z, Σ, Γ, δ, $, z_{0}), which accepts with an empty pushdown store, so it holds L ≤^{nf} L_{pp} by M_{f} = (Z ∪ {z′_{0}}, Σ, {a, e, 0, 1}, δ′, z_{0}) with

\begin{aligned}δ′ & = & \{(z, b) → (z′, aφ^{R}(c)eφ(d_{1})...φ(d_{n}) | (z, b, c) → (z′, d_{1}, ...d_{n}) ∈ δ\}∪ \\ & & \{(z′_{0}, b) → (z′, eφ($)aφ^{R}(c)eφ(d_{1})...φ(d_{n}) | (z_{0}, b, c) → (z′, d_{1}, ...d_{n}) ∈ δ\} \end{aligned}

for a coding of the pushdown alphabet φ : Γ → {0, 1}^{∗}. M_{f} simulates the pushdown automaton and guesses the characters popped by M. Hereby M_{f} produces a pushdown protocol. For an accepting calculation of M with empty pushdown store the output is in L_{pp} if the right contents of the pushdown store is guessed. ¿From Lemma 2.3 and Lemma 2.1 it follows AΣ_{1}FT (L_{pp}) = AΣ_{1}FT (DCF L) = AΣ_{1}FT (CF L) and from that:

Corollary 2.1 AΣ_{k}FT (L_{pp}) = AΣ_{k}FT (DCF L) = AΣ_{k}FT (CF L) for k ≥ 1

Lemma 2.4 A1Σ_{k}P DA ⊆ AΣ_{k}FT (L_{pp}) for all k ≥ 1

Proof: k = 1√ according to Lemma 2.3. Let A1Σ_{k}P DA ⊆ AΣ_{k}FT (L_{pp}), so A1Π_{k}P DA ⊆ AΠ_{k}FT (L_{pp}). For a L ∈ A1Σ_{k+1}P DA by M = (Z_{e}, Z_{a}, Σ, Γ, δ, z_{0}, $, E, V) we have to show, that a L′ ∈ A1Π_{k}P DA exists with L ≤^{nf} L′ by the nondeterministic, finite transducer

T := (Z_{e} × Γ ∪ {z′}, Σ, ({e, a} × Γ) ∪ Z_{a} ∪ Σ, δ_{t}, ⟨z_{0}, $⟩) with z′ new and
δ_{t} := {⟨⟨z_{1}, g⟩, x, ⟨z_{2}, h_{n}⟩, eh_{1}...eh_{n−1}⟩ | ⟨z_{1}, x, g, z_{2}, h_{1}...h_{n}⟩ ∈ δ ∧ z_{1}, z_{2} ∈ Z_{e}}∪

{⟨⟨z_{1}, g⟩, x, ⟨z_{2}, h⟩, ag⟩ | h ∈ Γ, ⟨z_{1}, x, g, z_{2}, λ⟩ ∈ δ ∧ z_{1}, z_{2} ∈ Z_{e}}∪ {⟨⟨z_{1}, g⟩, x, z′, eh_{1}...eh_{n}z_{2}⟩ | ⟨z_{1}, x, g, z_{2}, h_{1}...h_{n}⟩ ∈ δ ∧ z_{1} ∈ Z_{e}, z_{2} ∈ Z_{a}}∪

{⟨z′, x, z′, x⟩ | x ∈ Σ},

T, which simulates the k+1-times alternating pushdown automaton P at the beginning, until it alternates the first time. Hereby T stores the character g on top of the pushdown store ($ at the beginning) in the state, if P pushes h = h_{1}...h_{n} and pops g, then T writes eh_{1}...eh_{n−1} to the output tape and sets g := h_{n}, if P only pops g, then T guesses a new top character of the pushdown store h and writes ah on the output tape. If P alternates, then T writes eg and the state of the simulated pushdown automaton as a mark on the output tape and copies the rest of the input tape to the output tape. A language L′ with the property that x ∈ L(M) if and only if f_{T} (x) ∈ L′ is

L′ = {αzβ | α is a pushdown protocol of some computation,

leaving g in the pushdown store and l^{∗}(⟨z, β, g⟩) = 1}.

L′ can be recognized by a k − 1-times alternating pushdown automaton

P′ := (Z_{e}, Z_{a} ∪ {z′, z_{v}}, ({e, a} × Γ) ∪ Z_{a} ∪ Σ, Γ, δ′, z′, E, V ∪ {z_{v}})

with

δ′ := δ ∪ {⟨z′, eh, k, z′, hk⟩ | h, k ∈ Γ}
∪ {⟨z′, ah, h, z′, λ⟩ | h ∈ Γ}
∪ {⟨z′, ah, k, z_{v}, k⟩ | h ≠ k}
∪ {⟨z′, z, k, z, k⟩ | z ∈ Z_{a}, k ∈ Γ},

P′, which starts in an universal state with deterministicly pushing at first all characters behind an e and popping all characters behind an a or rejecting the input, if the character is not on the top of the pushdown store. After reaching the state mark z ∈ Z_{a}, P′ can simulate P in the state z to the end.

2.1 Further characterizations of the polynomial hierarchy

Definition It holds L ≤^{log} L′ (L ≤^{1−log} L′), if there is a logarithmic (1way) transducer T with x ∈ L if and only if f_{T} (x) ∈ L′. For a class of languages S we say

LOG(S) := {Y | ∃X ∈ S with Y ≤^{log} X}.

Theorem 2.1 For the k-th level of the polynomial hierarchy Σ_{k}^{P} it holds Σ_{k}^{P} = LOG(A1Σ_{k+1}P DA) = LOG(AΣ_{k+1}FT (L_{pp})) for k ≥ 1.

Proof: LOG(A1Σ_{k+1}P DA) ⊆ LOG(AΣ_{k+1}FT (L_{pp})) with Lemma 2.4. LOG(AΣ_{k+1}FT (L_{pp})) ⊆ Σ_{k}^{P}: The logarithmic reduction and k nondeterministics reductions can be performed in polynomial time, the question to a language in CF L or co−CF L on the last level can be answered directly in polynomial time according to [Sud78]. Σ_{k}^{P} ⊆ LOG(A1Σ_{k+1}P DA): According to [Sto76] for odd (even) k the language of the true quantified boolean expressions in conjunctive (disjunctive) normalform with a change of quantifiers restricted by k is log-complete for Σ_{k}^{p}. Here the following variation of presentation is used:

BBF_{k} := { ∃1^{l_{k}}∀0^{l_{k−1}}...∃1^{l_{1}}#c_{1} ∧ c_{2} ∧ ...c_{m} | k odd
c_{i} ∈ {p, n, 0}^{l} and the formula

∃x_{l}, ...x_{l−l_{k}}∀x_{l−l_{k}−1}, ...x_{l−l_{k}−l_{k−1}}, ...∃x_{l_{1}}, ...x_{1}C_{1} ∧ C_{2} ∧ ...C_{m},

with the clauses C_{i} := ⋁_{c_{ij}=p} x_{j} ∨ ⋁_{c_{ij}=n} \overline{x_{j}} is true\}
∪ { ∃1^{l_{k}}∀0^{l_{k−1}}...∀1^{l_{1}}#c_{1} ∨ c_{2} ∨ ...c_{m} | k even
c_{i} ∈ {p, n, 0}^{l} and the formula

∃x_{l}, ...x_{l−l_{k}}∀x_{l−l_{k}−1}, ...x_{l−l_{k}−l_{k−1}}, ...∀x_{l_{1}}, ...x_{1}C_{1} ∨ C_{2} ∨ ...C_{m},

with the clauses C_{i} := ⋀_{c_{ij}=p} x_{j} ∧ ⋀_{c_{ij}=n} \overline{x_{j}} is true\}

It holds BBF_{k} ∈A1Σ_{k+1}P DA by a pushdown automaton K_{k}, which enters an existential state reading a ’∃’ and guesses for the following characters, which stand for a variable, a covering and push therefor ’p’ or ’n’ and enters an universal state reading ’∀’ and guesses universaly the covering for the following variables into the pushdown store. Reaching ’#’ in case of odd k an universal state is entered to choose universally the clause, which has to be tested by a simultaneous popping of the covering. A clause is satisfied, if a ’p’ (’n’) is popped while reading a ’p’ (’n’) from the input, so this literal of the clause is true in the covering and the machine can accept, if the length of the clause is correct. If k is even and we have disjunctive normalform, the conjunction to test is guessed existentially and only accepted, if no ’p’ comes together with an ’n’. An other transition of the last universal state on ’#’ tests the length of the conjunctions. BBF_{ω} ∈ DSPACE(n) according to [Sto76]. It even holds:

Theorem 2.2 A1Σ_{ω}P DA ⊆ DSPACE(n)

Proof: Let L ∈ A1Σ_{ω}P DA by an alternating pushdown automaton P, so P can be simulated by a turingmachine using two stacks, one for the simulation of the pushdown store of P and the other for “backtracking”^{1}. Because the pushdown automaton has no ∞-loop on λ-transitions, a path can only have linear length ([KoHo66], Theorem 2.22) and the contents of both stacks has only linear length.

Theorem 2.3 LOG(A1Σ_{ω}P DA) = P SP ACE

Proof: ’⊆’ follows from Theorem 2.2. ’⊇’: According to [Sto76] BBF_{ω} = ⋃_{k} BBF_{k} is log-complete for P SP ACE

and can be recognized by a pushdown auomat in analogy to that in Theorem 2.1, with the difference, that it can alternate into the same states at any time.

This is stronger than the results of [JeKi89], where polynomial timebounded alternating pushdown automata with additional logarithmic work tape are used: AΣ_{k+1}^{L}P DA_{pt} = Σ_{k}^{p} and AΣ_{ω}^{L}P DA_{pt} = Σ_{ω}^{p} = P SP ACE. The strengthening consists of a separation of the logarithmic reduction from the calculation of the pushdown automaton. L_{pp} provides computations, where there can be a pushing after a popping. The pushdown automaton from Theorem 2.1 recognizing BBF_{k} does not make use of this. For that reason we can take the language L_{sp} = {x&x^{R} | x ∈ {0, 1}^{∗}} of symmetric words as ground oracle to build an oracle hierarchy containig complete problems of levels of the polynomial hierarchy.

Remark: Languages in AΣ_{1}FT (L_{sp}) can be recognized by a nondeterministic pushdown automat, which can only once change from pushing to popping and they can be produced by linear context-free grammars, where only one variable is allowed on the right side of a production.

Theorem 2.4 Σ_{k}^{p} = LOG(AΣ_{k+1}FT (L_{sp}))

Proof: In analogy to Theorem 2.1 with the difference, that only pushdown automata are used, which can only once change from pushing to popping.

Theorem 2.5 If the polynomial hierarchy is strict, then the A1Σ_{k}P DAhierarchy and the AΣ_{k}FT (L_{pp})-hierarchy are strict too.

1Recovering the configuration before the visit of a subtree

Proof: If A1Σ_{k}P DA = A1Σ_{k+1}P DA or AΣ_{k}FT (L_{pp}) = AΣ_{k+1}FT (L_{pp}) held, then a language in Σ_{k}^{p} could be recognized by a polynomial timebounded Σ_{k−1}-maschine, which calculates the reduction of an input to BBF_{k} ∈ A1Σ_{k+1}P DA rsp. ∈ AΣ_{k+1}FT (L_{pp}) and then simulates the k-times alternating pushdown automaton rsp. recognize the language in AΣ_{k}FT (L_{pp}).

It is not known, whether the A1Σ_{k}P DA- and the AΣ_{k}FT (L_{pp})-hierarchies are strict. But in contrary to the polynomial hierarchy it can be shown, that the undermost two steps are strict. Because CF L is not closed under complement, we obtain

Corollary 2.2 CF L ⊊ A1Σ_{2}P DA ⊆ AΣ_{2}FT (L_{pp})

2.2 Komplexities of the undermost levels of the hierarchies

Theorem 2.6 AΠ_{0}FT (L_{pp}) ⊆ DSP ACE(log(n))

Proof: L_{pp} ∈ DSP ACE(log(n)) by following algorithm: test, whether there are as much characters behind an a as behind an e in the input (count the difference up and down), search for every ex in the input by counting the next ay on the same height and test, whether y = x^{R}. An oracle hierarchy with finite transducers can also reach complete problems of levels of the PH using languages in weaker complexity classes as ground language. For example the languages L_{=} = {a^{n}b^{n} | n ∈ N} ∈ 1 −DSPACE(log(n)) and L_{sb} = {x&x^{R} | x is a prefix of the concatenation of binary representations of all numbers 1#10#11#100#101...} ∈ DSPACE(log(log(n))) yield the results AΣ_{k}FT (L_{sp}) ⊆ AΣ_{k+1}FT (L_{=}) and AΣ_{k}FT (L_{sp}) ⊆ AΣ_{k+1}FT (L_{sb}) for k ≥ 1.

Theorem 2.7 L_{sp} ∈ AΠ_{1}FT (L_{=})

Proof: \overline{L_{sp}} ≤^{nf} L_{=} by a transducer, which guesses on input x&y whether

• |x| < |y| and writes for all characters before & an a and writes not for all characters after & a b.

• |x| > |y| and writes not for all characters before & an a and writes for all characters after & a b.

• |x| = |y| but y ≠ x^{R} and guesses a character x_{i} before & and a character y_{i} ≠ x_{i} after & and write for all characters between x_{i} and & an a and for all characters between & and y_{i} a b.

Corollary 2.3 AΣ_{k}FT (L_{sp}) ⊆ AΣ_{k+1}FT (L_{=}) for k ≥ 1

Theorem 2.8 L_{=} ∈ AΣ_{1}FT (L_{sb})

Proof: L_{=} ≤^{nf} L_{sb} by a transducer, which writes for every a and b a guessed character from {0, 1, #} and for a b behind an a additional a & before the character.

Corollary 2.4 AΣ_{k}FT (L_{sp}) ⊆ AΣ_{k+1}FT (L_{sb}) for k ≥ 1

2.3 Complete problems for each level of the oracle hierarchy

Definition DCF L_{e} is the class of the languages, which can be recognized by a deterministic pushdown automaton with empty pushdown store, which makes no λ-transitions.

In [Sud78] ≤^{log}-complete languages for DCF L and CF L where constructed; we show, that in case of DCF L_{e} and CF L this can be improved to ≤^{f}- complete and in the case of DCF L to ≤^{1−log}-complete. As complete language for DCF L we define L_{dv} as follows:

Definition L_{dv} = {x_{0}#x_{1}#...x_{n} | x_{0}x_{i_{1}}x_{i_{2}}...x_{i_{k}} ∈ L_{pp}^{{0,1,2,3}} and there is no x_{l} = ayz with y ∈ {0, 1, 2, 3}, z ∈ {0, 1, 2, 3, e, a}^{∗} and i_{j} < l < i_{j+1}, such that x_{0}x_{i_{1}}...x_{i_{j}}ay is a prefix of a word in L_{pp}^{{0,1,2,3}}.}, that means L_{dv} is the language of the pushdown protocols, which can be interrupted by blocks, for which at their beginning can be seen, that they can not be the continuation of the pushdown protocol.

Remark: AΠ_{0}FT (L_{sp}) ⊆ AΠ_{0}FT (L_{pp}) ⊆ AΠ_{0}FT (L_{dv}) = DCF L_{e} ⊆ DCF L because of L_{sp} ≤^{f} L_{pp} ≤^{f} L_{dv} and the following Theorem.

Theorem 2.9 AΠ_{0}FT (L_{dv})= DCF L_{e}

Proof: ⊆: L_{dv} ∈ DCF L_{e} by a pushdown automaton, which determines at the first character having to be popped after a #, whether popping is possible or whether the input has to be read over to the next #. ⊇: Let L ∈ DCF L_{e} by a deterministic pushdown automaton M = (Z, Σ, Γ, δ, z_{0}, $) without λ-transitions, let φ : Γ → ℕ and ψ : Z → ℕ be numberings, so it holds L ≤^{f} L_{dv} by a transducer T, which calculates the function

f_{T} (b_{1}...b_{n}) = e2(e1)^{φ($)}(e0)^{ψ(z_{0})}e3#g(b_{1})...g(b_{n})a3

with g(b) =

a3#a0#a1#a2x_{1,1}e3#a1#a2x_{1,2}e3#...#a0#a1#a2x_{2,1}e3#...#a1#a2x_{|Γ|,|Z|}e3#,

x_{i,j} = e2(e1)^{φ(d_{1})}...e2(e1)^{φ(d_{n})}(e0)^{ψ(z′)} for δ(z_{i}, b, c_{j}) = (z′, d_{1}...d_{n}). f_{T} is constructed in a way, that a configuration ⟨z, b_{k}...b_{n}, g_{1}...g_{l}⟩ in a calculation of the Automaten M on the input b_{1}...b_{n} relates to the pushdown store contents 21^{φ(g_{1})}21^{φ(g_{2})}...21^{φ(g_{l})}0^{ψ(z)}3 of a computation of the pushdown protocol consisting of blockparts of f_{T} (b_{1}...b_{n}) before g(b_{k}). g(b) represents a table of all transitions with input character b. At first 3 is popped. If M is in the state z_{i}, then i blocks beginning with #a0# have to follow in the pushdown protocol, other blockparts inbetween can not belong to the pushdown protocol. The pushdown protocol is now continuated with blockparts from that spot in g(b_{k}) beginning with a1#a2x_{i,1}e3#a1#a2x_{i,2}e3.... If c_{j} is in the pushdown store of M, then j blocks beginning with #a1# have to follow in the pushdown protocol, other blockparts inbetween can not belong to the pushdown protocol. The pushdown protocol is now continuated with a2x_{i,j}e3, which makes the pushdown store contents relate to the continuating configuration entspricht. Because of 3 in the pushdown store, the pushdown protocol can only be continuated with blockparts from g(b_{k+1}). So M accepts b_{1}...b_{n} with empty pushdown store if and only if f_{T} (b_{1}...b_{n}) ∈ L_{dv}. A complete language for CF L is L_{nv}, whose words can contain additional blockparts apart from the blockparts for a word in L_{dv}. The nondeterminism relates to the choice of the blockparts.

Definition L_{nv} = {x_{0,1} ∨ x_{0,2} ∨ ...x_{0,n_{0}}#x_{1,1} ∨ ...#x_{n,1} ∨ ...x_{n,n_{n}} | ∃i_{0}, ...i_{n} with x_{0,i_{0}}#x_{1,i_{1}}#...x_{n,i_{n}} ∈ L_{dv}}.

Theorem 2.10 CFL=AΠ_{0}FT (L_{nv})=AΣ_{1}FT (L_{nv})

Proof: CF L ⊆AΠ_{0}FT (L_{nv}): Let L ∈ CF L by a nondeterministic pushdown automaton M = (Z, Σ, Γ, δ, z_{0}) without λ-transitions so holds L ≤^{f} L_{nv} by a transducer T, calculating the function

f(b_{1}...b_{n}) = e2(e1)^{φ($)}(e0)^{ψ(z_{0})}e3#g(b_{1})...g(b_{n})a3

with g(b) = a3#a1#a0#a2x_{1,1}e3#a0#y_{1,2}#...#a1#a0#y_{2,1}#...#a0#y_{|Γ|,|Z|}#, y_{i,j} is the concatenation of all a2x_{i,j}e3∨ with

x_{i,j} = e2(e1)^{φ(d_{1})}...e2(e1)^{φ(d_{n})}(e0)^{ψ(z′)}

for (z_{i}, b, c_{j})×(z′, d_{1}...d_{n}) ∈ δ, in analogy to Theorem 2.9 with the difference, that for nondeterministic δ there is a choice between the a2x_{i,j}e3. AΣ_{1}FT (L_{nv})⊆ CF L: A nondeterministic pushdown automaton can simulate the transducer and recognize L_{nv} guessing a blockpart between ∨ from every block between #’s and test whether this is in L_{dv}.

Corollary 2.5 AΣ_{k+1}FT (L_{pp})=AΣ_{k+1}FT (L_{dv})=AΣ_{k}FT (\overline{L_{nv}})

We need the following Lemma for being able to insert additional tests in words of an oracle language.

Lemma 2.5 Let L ∈ AΣ_{k}FT (L_{pp})(∈ AΠ_{k}FT (L_{pp})) for k ≥ 1 and without loss of generality a, e, 0, 1 ∉ Σ, so L′ =: {y_{1}x_{1}y_{2}x_{2}...x_{n}y_{m} | x_{1}x_{2}...x_{n} ∈ L, ∀j x_{j} ≠ λ and ∀i y_{i} ∈ L_{pp}} ∈ AΣ_{k}FT (L_{pp})(∈ AΠ_{k}FT (L_{pp})).

Proof: k = 1: Let L ∈ CF L by an automata A, so L′ ∈ CF L by a automata P, which simulates A and if a string of {a, e, 0, 1}^{∗} appears, interrupt the simulation, put a mark on the pushdown store, test, whether the string is in L_{pp}, remove the mark from the pushdown store and continue the simulation of A. Let L ∈ co−CF L so \overline{L} ∈ CF L. It holds

\begin{aligned}\overline{L′} = \{y_{1}x_{1}y_{2}x_{2}...x_{n}y_{m} & | & ∀j x_{j} ≠ λ, ∀i y_{i} ∈ \{a, e, 0, 1\}^{∗} and \\ & & (x_{1}x_{2}...x_{n} ∈ \overline{L} or ∃i y_{i} ∈ \{a, e, 0, 1\}^{∗} \ L_{pp})\} ∈ CF L \end{aligned}

by a nondeterministic pushdown automat, which guesses, whether x_{1}x_{2}...x_{n} ∈ \overline{L}(∈ CF L) is to test, or whether a y_{i} ∈ \{a, e, 0, 1\}^{∗} \ L_{pp}, so we get L′ ∈ co−CF L. Conclusion from k to k +1: Let L ∈ AΣ_{k+1}FT (L_{pp}) that means L ≤^{nf} L_{1} ∈ AΠ_{k}FT (L_{pp}) by a transducer T_{1}. The problem can now be deferred to the underlying oracle level. Let

L′_{1} := {y_{1}x_{1}y_{2}x_{2}...x_{n}y_{m} | x_{1}x_{2}...x_{n} ∈ L_{1}, ∀j x_{j} ≠ λ and ∀i y_{i} ∈ L_{pp}},

so it holds L′ ≤^{nf} L′_{1} by a transducers T′_{1}, which only copies the characters from {a, e, 0, 1}^{∗} to the output tape without changing the state and otherwise behave like T_{1}. With supposition of induction L′_{1} ∈ AΠ_{k}FT (L_{pp}) and so we get L′ ∈ AΣ_{k+1}FT (L_{pp}). Let L ∈ AΠ_{k+1}FT (L_{pp}) that means \overline{L} ≤^{nf} L_{2} ∈ AΠ_{k}FT (L_{pp}) by a transducer T_{2}. Let

\begin{aligned}L′_{2} & := \{ & y_{1}x_{1}y_{2}x_{2}...x_{n}y_{m} | ∀j x_{j} ≠ λ, ∀i y_{i} ∈ \{a, e, 0, 1\}^{∗} and \\ & & (x_{1}x_{2}...x_{n} ∈ L_{2} or ∃i y_{i} ∈ \{a, e, 0, 1\}^{∗} \ L_{pp})\} \end{aligned}

so it holds \overline{L′} ≤^{nf} L′_{2} by a transducer T′_{2}, which only copies the characters from {a, e, 0, 1}^{∗} to the output tape without changing the state and otherwise behave like T_{2}. It holds

\begin{aligned}\overline{L′_{2}} & = & \{y_{1}x_{1}y_{2}x_{2}...x_{n}y_{m} | x_{1}x_{2}...x_{n} ∈ \overline{L_{2}}, ∀j x_{j} ≠ λ and ∀i y_{i} ∈ L_{pp}\} \\ & ∈ & AΣ_{k}FT (L_{pp}) \end{aligned}

with supposition of induction, from this follows L′_{2} ∈ AΠ_{k}FT (L_{pp}) and from that \overline{L′} ∈ AΣ_{k+1}FT (L_{pp}) and L′ ∈ AΠ_{k+1}FT (L_{pp}).

Theorem 2.11 For all k AΣ_{k}FT (L_{pp}) has complete languages for ≤^{f}.

Proof: by induction: k = 0, 1√ Let L_{1} be complete for AΠ_{k}FT (L_{pp}), so L′_{1} is too according to Lemma 2.5 and for every L ∈AΣ_{k+1}FT (L_{pp}) it holds L ≤^{nf} L_{1} by a nondeterministic transducer M = (Z, Σ, Γ, δ, z_{0}) and so we get

\begin{aligned}L ≤^{f} L_{2} := & \{ & # ∨ x_{1,1} ∨ x_{1,2} ∨ ...x_{1,n_{0}}# ∨ x_{2,1} ∨ ...# ∨ x_{n,1} ∨ ...x_{n,n_{n}} | \\ & & ∃i_{1}, ...i_{n}, m with ex_{1,i_{1}}x_{2,i_{2}}...x_{n,i_{n}}a0^{m} ∈ L′_{1}\} \end{aligned}

by M′ = ({z_{0}, Σ, Γ ∪ {#, ∨, a, e, 0}, δ′, z_{0}) with δ′(z_{0}, b) = (z_{0}, #y), where y is a concatenation of all ∨a0^{φ(z_{1})}c_{1}...c_{k}e0^{φ(z_{2})} with ((z_{1}, b), (z_{2}, c_{1}...c_{k})) ∈ δ. (Let φ(z_{0}) = 0). It holds v = v_{1}...v_{n} ∈ L if and only if there is a calculation of M on v with the series of states z_{0}, ..., z_{n} and functional value f_{M}(v) = c_{1,1}...c_{1,k_{1}}c2, 1...c_{n,k_{n}} ∈ L_{1} if and only if

\begin{matrix}eac_{1,1}...c_{1,k_{1}}e0^{φ(z_{1})}a0^{φ(z_{1})}c_{2,1}...c_{n,k_{n}}e0^{φ(z_{n})}a0^{φ(z_{n})} ∈ L′_{1} and \\ ∀j < n ((z_{j−1}, v_{j}), (z_{j}, c_{j,1}...c_{j,k_{j}})) ∈ δ \end{matrix}

if and only if f_{M′}(v) ∈ L_{2} because a0^{φ(z_{j−1})}cj, 1...c_{j,k_{j}}e0^{φ(z_{j})} appears after the j-th # in f_{M′}(v). It holds L_{2} ∈ AΣ_{k+1}FT (L_{pp}) because of L′_{1} ∈ AΠ_{k}FT (L_{pp}) and L_{2} ≤^{nf} L′_{1} by a transducer, which guesses a blockpart between ∨’s from each block between #’s and copies it to the output tape, thereby a in the first blockpart and e0^{φ(z_{n})} in the last blockpart is omitted, because ea and e0^{φ(z_{n})}a0^{φ(z_{n})} are in L_{pp} as well as λ. The transducer can guess, which blockpart is the last, if it guesses wrong, it determines that at the next # and writes e0a1 to the output tape causing the output not to be in L_{1}.

3 Alternating grammars

Transfering the principle of alternation to grammars, we have to consider strings of variables and terminal symbols of a derivation of a word by a grammar, which in the following we call sentential forms, instead of configurations of automata. In contrast to [Mor89] we take the reduction, that means the direction from the word to the start symbol as the direction of the alternation. Because there are no states which we could divide into existential and universal states, in the following definition the productions and variables of a grammar are divided into existential and universal productions and variables (not disjunctly). Instead of a labeling function for configurations we define sets of sentential forms for each level of alternation. A sentential form α is in a Σ-set, if there is a sentential form in the Π-set under that, from which α can be derived with universal productions; in the undermost level this sentential form must be the start symbol S. A sentential form β consisting only of existential variables and terminal symbols, is in a Π-set, if all sentential forms γ, from which β can be derived by universal productions, are in the Σ-set under that. For technical reasons γ has to be restricted to sentential forms consisting only of universal variables and terminal symbols and in the Π_{1}-level on the characters S and F.

Definition An alternating grammar G is an 8-tuple

G = (V, V_{e}, V_{a}, Σ, P_{e}, P_{a}, S, F) with S, F ∈ V_{e} ∩ V_{a},

for k > 0 we define:

SenF Σ_{0}(G) := SenF Π_{0}(G) := {S}

SenF Σ_{1}(G) := {α ∈ (V_{a} ∪ Σ)^{∗} | S ⟹_{P_{e}}^{∗} α}

SenF Π_{1}(G) := {α ∈ (V_{e} ∪ Σ)^{∗} | ∀β ∈ {S, F }(β ⟹_{P_{a}}^{∗} α → β = S)}

SenF Σ_{k+1}(G) := {α ∈ (V_{a} ∪ Σ)^{∗} | ∃β ∈ (V_{e} ∪ Σ)^{∗} ∩ SenF Π_{k}(G) with β ⟹_{P_{e}}^{∗} α}

SenF Π_{k+1}(G) := {α ∈ (V_{e} ∪ Σ)^{∗} | ∀β ∈ (V_{a} ∪ Σ)^{∗}(β ⟹_{P_{a}}^{∗} α → β ∈ SenF Σ_{k}(G)}.

Because we presume, that S does not appear on the right side of productions in a grammar G, S is in every SenF Π-level and in every SenF Σ-level. Because of S ∈ SenF Π_{2}(G) it holds that

SenF Σ_{1}(G) = {α ∈ (V_{a} ∪ Σ)^{∗} | S ⟹_{P_{e}}^{∗} α}
⊆ {α ∈ (V_{a} ∪ Σ)^{∗} | ∃β ∈ (V_{e} ∪ Σ)^{∗} ∩ SenF Π_{2}(G) with β ⟹_{P_{e}}^{∗} α}
⊆ SenF Σ_{3}(G)

from this we get

SenF Σ_{2k+3}(G) ⊇ SenF Σ_{2k+1}(G) and SenF Π_{2k+2}(G) ⊇ SenF Π_{2k}(G) for all k and so we can define the ω-set as union of all odd sets:

SenF Σ_{ω}(G) := ⋃_{k odd} SenF Σ_{k}(G).

It would be interesting to know, whether we obtain the same results if we define the ω-set as union of all sets, the proof might be difficult for technical reason. Alternating languages can be defined as:

LΣ_{k}(G) := SenF Σ_{k}(G) ∩ Σ^{∗}

CF LΣ_{k} := {L | there is an alternating context-free grammar G with LΣ_{k}(G) := L} CSLΣ_{k} := {L | there is an alternating context-sensitive grammar G with LΣ_{k}(G) := L}

The alternating languages LΠ_{k}(G), LΣ_{ω}(G), CF LΠ_{k}, CF LΣ_{ω}, CSLΠ_{k} and CSLΣ_{ω} can be defined analogously.

Corollary 3.1 CF L = CF LΣ_{1}

Remark: Alternating regular grammars can only produce regular languages.

3.1 Alternating context-free grammars

3.1.1 Examples for alternating grammars

a) It holds L_{p} := {a^{p} | p prim } = LΠ_{2}(G) for the alternating grammar

G := ({S, B, C, D, E, F, G, H}, {S, F }, {B}, {a}, P_{e}, {B → a}, S, F) with
P_{e} := { S → HC | ED | D | G | GB | GBG
D → B | BB | BCB
C → aC | BC | a | B
E → aEa | aE | aD (∗ more a’s at the beginning ∗)
H → aHa | Ha | Da (∗ less a’s at the beginning ∗)
G → Ga | a},

we get SenF Σ_{1}(G) = {α ∈ {B, a}^{≥2} | ¬∃n, m > 1 α = (a^{n}B)^{m}}, because each sentential form containing a block of a’s having a different length than the block of a’s at the beginning of the sentential form can be derived from S. Only if the number of the a’s is prime, no segmentation in blocks of the same length is possible and all sentential forms of {a, B}^{∗}, from which a^{p} can be derived, must be in SenF Σ_{1}(G). b) It holds L_{q} := {a^{2^{n}} | n ∈ ℕ} = LΣ_{2}(G) by the alternating grammar

G := ({S, B, C, D, F, G}, {S, F, B}, {S, F }, {a}, {B → a}, P_{a}, S, F) with
P_{a} := { F → C | CG | GDB | GDBG | Ga
C → a | BCa | aCa | Ba (∗ #a in the block too big ∗)

D → B | BDa | aDa (∗ #a in the block = #characters before B∗)

G → B | a | BG | Ga}.

3.1.2 The equivalence of the oracle hierarchy and the hierarchy of alternating context-free grammars

To prove this equivalence, we show in the following Lemma, that for alternating grammars a Π-level is the set of the complements of the languages in the corresponding Σ-level.

Lemma 3.1 CF LΣ_{k} = co−CF LΠ_{k}

Proof: Let L ∈ CF LΣ_{k} (∈ CF LΠ_{k}) by the alternating grammar G = (V, V_{1}, V_{2}, Σ, P_{1}, P_{2}, S, F), so \overline{L} ∈ CF LΠ_{k} (∈ CF LΣ_{k}) by the alternating grammar G′ := (V, V_{2}, V_{1}, Σ, P_{2}, P_{1}, F, S). In the new Π_{1}-level exactly those sentential forms α are missing, which are included in the old Σ_{1}-level, because of S ⟹_{P_{1}}^{∗} α. In the new Σ_{1}-level exactly those sentential forms β are

included, which are missing in the in the old Π_{1}-level, because of F ⟹_{P_{2}}^{∗} β.

With induction we show, that

SenF Σ_{k}(G) = (V_{2} ∪ Σ)^{∗} \ SenF Π_{k}(G′) andSenF Π_{k}(G) = (V_{1} ∪ Σ)^{∗} \ SenF Σ_{k}(G′).

For k = 1 it holds

SenF Σ_{1}(G)

= {α ∈ (V_{2} ∪ Σ)^{∗} | S ⟹_{P_{1}}^{∗} α}
= {α ∈ (V_{2} ∪ Σ)^{∗} | ∃β ∈ {S, F }(β ⟹_{P_{1}}^{∗} α ∧ ¬β = F)}
= (V_{2} ∪ Σ)^{∗} \ {α ∈ (V_{2} ∪ Σ)^{∗} | ∀β ∈ {S, F }(β ⟹_{P_{1}}^{∗} α → β = F)}
= (V_{2} ∪ Σ)^{∗} \ SenF Π_{1}(G′)

and

SenF Π_{1}(G)
= {α ∈ (V_{1} ∪ Σ)^{∗} | ∀β ∈ {S, F }(β ⟹_{P_{2}}^{∗} α → β = S)}
= (V_{1} ∪ Σ)^{∗} \ {α ∈ (V_{1} ∪ Σ)^{∗} | ∃β ∈ {S, F }(β ⟹_{P_{2}}^{∗} α ∧ ¬Sβ = S}
= (V_{1} ∪ Σ)^{∗} \ {α ∈ (V_{1} ∪ Σ)^{∗} | F ⟹_{P_{2}}^{∗} α}
= (V_{1} ∪ Σ)^{∗} \ SenF Σ_{1}(G′),

because F is the only sentential form from {S, F }, which is not equal to S. Conclusion from k to k+1: Let SenF Σ_{k}(G) = (V_{2} ∪ Σ)^{∗} \ SenF Π_{k}(G′) and SenF Π_{k}(G) = (V_{1} ∪ Σ)^{∗} \ SenF Σ_{k}(G′), so we get

SenF Σ_{k+1}(G)

= {α ∈ (V_{2} ∪ Σ)^{∗} | ∃β ∈ (V_{1} ∪ Σ)^{∗} ∩ SenF Π_{k}(G) with β ⟹_{P_{1}}^{∗} α}

= {α ∈ (V_{2} ∪ Σ)^{∗} | ∃β ∈ (V_{1} ∪ Σ)^{∗}(β ⟹_{P_{1}}^{∗} α ∧ β ∈ (V_{1} ∪ Σ)^{∗} \ SenF Σ_{k}(G′))}

= {α ∈ (V_{2} ∪ Σ)^{∗} | ¬∀β ∈ (V_{1} ∪ Σ)^{∗}(β ⟹_{P_{1}}^{∗} α → β ∈ SenF Σ_{k}(G′))}

= (V_{2} ∪ Σ)^{∗} \ {α ∈ (V_{2} ∪ Σ)^{∗} | ∀β ∈ (V_{1} ∪ Σ)^{∗}(β ⟹_{P_{1}}^{∗} α → β ∈ SenF Σ_{k}(G′))}

= (V_{2} ∪ Σ)^{∗} \ SenF Π_{k+1}(G′)

und analogical

SenF Π_{k+1}(G) = (V_{1} ∪ Σ)^{∗} \ SenF Σ_{k+1}(G′).

¿From that follows

LΣ_{k}(G) = SenF Σ_{k}(G) ∩ Σ^{∗} = (V_{2} ∪ Σ)^{∗} ∩ Σ^{∗} \ SenF Π_{k}(G′) = \overline{LΠ_{k}(G′)} and
LΠ_{k}(G) = SenF Π_{k}(G) ∩ Σ^{∗} = (V_{1} ∪ Σ)^{∗} ∩ Σ^{∗} \ SenF Σ_{k}(G′) = \overline{LΣ_{k}(G′)}.

The following Lemma shows another characterization of a Σ-level of the oracle hierarchy from the second level on, which is different to the reduction with a nondeterministic transducer to the underlying Π-level.

Lemma 3.2 If Σ^{∗} ⊇ L ∈ AΣ_{k+1}FT (L_{pp}) for k ≥ 1, then there is a L_{r} ∈ AΠ_{k}FT (L_{pp}) with L_{r} ⊆ Δ^{∗} and a relation R ⊆ Σ × Δ with x_{1}...x_{n} ∈ L if and only if ∃y_{1}...y_{n} ∈ L_{r} and ∀i ≤ n ⟨x_{i}, y_{i}⟩ ∈ R

Proof: Let L ≤^{nf} L_{1} ∈ AΠ_{k}FT (L_{pp}) by a nondeterministic, finite transducer T = (Z, Σ, Γ, δ, z_{0}) with m := max_{⟨z,x,z′,y⟩∈δ}|y| and \overline{L_{1}} ≤^{nf} L_{2} ∈ AΠ_{k−1}FT (L_{pp}) by the transducer T_{2} = (Z_{2}, Γ, Λ, δ_{2}, z′_{0}). Let

R := {⟨x, ⟨z, y, z′⟩⟩ | ⟨z, x, z′, y⟩ ∈ δ},
Δ := {⟨v, y, z⟩ | y_{i} ∈ Γ^{≤m} ∧ ∃x ⟨v, x, z, y⟩ ∈ δ}
⊆ Z × Γ^{≤m} × Z and
L_{r} := { ⟨z_{0}, y_{1}, z_{1}⟩⟨z_{1}, y_{2}, z_{2}⟩...⟨z_{n−1}, y_{n}, z_{n}⟩ ∈ Δ^{∗} | y_{1}...y_{n} ∈ L_{1}}.

The relation R corresponds to guessing parts of the transitions of a reduction, the oracle language L_{r} must perform a test whether the output of the reduction is in L_{1} and whether the states of the reduction are consistent. It holds

\overline{L_{r}} = \{ ⟨v_{1}, y_{1}, z_{1}⟩⟨v_{2}, y_{2}, z_{2}⟩...⟨v_{n}, y_{n}, z_{n}⟩ | y_{1}...y_{n} ∈ \overline{L_{1}} ∨ ∃i ≤ n v_{i} ≠ z_{i−1}\}
∈ AΣ_{k}FT (L_{pp}) because of
≤^{nf} L_{2}

by a transducer, which simulates T_{2} on the y′_{i}s and additionaly writes an error character ∉ Δ, if a v_{i} ≠ z_{i−1} is found. Therefore L_{r} ∈ AΠ_{k}FT (L_{pp}).

Theorem 3.1 CF LΣ_{k} = AΣ_{k}FT (L_{pp})

Proof: CF LΣ_{k} ⊇ AΣ_{k}FT (L_{pp}) by induction: k = 1√ Let Σ^{∗} ⊇ L ∈ AΣ_{k+1}FT (L_{pp}) and according to the supposition of induction the language \overline{L_{r}} according to Lemma 3.2 in CF LΣ_{k} and according to Lemma 3.1 L_{r} = LΠ_{k}(G) ∈ CF LΠ_{k} by the alternating grammar G = (V, V_{e}, V_{a}, Δ, P_{e}, P_{e}, S), so L = LΣ_{k+1}(G′) ∈ CF LΣ_{k+1} by the alternating grammar

G′ = (V ∪ Δ, V_{e} ∪ Δ, V_{a} ∪ Δ, Σ, P′_{e}, P_{a}, S)

with P′_{e} := P_{e} ∪ {D → E | ⟨E, D⟩ ∈ R ⊆ Σ × Δ}. It holds x_{1}...x_{n} ∈ L if and only if ∃Y_{1}...Y_{n} ∈ L_{r} and ∀i ≤ n ⟨x_{i}, Y_{i}⟩ ∈ R if and only if ∃Y_{1}...Y_{n} ∈ SenF Π_{k}(G′) and Y_{1}...Y_{n} ⟹_{P′_{e}}^{∗} x_{1}...x_{n} if and only if

x_{1}...x_{n} ∈ SenF Σ_{k}(G′). CF LΣ_{k} ⊆ AΣ_{k}FT (L_{pp}): We have to show by induction, that SenF Σ_{k}(G) ∈ AΣ_{k}FT (L_{pp}) holds for L = LΣ_{k}(G). k = 1: SenF Σ_{1}(G) ∈ CF L = AΣ_{1}FT (L_{pp}). Conclusion from k to k+1: Let L = LΣ_{k+1}(G) for the alternating grammar G, so according to Lemma 3.1 it holds

SenF Π_{k}(G) = (V_{1} ∪ Σ)^{∗} \ SenF Σ_{k}(G′)
= (V_{1} ∪ Σ)^{∗} ∩ \overline{SenF Σ_{k}(G′)} ∈ AΠ_{k}FT (L_{pp})

because of SenF Σ_{k}(G′) ∈ AΣ_{k}FT (L_{pp}) according to the supposition of induction. According to Lemma 2.5 there is a language SenF Π_{k}(G)′ with the property SenF Σ_{k+1}(G) ≤^{nf} SenF Π_{k}(G)′ by a transducer T, which guesses a sentential form in SenF Π_{k}(G) and guesses, which character in the sentential form can be derived to which part. For every character Z it holds for the language L_{Z} := {α | Z ⟹_{P_{e}}^{∗} α} ∈ CLF and so we get L_{Z} ≤^{nf} L_{pp} by T_{Z}. For every guessed Z and the corresponding part of the input the transducer T inserts a reduction of this part by T_{Z}. Hereby SenF Π_{k}(G)′ tests the guessed sentential form in SenF Π_{k}(G) and whether the input can be derived from the sentential form. According to Lemma 2.5 it holds SenF Π_{k}(G)′ ∈ AΠ_{k}FT (L_{pp}) and so we get SenF Σ_{k+1}(G) ∈ AΣ_{k+1}FT (L_{pp}).

3.1.3 Reaching the context-sensitive languages with alternating context-free grammars

Theorem 3.2 CSL ⊆ CF LΣω

Proof: Let L ∈ CSL by the context-sensitive grammar G′ = (V, Σ, P, S), where all productions have the form P_{i} = α_{i}X_{i}γ_{i} → α_{i}β_{i}γ_{i}. Then we can get L = LΣ_{ω}(G) for the alternating context-free grammar G := (V_{e} ∪ V_{a} ∪ {S^{∗}}, V_{e}, V_{a}, Σ, P_{e}, P_{a}, S′, F) with

V_{e} := {X′ | X ∈ V } ∪ {V_{i} | P_{i} ∈ P } ∪ {F },
V_{a} := {W_{i} | P_{i} ∈ P } ∪ V ∪ {S′, F },
P_{e} := {X′ → X | X ∈ V } ∪ {V_{i} → β_{i} | P_{i} ∈ P } ∪ {S′ → S^{∗} | S}∪
{S^{∗} → S^{∗}Z | ZS^{∗} | Z ∈ V ∩ Σ} ∪ {S^{∗} → α_{i}W_{i}γ_{i} | P_{i} ∈ P },
P_{a} := {X → X′ | X ∈ V } ∪ {X_{i} → V_{i} | P_{i} ∈ P } ∪ {W_{i} → V_{i} | P_{i} ∈ P }.

The variables V_{i} and W_{i} represent the position of the X_{i} belonging to the production P_{i} = α_{i}X_{i}γ_{i} → α_{i}β_{i}γ_{i} in the sentential form. The production is simulated in the next Σ-level by the production V_{i} → β_{i}. The universal production X_{i} → V_{i} tests, whether the sentential form can be derived and the universal production W_{i} → V_{i} tests, whether the context α_{i} and γ_{i} is given for the production P_{i}, because the set Cont := {δα_{i}W_{i}γ_{i}δ′ | P_{i} ∈ P and δ, δ′ ∈ (V ∩ Σ)^{∗}} is a subset of every SenF Σ-level. The grammar G can simulate one step of derivation by alternating twice. So we get

SenF Π_{0}(G) = {S′},
SenF Σ_{1}(G) = {S′} ∪ {S} ∪ Cont,
SenF Π_{2}(G) = {S′} ∪ {V_{i} | P_{i} = S → δ},
SenF Σ_{3}(G) = {S′} ∪ {β | S → β ∈ P } ∪ Cont ...

By induction it follows in general

SenF Σ_{2k+1}(G, {S′}) = SenF Σ_{2k+2}(G, {S′}) = {α | S ⟹_{P}^{≤k} α} ∪ Cont

and so we get SenF Σ_{ω}(G, {S′}) = ⋃_{k odd} SenF Σ_{k}(G, {S′}) = {α | S ⟹_{P}^{∗} α}∪

Cont for an optional number of alternations and so we get LΣ_{ω}(G) = L(G′).

Remark: It holds CSLΣ_{k} = CSL because of [Imm88]/[Sze88].

This method can be generalized to alternating context-sensitive grammars.

Theorem 3.3 CSLΣ_{ω} = CF LΣ_{ω}

The proof is similar to the last proof, the same technique is used to simulate the existential productions, a complementary technique is used to simulate universal productions and additional productions, which represent transitions between the two simulations, simulate the alternation. The surprise of this result is, that for unboundedly alternating grammars the context is no factor. With results from [Coo71] and [CKS81] we get

Corollary 3.2 CF LΣ_{ω} = CSLΣ_{ω} = ASPACE(n) = DTIME(2^{n}) = AΣ_{0}^{n}P DA.

The proof of CSLΣ_{ω} = ASPACE(n) is analogous to the proof of CSL = NSPACE(n) in [HoUl79], where the alternating linear bounded automaton, which simulates the grammar, has to check before alternating, whether there are existential variables rsp. universal variables left. The grammar, which simulates the automaton, uses an existential variable for an existential state and a universal variable for an universal state.

Remark: This yields the assumption, that the alternating grammars we defined can generate more than the alternating grammars in [Mor89], where LOG(ACF L) = P SP ACE holds. Whereas in both cases P is the logarithmic closure over alternating linear languages, where only one variable can occur in a sentential form.

3.2 Alternating grammars without restrictions

Alternating turing machines can not recognize more than the recursively enumerable languages. The reason is, that only finitely much can be guessed, because a ∞-loop in universal states would produce an infinitely long path, which can not be in the finite accepting subtree. Alternating grammars do not have this restriction, for that they can give a further characterization of the arithmetic hierarchy from [Soare87], which is defined as oracle hierarchy, having the recursively enumerable languages as Σ_{1}-level. The arithmetic hierarchy can also be characterized with changing quantors leading a recursive set, the changing quantors can be simulated in every level of sentential forms by an alternating grammar with diminishing productions.

References

[Ber79] J. Berstel: Transductions and Context-Free Languages, Teubner 1979.

[CKS81] A.K. Chandra, D.C. Kozen, L.J. Stockmeyer; Alternation, Journ. of the ACM 28,1(1981), 114-133.

[Coo71] S.A. Cook: Characterizations of pushdown machines in terms of timebounded computers, Journ. of the ACM 18,1(1971), 4-18

[HoUl79] J.E. Hopcroft, J.D. Ullman: Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979.

[Imm88] N. Immerman: Nondeterministic space is closed under complementation, SIAM Journ. Comput. 15, 5 (1988), 935-938.

[JeKi89] Birgit Jenner, Bernd Kirsig: Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata. Theoretical Informatics and Applications, 1989, 87-99.

[KoHo66] A.J. Korenjak, J.E. Hopcroft: Simple deterministic languages, Conf. Rec. 7th Annual IEEE Symp. Switching and Automata Theory (1966), 36-46.

[LSL84] R.E. Ladner,L.J.Stockmeyer,R.J. Lipton: Alternation bounded auxiliary pushdown automata, Information and Control 62(1984), 93-108.

[Mor89] Etsuro Moriya: A grammatical characterization of alternating pushdown automata, TCS 67 (1989) 75-85.

[Sze88] R. Szelepcsenyi: The Method of forced enumeration for nondeterministic automata, Acta Informatica 26(1988), 279-284.

[Soare87] Robert I. Soare: Recursively Enumerable Sets and Degrees, Springer 1987.

[Sto76] L.J.Stockmeyer: The polynomial-time hierarchy, Theoret. Comp. Sci. 3 (1976), 1-22.

[Sud78] I.H. Sudborough: On the tape complexity of deterministic contextfree languages, Journ. of the ACM 25, 3 (1978),405-414.

[Wra76] C. Wrathall: Complete sets and the polynomial-time hierarchy, Theoret. Comp. Sci. 3 (1976), 23-33.

[figure: EXPTIME; Hasse diagramm of inclusions; CFLΣ_{ω} =CSLΣ_{ω}; PSPACE; CSL; DSPACE(n); A1Σ_{ω}P DA; Π_{k}^{p}; AΠ_{k+1}FT (L_{pp}); A1Π_{k+1}P DA; .; .; .; .; .; .; .; .; .; Π_{2}^{p}; AΠ_{3}FT (L_{pp}); A1Π_{3}P DA; co-NP; AΠ_{2}FT (L_{pp}); A1Π_{2}P DA; Σ_{k}^{p}; AΣ_{k+1}FT (L_{pp}); A1Σ_{k+1}P DA; .; .; .; .; .; .; .; .; .; Σ_{2}^{p}; AΣ_{3}FT (L_{pp}); A1Σ_{3}P DA; NP; AΣ_{2}FT (L_{pp}); A1Σ_{2}P DA; AΣ_{1}FT (L_{pp})=A1Σ_{1}P DA=CFL; co-CFL=AΠ_{1}FT (L_{pp})=A1Π_{1}P DA; LOG(CFL); P; LOG(DCFL); DCFL; DCFL_{e}; NSPACE(log(n)); DSPACE(log(n)); AΠ_{0}FT (L_{pp})]

An arrow means, that the upper class is reachable by logarithmic reduction, thick lines mean strict inclusions.