Empty Alternation ^{⋆}

Klaus-Jörn Lange Klaus Reinhardt

Institut für Informatik, TU München Institut für Informatik, Universität Stuttgart
Arcisstr.21, D-80290 München  Breitwiesenstr.22, D-70565 Stuttgart
e-mail: lange@informatik.tu-muenchen.de e-mail: reinhard@informatik.uni-stuttgart.de

Abstract. We introduce the notion of empty alternation by investigating alternating automata which are restricted to empty their storage except for a logarithmically space-bounded tape before making an alternating transition. In particular, we consider the cases when the depth of alternation is bounded by a constant or a polylogarithmic function. In this way we get new characterizations of the classes AC^{k}, SAC^{k} and P using a push-down store and new characterizations of the class Θ_{2}^{P} using Turing tapes.

1 Introduction

Alternation as introduced by Chandra, Kozen, and Stockmeyer in [CKS81] proved to be a very fruitful and versatile parallel concept in complexity theory. It has been combined with both automata and grammar models. The language families described by alternating devices typically coincide with sequential time or space classes. Furthermore, several well-known hierarchies defined by iterated relativizations of sequential time and space have been characterized by constant depth-bounded alternation, that is by bounding the number of transitions between existential and universal configurations within each computation path by a constant. Let us review these relations for logarithmically space-bounded Turing machines, polynomially time-bounded Turing machines, and for the intermediate model of polynomially time-bounded auxiliary push-down automata:

Logarithmic Space: There are two types of relativizations of nondeterministic logarithmic space, that of Ladner and Lynch (see [LL76]) and that of Ruzzo, Simon, and Tompa (see [RST84]), which is more restricted by prohibiting nondeterministic oracle queries: while writing on its query tape the oracle machine has to work deterministically. While the Ladner-Lynch relativization leads to the Polynomial Hierarchy of Meyer and Stockmeyer , Ruzzo-Simon-Tompa relativization characterizes the “late” Logarithmic Space Hierarchies (see [Lan86]). Thus, in the case of logarithmically space-bounded computations, alternation is related to the weaker kind of relativization.

Polynomial Time: The two types of relativization — Ladner-Lynch vs. Ruzzo-Simon-Tompa — coincide in the case of nondeterministic polynomially timebounded computations and lead to the Polynomial Hierarchy of Meyer and Stockmeyer. In [JKL89] the Deterministic Polynomial Hierarchy was introduced by iterating restricted relativizations of deterministic polynomial time equipped with an nondeterministic polynomial time oracle. This hierarchy does not seem to coincide with the Polynomial Hierarchy but rather shows some similarities to the Logarithmic Space Hierarchies - in particular, its collapse. If we look at alternating polynomial time, bounding the depth of alternation by a constant leads to the Polynomial Hierarchy. We see that in the case of polynomially time-bounded computations, alternation is related to the stronger kind of relativization and the corresponding hierarchy.

⋆ This research was supported by DFG-SFB 342, Teilprojekt A4 “KLARA”.

Polynomial Time of Auxiliary Push-Down Automata: Finally, let us consider polynomially time-bounded two-way push-down automata which are augmented by a logarithmically space-bounded working tape (see [Coo71], [Sud78]). Bounding the depth of alternation of this device by a constant again leads to the Polynomial Hierarchy, but (as in the Ladner-Lynch case) shifted by one level ([JK89], [Bun87]). It is possible to define both a Ladner-Lynch-like and a Ruzzo-Simon-Tompa-like relativization of this device. In the latter case not only nondeterminism but also access to the push-down store has to be prohibited during the generation of oracle queries. Here again, the Ladner-Lynch approach leads to the Polynomial Hierarchy, while the corresponding Ruzzo-Simon-Tompa hierarchy behaves like the Logarithmic Space Hierarchies, in particular it collapses on its first level down to LOG(CF L), the class of problems reducible to context-free languages.

Thus, we see that in all three cases we have two types of relativizations and corresponding hierarchies, a stronger relativization which leads to the Polynomial Hierarchy and a weaker relativization which collapses on a low level of the corresponding hierarchies.^{2} Unless the considered type of storage is just a logarithmically space-bounded working tape, alternation is related to the stronger hierarchy. In this paper we introduce a new kind of restricted alternation, which we call Empty Alternation. It is characterized by the property that in moments of alternation all tapes or stacks have to be empty except for one working tape of logarithmic size. While “full” alternation usually corresponds to the stronger relativization and the corresponding hierarchy, empty alternation will correspond to the weaker one. Thus, the fact that full alternation and Empty Alternation coincide if there is no additional storage but a logspace tape explains the correspondence of logspace alternation to the Ruzzo-Simon-Tompa relativization. This paper is organized as follows. In section 2 we will give a short overview on complexity classes obtained by bounding depths of alternations by constants or polylogarithmic functions. In section 3 the notion of Empty Alternation is introduced and related to full alternation, yielding new characterizations of wellknown classes like AC^{k}, SAC^{k}, or Θ_{2}^{P} := L^{NP} = P^{NP [log]} = P_{∥}^{NP}.

2 Generally, the former allows opposite relativizations of certain relations, while the

latter often is “positive” in the sense, that the existence of certain relativizations would settle the unrelativized case. For example, there are oracle sets A and B such that LOG^{A} = NLOG^{A} and LOG^{B} ≠ NLOG^{B} if we use the relativization of Ladner and Lynch. Considering the relativization of Ruzzo, Simon, and Tompa, however, the existence of any oracle set C separating LOG^{C} from NLOG^{⟨C⟩} would imply LOG ≠ NLOG !

2 Alternation

We assume the reader to be familiar with the basic notions and results of complexity theory as they are contained in [HoUl79] or [BDG88] and [BDG90]. In particular, LOG, NLOG, P, NP, and PSPACE denote the sets recognizable in (nondeterministic) logarithmic space, (nondeterministic) polynomial time, and polynomial space. Let LOG(X) denote the class of all languages logspace manyone reducible to a class X. By NAuxPDA–TIME(pol) and DAuxPDA–TIME(pol) we denote the classes of languages recognizable by nondeterministic and deterministic auxiliary push-down automata (see [Coo71]) in polynomial time. In addition, we use the STA-notation: ST A(f, g, h) denotes the set of all languages recognizable by alternating Turing machines, which are f(n) space-bounded, g(n) time-bounded, and make no more than h(n) − 1 alternations. Thus, h(n) = 1 covers nondeterministic languages and by convention h(n) = 0 denotes the deterministic case. By AC^{k} (respectively SAC^{k}) we denote the class of languages recognized by circuit families of polynomial size, O(log^{k} n) depth, and of unbounded (respectively semi-unbounded) fan-in (see [Ven87]). In the following we will consider alternating logspace machines, push-down automata (both with and without polynomial time bound), and polynomially timeor space-bounded Turing machines with two-way input and bounded depth of alternation which are always equipped with a logarithmically space-bounded working tape. This, of course, does not change the computational power in the case of polynomially time- or space-bounded Turing machines. But it will be useful when introducing empty alternation. Thus, for X ∈ {LOG, PDA–TIME(pol), PDA, P, PSPACE} and a function g, where we allow the cases that g is a constant or that g is unbounded which will be indicated by the symbol ω, let AΣ_{g}^{s(n)}X (respectively AΠ_{g}^{s(n)}X) denote the set of all languages recognized by alternating X-machines augmented with an s(n) space-bounded working tape, which make g(n) − 1 alternations starting in an existential (respectively universal) state. Characterizations of these classes with s(n) = log n are collected in Table 1. Here, the result ST A(pol, −, pol) = PSPACE in Column 5 is due to the result ST A(f, −, g) ⊆ DSPACE(f(f +g)) for f(n) ≥ log(n) of Borodin (cited according to [CKS81]). Most of the results may be found in [LSL84], [CKS81], [JK89], [Sud78], [Imm88], and [Sze88]. The remaining cases for push-down automata are settled by the following theorems, which we will state without proof. First, the Auxiliary PDA Theorem from [LSL84] can be extended to:

Theorem 1. For s(n) ≥ log(n) and a(n) ≥ 0 computable within space s(n) it holds:

⋃_{c} AΣ_{a(n)}SPACE(2^{cs(n)}) ⊆ AΣ_{1+a(n)}^{s(n)}PDA

Step of without  with pushdown store  with polynomial tape
alter- push-down polynomial  without polynomial without
nation  store  time bound time bound time bound time bound
determ.  L  \begin{matrix}LOG(DCF L) \\ [Sud78] \end{matrix}  P  PSPACE
AΠ_{1}  [Bo et al 88] {P \atop [Coo71]}  co−NP
AΣ_{1}  NL  \begin{matrix}LOG(CF L) \\ [Sud78] \end{matrix}  NP
AΠ_{2}  {[Imm88] \atop [Sze88]}  \begin{matrix}co−NP \\ [JK89] [LSL84] \end{matrix}  Π_{2}^{p}

AΣ_{2} NP [JK89] PSPACE [LSL84]

Σ_{2}^{p}
⋮  ⋮  ⋮
AΠ_{k}  \begin{matrix}Π_{k−1}^{p} \\ [JK89] \end{matrix}  Π_{k}^{p}
AΣ_{k}  \begin{matrix}Σ_{k−1}^{p} \\ [JK89] \end{matrix}  Σ_{k}^{p}  {[Imm88] \atop [Sze88]}
⋮  ⋮  ⋮

AΣ_{log(n)} AC^{1}

Σ_{log(n)}^{p} ⟨Corollary 4⟩

Σ_{log(n)}^{p}
⋮  ⋮  ⋮  ⋮

AΣ_{log^{k}(n)} AC^{k}

Σ_{log^{k}(n)}^{p} ⟨Corollary 4⟩

⟨Corollary 2⟩ Σ_{log^{k}(n)}^{p} [CKS81]
⋮  ⋮  ⋮  ⋮

AΣ_{ω} P [CKS81] PSPACE [JK89] EXPTIME [LSL84] PSPACE [CKS81]

EXPTIME [CKS81]

Table1. Complexity classes of automata with space-bounded tape

As a consequence with AΣ_{a(n)}^{log}PDA ⊆ ⋃_{c} NSPACE(a(n)2^{c log(n)}) [LSL84] we get:

Corollary 2. AΣ_{log^{k}}^{log}PDA = PSPACE

Second, we give the extension of a result in [JK89] to the case of non-constant depth of alternation:

Theorem 3. For s(n) ≥ log(n) and a(n) ≥ 1 computable within space s(n) it holds:

⋃_{c} AΣ_{a(n)}^{s(n)}TIME(2^{cs(n)}) = ⋃_{c} AΣ_{1+a(n)}^{s(n)}PDA–TIME(2^{cs(n)})

Corollary 4. AΣ_{log^{k}}^{log}P OL = AΣ_{log^{k}}^{log}PDA–TIME(pol)

3 Empty Alternation

If we add bounded alternation to logarithmically space-bounded Turing machines, the result is comparatively small: we just get NLOG. The situation changes completely, if we slightly increase the power of the underlying machine model. For example, consider the rather small class DAuxPDA–TIME(pol), which is contained in both SC^{2} and NC^{2}, and hence in P and in POLYLOGSPACE. For DAuxPDA–TIME(pol) the addition of depth-bounded alternation yields already the Polynomial Hierarchy ([JK89],[Bun87]). If we take a closer look to this phenomenon, we see that the underlying machine has now the possibility of pushing polynomially many bits in an existential or universal way onto the push-down store. These bits are then popped, i.e. read one-way, and evaluated again with the help of bounded alternation. This phenomenon and its explanation led us to the concept of empty alternation: we augment machines with several storage types and then add alternation under the restriction that in moments of alternation (during transitions between existential and universal configurations) all auxiliary memories are empty and all transferred information is contained in the state and on a logarithmically space-bounded working tape. In the following, for X ∈ {LOG, PDA–TIME(pol), PDA, P, PSPACE} and a function g, where we again admit the cases that g is a constant or that g is unbounded, let EAΣ_{g}^{log}X denote the set of all languages recognized by logspace Turing machines augmented with storage of type X, which make g(n) − 1 empty alternations. The main results of this chapter are collected in Table 2, which is the “empty” analogue of Table 1.

3.1 Empty Alternation and Push-down Automata

In this section we study the concept of empty alternation for machines equipped only with an additional logspace tape (i.e. for ’unaugmented’ machines), with one push-down store while maintaining a polynomial time bound, and with one pushdown store without any restriction of the running time. Obviously, for unaugmented machines empty alternation coincides with (full) alternation, which yields EAΣ_{g}^{log}LOG = AΣ_{g}^{log}LOG for g ∈ O(1) ∪ {log^{k} n, ω}. Thus, EAΣ_{ω}^{log}LOG = P. The following result shows that this relation holds even for machines augmented with an unrestricted push-down store.

Theorem 5. EAΣ_{ω}^{log}PDA ⊆ P

Proof. According to [Coo71] it can be decided in polynomial time for two configurations K_{1}, K_{2} with empty pushdown store, whether K_{1} |\frac{∗}{M} K_{2} without alternation. If M without loss of generality only stops with empty pushdown store, then for input x it can be calculated recursively for all such configurations in the calculation of M(x), whether there is a partial accepting subtree under that configuration. Because this has to be calculated once for each of the polynomially many configurations, this can be done in polynomial time.

determ.  L  \begin{matrix}LOG(DCF L) \\ [Sud78] \end{matrix}  P  PSPACE
AΠ_{1}  [Bo et al 88]  {P \atop [Coo71]}  co−NP
AΣ_{1}  NL  \begin{matrix}LOG(CF L) \\ [Sud78] \end{matrix}  NP
EAΠ_{2}  [Imm88]
EAΣ_{2}  [Sze88]

⋮ / (EAΠ_{k})

EAΣ_{k}  ⟨Theorem 8⟩

⋮

EAΣ_{log(n)}  AC^{1} ⟨Theorem 9⟩
⋮  ⋮
EAΣ_{log^{k}(n)}  AC^{k} ⟨Theorem 9⟩  Θ_{2}^{p}
⋮  ⋮
EAΣ_{ω} [CKS81] P ⟨Corollary 7⟩ ⟨Corollary 6⟩ ⟨Theorem 10⟩ ⟨Theorem 11⟩

Table2. Complexity classes of automata with logarithmically space-bounded tape and empty alternation

Contrast this with AΣ_{ω}^{log}PDA =EXPTIME in [LSL84]. By Cook’s characterization of P by auxiliary push-down automata in [Coo71] Theorem 5 yields

Corollary 6. EAΣ_{g}^{log}PDA = P, for g ∈ {O(1), log^{k}, ω}.

Another consequence of Theorem 5 follows from P = EAΣ_{ω}^{log}LOG ⊆ EAΣ_{ω}^{log}PDA–TIME(pol):

Corollary 7. EAΣ_{ω}^{log}PDA–TIME(pol) = P

On the other hand using the result of [Bo et al 88], it is easy to see that we have a collapse to LOG(CF L) for constant bounded empty alternation:

Theorem 8. EAΣ_{k}^{log}PDA–TIME(pol) = LOG(CF L), for each k.

In an obvious way it is possible to introduce semi-unbounded empty alternation (compare with [Ven87]) which yields classes named SEAΣ_{g}^{log}X. Now, the nature of polylogarithmically bounded empty alternation of polynomially time-bounded push-down automata is characterized by

Theorem 9. EAΣ_{log^{k} n}^{log}PDA–TIME(pol) = AC^{k}

and SEAΣ_{log^{k} n}^{log}PDA–TIME(pol) = SAC^{k}, for k ≥ 1.

Proof. The inclusions from right to left are obvious. An empty alternating pushdown automaton with h·log(n) space-bounded tape can be simulated by an AC^{k} (respectively SAC^{k}) circuit which calculates with O(|x|^{2h+2}) sub-circuits for every pair of surface-configurations ⟨K_{1}, K_{2}⟩ with empty push-down store whether K_{2} is reachable from K_{1} (K_{1} |\frac{∗}{M} K_{2}) without any alternation. Since this can be done in LOG(CF L) or LOG(co−CF L) it can also be done by a SAC^{1}-circuit because of [Bo et al 88]. Then the circuit recursively calculates in each level j of the log^{k} levels for every surface-configuration K_{i} the bit c_{i,j}, which is 1, if K_{i} has an accepting tree of depth j. For an accepting (rejecting) configuration, this is 1 (0), for an existential configuration it is

c_{i,j} = ⋁_{l}(c_{l,j−1} ∧ ⟨K_{i}, K_{l}⟩) and it is c_{i,j} = ⋀_{l}(c_{l,j−1} ∨ \overline{⟨K_{i}, K_{l}⟩})

for an universal configuration. In case of a semi-unbounded push-down automaton there are only finitely many l’s in a conjunction, so the whole construction results in a SAC^{k} circuit.

This result indicates the comparatively small computational power of Empty Alternation when dealing with polynomially time-bounded auxiliary push-down automata: the addition of a push-down store does not increase the power of a logspace machine as long as the depth of alternation is at least logarithmically growing. But the other direction holds too in the sense that empty alternating push-down automata without two-way input and without logspace working tape generate languages complete for EAΣ_{a(n)}^{log}PDA–TIME(pol) (respectively SEAΣ_{a(n)}^{log}PDA– TIME(pol)), which is shown in [Rei92]. This generalizes the equations NAuxPDA–TIME(pol) = LOG(CFL) and

DAuxPDA–TIME(pol) = LOG(DCFL)

of Sudborough [Sud78]; it may be interpreted in the sense that in EAΣ_{a(n)}^{log}PDA– TIME(pol)-automata a one-way push-down part may be separated from a twoway logspace part. This decomposition is also possible for fully alternating pushdown automata as shown in [Rei89] and [Rei90]. Similar results can be obtained with alternating grammars. For the alternating context free grammars in [Mor89] we have LOG(ACF L_{λ−free}^{left}) = PSPACE according to [CT90], but for the alternating (even λ-free) alternating context free grammars in [Rei89] LOG(CF LΣ_{ω}) =EXPTIME holds. A surprising result of [Rei92] is that alternating linear grammars generate the complete languages corresponding to empty alternation: LOG(LINΣ_{ω}) = P, LOG(LINΣ_{log^{k} n}) = AC^{k} and LOG(LINΣ_{k}) = NL for k ≥ 1.

3.2 Empty Alternation and Turing Tapes

If we consider machines with two or more auxiliary push-down stores, it is easy to see that from the aspect of complexity these are equivalent to Turing tapes. That is why we will consider empty alternation of polynomial time and of polynomial space in this subsection. In the case of polynomial time we will get a characterization of the class Θ_{2}^{p} := L^{NP}. This class was named and characterized by Wagner, who gave several representations of the classes Θ_{k+1}^{p} := L^{Σ_{k}^{p}}. In the following P^{A[log]} refers to classes defined by polynomial time-bounded oracle machines, which are allowed to ask at most O(log(n)) queries and P_{∥}^{A} refers to classes defined by polynomial time-bounded oracle machines, which are allowed to ask a polynomial number of queries in parallel. With the help of Wagner’s characterizations L^{NP} = P^{NP [log]} = P_{∥}^{NP} in [Wag90], we show one of our main results:

Theorem 10. EAΣ_{2}^{log}P = EAΣ_{ω}^{log}P = Θ_{2}^{p}

Proof. EAΣ_{ω}^{log}P ⊆ P_{∥}^{NP}: Let K(x) be the set of those configurations of an EAΣ_{ω}^{log}P -machine M on input x, where the not logarithmic space-bounded tape is empty. Thus |K(x)| is bounded by a polynomial. We consider the language

L_{1} := \{(x, K_{1}, K_{2}) | K_{1}, K_{2} ∈ K(x) and K_{1} |\frac{∗}{M} K_{2} without any alternation \}.

Obviously, we have L_{1} ∈ NP. With one parallel round of queries to L_{1} we can compute the complete reachability relation

R(x) := \{(K_{1}, K_{2}) | K_{1}, K_{2} ∈ K(x) and K_{1} |\frac{∗}{M} K_{2} without any alternation \}.

Then the partial accepting subtrees for all the configurations in K(x) can be computed like in the proof of Theorem 5. We assume w.l.o.g. that the tape, which is not logarithmic space-bounded is empty, if the machine accepts or stops. The simulation accepts, if the start configuration belongs to a partial accepting subtree.

P^{NP [log]} ⊆ EAΣ_{2}^{log}P: Let L ∈ P^{NP [log]} by an oracle machine M with oracle SAT. An EAΣ_{2}^{log}P -machine A simulates M twice: In the first simulation A starts in an existential state and simulates the deterministic steps of M. If M asks the i-th oracle question ’v_{i} ∈ SAT?’, then A guesses the answer and stores it as the i-th bit on the logarithmic space-bounded tape. If the answer ’Yes’ is guessed, then A simulates the NP -machine B for SAT on v_{i} and rejects, if B rejects. If the answer ’No’ is guessed, the verification is postponed to the second phase of alternation. Then A continues the simulation of M. If M accepts, then A alternates into an universal state and starts the second phase of the simulation by simulating again the deterministic steps of M. If M asks the i-th oracle question ’v_{i} ∈ SAT?’, then A looks up the answer from the logarithmic space-bounded tape. If the answer is ’No’, then A simulates universally the co−NP -machine C for UNSAT on v_{i} and rejects, if C rejects. Then A continues the simulation of M. If M accepts, then A accepts.

As we see, a hierarchy defined by bounded empty alternation of polynomially time-bounded machines would collapse on its second level down to Θ_{2}^{P}. (Even totally unbounded empty alternation collapses to alternation depth two!) But this then is precisely the Deterministic Polynomial “Hierarchy” of [JKL89]. This again shows the close relationship of empty alternation to weak relativizations and hierarchies compared to the closeness of full alternation to more powerful ones. Finally, we shortly consider the case of polynomial space. By a result of Borodin (cited in [CKS81]) we have AΣPSPACE_{pol} = PSPACE. While AΣPSPACE_{ω} = EXPTIME, empty alternation does not lead beyond PSPACE:

Theorem 11. EAΣ_{ω}^{log}PSPACE = PSPACE

Proof. It can be decided with polynomial space for two configurations K_{1}, K_{2}, whether K_{1} |\frac{∗}{M} K_{2} without alternation. If M without loss of generality only stops with all auxiliary tapes empty, then for input x it can be calculated recursively for all such configurations in the calculation of M(x), whether there is a partial accepting subtree under that configuration. Because this has to be calculated once for each of the polynomially many configurations, this can be done in polynomial space.

Discussion and Open Questions

We introduced the concept of Empty Alternation as a restriction of the usual ‘full’ alternation and exhibited close connections to questions of how to relativize complexity classes and about the collapses of hierarchies. As a result new representations of many well-known complexity classes have been obtained. Since alternation is a very powerful mechanism, it seems reasonable not only to restrict the concept itself, but also the device it is applied to. In this way, relations between formal languages and complexity could be generalized. This leaves open to investigate these relations with respect to other models of formal language theory. First candidates should here be all types of stack automata, since the relations between their deterministic, nondeterministic, (fully) alternating, and auxiliary versions show a very similar pattern to that of push-down automata. Another interesting question would be to determine both an alternation type and an automaton model which together characterize the NC^{k} classes not as time classes, but directly by the depth of alternation.

Acknowledgment We thank Volker Diekert, Werner Ebinger, Birgit Jenner, Anca Muscholl and Peter Rossmanith for many helpful remarks, Prof. Dr. W. Knödel, who made this joint work possible and an anonymous referee, who helped us to simplify the proof of Theorem 10.

References

[BDG88] J. Balcázar and J. Diáz and J. Gabárro: Structural Complexity Theory I; Springer 1988.

[BDG90] J. Balcázar and J. Diáz and J. Gabárro: Structural Complexity Theory II; Springer 1990.

[Bo et al 88] A.Borodin. S.A. Cook, P.W.Dymond, W.L. Ruzzo, M.Tompa; Two applications of complementation via inductive counting, 3rd Structure in Complexity Theory.

[Bun87] G. Buntrock: On the Robustness of the Polynomial Time Hierarchy, Technische Universität Berlin, Technischer Bericht, Nr.: 87-11,1987.

[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 push-down machines in terms of time bounded computers, Journ. of the ACM 18,1 (1971), 4-18.

[CT90] Z.-Z. Chen, S. Toda: Grammatical Characterizations of P and PSPACE, transactions of the IEICE, Sep. 1990.

[HoUl79] J.E. Hopcroft, J.D. Ullmam: 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.

[JK89] B. Jenner, B. Kirsig: Characterizing the polynomial hierarchy by alternating auxiliary push-down automata. Theoretical Informatics and Applications, 1989, 87-99.

[JKL89] B. Jenner, B. Kirsig, K.-J. Lange: The Logarithmic Alternation Hierarchy Collapses, Information and Computation 80 (1989), 269-288.

[LL76] R. Ladner and N. Lynch: Relativization of questions about log space computability, Math. Systems Theory 10 (1976),19-32.

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

[Lan86] K.-J. Lange: Two Characterizations of the Logarithmic Alternation Hierarchy, Proc. of 12th MFCS 233, LNCS, Springer 1986, 518–526.

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

[Rei89] K. Reinhardt: Hierarchien mit alternierenden Kellerautomaten, alternierenden Grammatiken und finiten Transducern, Diplomarbeit, Universität Stuttgart, 1989.

[Rei90] K. Reinhardt: Hierarchies over the context-free Languages, Proc. of 6th IMYCS, LNCS, 464, Springer 1990, 214-224.

[Rei92] K. Reinhardt. Counting and empty alternating pushdown automata, Proc. of 7th IMYCS, pages 198–207, Smolenice Castle, Tschechoslowakei, 1992.

[RST84] W. Ruzzo and J. Simon and M. Tompa: Space – Bounded hierarchies and probabilistic computations, JCSS 28 (1984), 216-230.

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

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

[Wag90] K. Wagner. Bounded query classes. SIAM Journ. Comput. 19(1990), 833–846.

[Ven87] H. Venkateswaran: Properties that characterize LOGCFL. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, 141-150, New York,May 1987.

This article was processed using the L^{A}TEX macro package with the LLNCS document class.