数理解析研究所講究録 1325 巻 2003 年 191-196

191
Shrinking alternating two-pushdown automata
ドイツ連邦共和国・カッセル大学

F. オットー (Friedrich Otto)

Fachbereich Mathematik/Informatik,Universit\"at Kassel
34109 Kassel, Germany
and早稲田大学・教育学部

守屋悦朗 (Etsuro Moriya) *Department of Mathematics,School of Education
Waseda University,Shinjuku-ku,Tokyo,169-8050,Japan
Abstract
The alternating variant of the shrinking two pushdown automaton of Buntrock and Otto (1998) is introduced. It is shown that the class of languages accePted by these automata is contained in the class ofdeterministic context-sensitive languages, and that it
contains aPSPACE complete language. Hence, the-space reclosure of this class of languages under
ductions coincides with the complexity class PSPACE.
$\log$

1Introduction
In 1986 Dahlhaus and Warmuth published theirpaper [5] on the class GCSL of growing contextlanguages, in which they proved that themembership problem for alanguage from this classis decidable in polynomial time. Here alanguage
is called growing context-sensitive, if it is generated by aphrase-structure grammar containing
only rules that are strictly monotonous, that is,for each rule of the grammar the left-hand side isstrictly shorter than the right-hand side.
Since then this language class has received a
lot of attention. First Buntrock and Lorys haveshown that GCSL is an abstract family of languages in the sense of Ginsburg, Greibach andHopcroft [6], and that it can be characterized byless restricted classes of grammars [1]. Then Buntrock and Otto [2] have shown that GCSL is theclass of languages that are accepted by the s0called shrinking twO-pushdown automata (sTPDA).
These tw0-pushdown automata are shrinking withrespect to aweight function that assigns apositive weight to each pushdown symbol and to eachinternal state, which gives aweight for each configuration by adding up the weights of the contents of the two pushdown stores and of the actual
state. It is required that in each transition of theautomaton the weight of the actual configuration$.\mathit{9}en.sitive$

decreases (see Section 2for the definition). Interestingly the deterministic variant of the sTPDA
characterizes the class of Church-Rosser languages
CRL $[2, 15]$ , which were defined by McNaughton
et al. using length-reducing and confluent stringrewriting systems $[13, 14]$ . In fact McNaughton
asks in [12] whether GCSL should be inserted in
the Chomsky hierarchy as the class of “type oneand-a-half languages.”
For the class CRL further characterizations bydeterministic auto mata have been obtained. MOtivated by the “analysis by reduction” used in linguistics, Jancar, Mraz, Platek, and Vogel havedefined and investigated the restarting automaton RRWW and many variants thereof [8, 9, 10].
An RRWW-automaton has afinite control and a-head with afinite look-ahead working
on alist of symbols. It can perform three kindsof operations: amove-right step, which shifts the-window one position to the right andpossibly changes the actual state, arewrite step,which replaces the contents of thedow by ashorter string, moving the head to theposition immediately to the right of the newly
written string and possibly changing the actual
state, and arestart step, which moves the rcad-head back to the left end of the list, andputs the automaton back into its inital state. Suchan automaton works in cycles, aaid it is requiredthat it performs exactly one rewrite step in eachcycle. It should be stressed that during arewrite
step the length of the list actually decreases.
Apart from 1 thc basic model various restrictedtypes of RRWW-automata have been considered,among them the RWW-automata, various mon0tonous versions and the dete rministic variants. It
has been observed that the class CFL of contextfree languages coincides with the class of languages
that are accepted by the s0-called monotonous$\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{d}/\mathrm{w}\mathrm{r}\mathrm{i}\mathrm{t}\mathrm{e}$$1^{\cdot}\mathrm{e}\mathrm{a}\mathrm{d}/\mathrm{w}\mathrm{r}\mathrm{i}\mathrm{t}$$\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{d}/\mathrm{w}\mathrm{r}\mathrm{i}\mathrm{t}\mathrm{e}- \mathrm{w}\mathrm{i}_{11-}$$/\mathrm{w}\mathrm{r}\mathrm{i}\mathrm{t}\mathrm{e}$192
RWW- and RRWW-automata [10], and that thedeterministic RWW- and RRWW-automata yieldother characterizations of the class CRL $[16, 18]$ .
Interestingly, these characterizations do not carryover to the corresponding nondeterministic classes$[11, 17]$ : each growing context-sensitive language
automaton but
is accepted by some
-automaton that accepts thethere is an
Gladkij language $L_{\mathrm{G}1}:=\{w\# w^{R}\# w|w\in\{a, b\}^{*}\}$ ,which is not growing context-sensitive [3]. Only
by restricting attention to weakly monotonous R-automata we obtain the class GCSL [11].
Thus, while the sDTPDA is as powerful as the-automaton, the sTPDA isdeterministic-auunrestricted
theless powerful than
thereof
whetherquestion
thetolllaton. This raises
is amore powerful variant of the sTPDA that isequivalent in computational power to the unreautomaton
strictedis
As alternation apowerful generalization of
nondeterminism, we define and investigate here
the alternating variant of the shrinking TPDA, theshrinking alternating TPDA (sATPDA). We willshow that the increase in computational power obtained by alternation is not as big as one might expect, as the sATPDA only accepts languages thatare deterministic context-sensitive. This is done
by providing asimulation of an sATPDA by adeterministic linear space-bounded Turing machine.
On the other hand, we will see that asuitably encoded version of the language QBF of quantified
Boolean formulas, which is known to be PSPACE
complete, is accepted by some sATPDA, which
implies that the closure of the class-space reductions yields the complexity
underclass PSPACE. Also we will see that the lanis an abstract family ofguage classadditionis closed under comlanguages that inplementation, and therewith under intersection,and reversal.
unand
As the closure ofclasscomplexity
der -space reductions yields the
NP $[11, 17]$ , this gives some indication that thesATP DA is even more powerful than theautomaton. Unfortunately the exact relationship-automatabetween the sATPDA and theremains open.
$\mathrm{R}(\mathrm{R})\mathrm{W}\mathrm{W}$$\mathrm{R}(\mathrm{R})\mathrm{W}\mathrm{W}$denotesbe afinite alphabet. ThenLet
the set of strings over Iincluding the mpty str ing. The following definition is, andtaken from [2].
$\mathrm{e}$$\Sigma^{+}=\Sigma^{*}\backslash \{\epsilon\}$$\epsilon$

Definition 2.1.
two pushdown automaton (TPDA) is a nondete rministic automaton with two
pushdown stores. For mally, it is defined as a 7tuple $M=(Q, \Sigma, \Gamma, \delta, q_{0},1, F)$ , where$A$

finite set of states,-Iis the finite input alphabet,andis the finite tape alphabet with,$-q_{0}\in Q$ is the initial state,is the bottom marker of the pushdown stores,$-F\subseteq Q$ is the setof accepting states, andis thetransition relation. Heredenotes the set of finite subsets of$-Q$ is the$(\mathrm{R})\mathrm{R}\mathrm{W}$$-\Gamma$$\mathrm{R}(\mathrm{R})\mathrm{W}\mathrm{W}$$-[perp]\in\Gamma\backslash \Sigma$$-\delta:Q\mathrm{x}\Gamma \mathrm{x}\Gammaarrow P_{fin}(Q\cross \mathrm{I} " \mathrm{x}\Gamma^{*})$$\mathrm{R}(\mathrm{R})\mathrm{W}\mathrm{W}$$\log$$\mathcal{L}(\mathrm{s}\mathrm{A}\mathrm{T}\mathrm{P}\mathrm{D}\mathrm{A})$$\mathcal{L}(\mathrm{R}\mathrm{W}\mathrm{W})$$\mathcal{L}(\mathrm{R}\mathrm{R}\mathrm{W}\mathrm{W})$$\log$$\mathrm{R}(\mathrm{R})\mathrm{W}\mathrm{W}-$$\mathrm{R}(\mathrm{R})\mathrm{W}\mathrm{W}$$\mathrm{r}_{\neq}\supset\Sigma$$\Gamma\cap Q=\emptyset$$\mathrm{R}(\mathrm{R})\mathrm{W}\mathrm{W}$$\mathcal{L}(\mathrm{s}\mathrm{A}\mathrm{T}\mathrm{P}\mathrm{D}\mathrm{A})$$\Sigma^{*}$$\Sigma$$P_{fin}(Q\cross \mathrm{I} " \mathrm{x}\Gamma^{*})$$Q\mathrm{x}\Gamma^{*}\cross$$\Gamma^{*}$.

deterministic two pushdown autolnaton
is(DTPDA), if is (partial) function from
.
into

$M$

$a$

$\delta$$\Gamma\cross\Gamma$$Q\cross$$a$$Q\cross\Gamma^{*}\mathrm{x}\Gamma^{*}$

Aconfiguration of aTPDA $M$ is described asis, where $q\in Q$ is the actual state,
the contents of the first pushdown store with thefirst letter of at the bottom and the last letis the contents
ter of at the top, andof the second pushdown store with the last letter of at the bottom and the first letter of at, the corthe top. For an input string. The
responding initial configuration ison
TPDA $M$ induces acomputation relation
the set of configurations (see, e.g., [7]), which is
the reflexive, transitive closure of the single-step. The TPDA $M$ accepts
computation relation$u\in\Gamma^{*}$

$uqv$

$u$

$v\in\Gamma^{*}$$u$$t^{1}$

$v$

$u$ )

$\in\Sigma^{*}$$[perp] q0w[perp]$$\vdash_{M}*$$\vdash_{M}$with its second pushdown store empty, that is, thelanguage $L(M)$ accepted by NI is defined as$L(M):=$ {w$\in \mathrm{C}$’|$[perp] q_{0}w[perp]\vdash_{M}^{*}\alpha q$

for some $q\in F$ and a$\in\Gamma^{*}$}.

In general the TPDA is as powerful as the Turing machine. However, we are only interested inDA’s.
certain restricted
Aweight function for aTPDA $M=(Q,$ , , ,, $F)$ is amapping that assigns apositive
integer as weight to each symbol $a\in Q\cup\Gamma$. This
mapping is extended to amorphism from $(Q\cup$in the obvious way. To simplify thetonotation this morphism will also be denoted by .
$\mathrm{T}\mathrm{P}$2Definitions and notation$\Sigma$$q_{0},$

Here we introduce some basic notation. Then we
give the definition of the shrinking TPDA and its
alternating variant, the sATPDA, and we describe.
aparticular sATPDA for the Gladkij language$L_{\mathrm{G}1}$$\Gamma)^{*}$$[perp]$$\Gamma$$\delta$$g$$(\mathrm{N}, +)$$g$

193 193
Definition 2.2.
called shrinking if there is a weight function for $M$ such that,, $(p, u’, v’)\in 5(\mathrm{q}, u, v)$
for all $q\in Q$ and ,$g(u’pv’)<g(uqv)$. By
we
implies that
denote the corresponding class of shrinking (D),$A(\mathrm{D})\mathrm{T}\mathrm{P}\mathrm{D}\mathrm{A}M\iota s$

$g$

$u$

$v\in\Gamma$$\mathrm{s}(\mathrm{D})\mathrm{T}\mathrm{P}\mathrm{D}\mathrm{A}$TP DAs.

Without loss of generality we can assume for
an sTPDA $M$ that the bottom marker 1can only
occur at the bottom of apushdown store andthat no other symbol can occur at that place, andthat $M$ halts with its right-hand pushdown store
empty and the left-hand one containing at most.
thesTPDA is an sATPDA without universal states, weholds. In tlte follows:
see that GCSL
ing example we present an sATPDA that accepts.
the Gladkij language$\subseteq \mathcal{L}(\mathrm{s}\mathrm{A}\mathrm{T}\mathrm{P}\mathrm{D}\mathrm{A})$$L_{\mathrm{G}1}$

Example 2.5. Let MGi $:=(Q,$ , , , ,be defined by taking $Q:=\{q0, q_{1}, \ldots, q_{6}\}$ , $U.–$, $F:=$, $\Sigma:=\{a, b, \#\}$ ,the following list,, and let be givenof transition steps:$U$$\Sigma$$\Gamma$$\delta$$(\mathit{1}0, [perp], F)$$\Gamma:=\Sigma\cup\{a_{1}, b_{1}, [perp]\}$$\{q_{1}\}$$\{q_{6}\}$$\delta$$\mathrm{t}\mathrm{h}_{1}\mathrm{o}\mathrm{u}\mathrm{g}\mathrm{h}$$b_{1}q_{4}barrow q_{4}$$q_{0}aarrow a_{1}q_{0}$$q_{2}barrow b_{1}q_{2}$$q_{0}barrow b_{1}q_{0}$$q_{2}\#arrow q_{3}$$[perp] q_{4}\#arrow[perp] q_{\dot{\mathrm{D}}}$$qo\#$ $arrow q_{1}\#$$a_{1}q_{3}aarrow q_{3}$$q_{5}aarrow q_{5}$$\mathrm{s}\mathrm{y}\mathrm{m}\mathrm{b}\mathrm{o}\mathrm{l}[perp]$

Proposition 2.3. (a) A language is accepted by
an sTPDA if and only if it is a growing context-sensitive language [2].
(b) A language is accepted by an sDTPDA if andonly if it is a Church-Rosser language [2,15].
Finally, we are prepared to introduce the main
topic of this note, the alternating shrinking TPDA.

Definition 2.4. An alternating TPDA $M=(Q$ ,, $F)$ is TP DA
,
, , ,
which
a
subsetof the set of states is desigfor
nated as the set of universal states. The states inare accordingly called exthe difference set
istential states. An alternating TPDA (ATPDA) iscalled shrinking, if the underlying TPDA is shrinking. By sATPDA $u1e$ denote the class of all shinking ATPDAs.
$U$$\Sigma$$\Gamma$$\delta$$q_{0},$$[perp]$$(Q, \Sigma, \Gamma, \delta, q_{0}, [perp], F)$

$a$

$U$

$Q$

$Q\backslash U$$q_{1}\#arrow\# q_{2}$$b_{1}q_{3}barrow q_{3}$$q_{5}barrow q_{6}$$q_{1}\#arrow q_{4}$$\neq q_{3}[perp]arrow\neq q_{6}$$q_{5}[perp]arrow q_{6}$$q_{2}aarrow a_{1}q_{2}$$a_{1}q_{4}aarrow q_{4}$Further, we define aweight function g : $Q\cup$by taking$\Gammaarrow \mathrm{N}_{+}$$g(a):=g(b):=2$ ,$g(a_{1}):=g(b_{1}):=1$ ,$g(\#):=g([perp]):=1$ ,$g(q_{i}):=7-i(i=0, \ldots, 6)$ .

is
It is easily verified that the ATPDA
shrinking with respect to this weight function. It.
remains to verify thatbe agiven input. If . containsLetless than two or more than two occurrences of thewill notsymbol , then it is easily seen that
accept this input. Thus, we may assume that the
input is of the form $x=u\#\tau’\# w$ fot so me strings. Hence, the initial configuration, ,. Starting fr om this configurationis,will reach the configuration
denotes the image of under the natuwhere. The
ral isomorphism from $\{a, b\}$ ’onto. The
is the only universal state ofstate
exactly two illlconfiguration
mediate successor configurations:$\Lambda f_{\mathrm{G}1}$$L(\Lambda \mathrm{f}\mathrm{G}1)$$=L_{\mathrm{G}1}1_{1\mathrm{O}}1\mathrm{d}\mathrm{s}$$x\in\Sigma^{*}$

$x$

$\#$

$u$

$\lambda \mathrm{f}\mathrm{c}\mathrm{l}$$ta\subset-\{a, b\}^{*}$$v$$[perp] q_{0}u\neq v\# w[perp]$$[perp] u_{1}q_{1}\# v\# w[perp]$$M_{G1}$

We need to define the language accepted by an
PDA. For doing so we introduce the notion of

asuccessful configuration of an ATPDA.
$v\in\Gamma^{*}$$\{a_{1}, b_{1}\}^{*}$$M_{\mathrm{G}1}$$q_{1}$

Let $M=(Q, U, \Sigma, \Gamma, \delta, q_{0},1, F)$ be an ATPDA,
and let $uqv$ be aconfiguration of $M$ , where $q\in Q$. If
and $q\in F$ , then $uqv$ isand ,asuccessful configuration. If is an existential
state, and there is atransition $uqv\vdash_{M}xpy$ suchis successful, then also $uqv$ is asuccessfulthatconfiguration. Finally, assume that is auniversal
be the,,,state, and let
finitely many configurations that $M$ can reach inasingle step from $uqv$ . Then $uqv$ is asuccessful
configuration, if all the configurations xiptyu$i\leq k$ , are successful.
Now the language $L(M)$accepted by the ATPDA $M$ is defined as follows:
$u$

$u$

$u_{1}$$[perp] u_{1}q_{1}\# v\neq w[perp] \mathrm{h}\mathrm{a}\mathrm{s}$$v=\epsilon$

and$(\mathrm{a})[perp] u_{1}\# q_{2}v\# w[perp]$$q$$xp\tau/$$q$$x_{2’}p_{2}y_{2}$$x_{1}p_{1}y_{1}$$\ldots$$x_{k}p_{k}y_{k}$$1\leq$$L(M):=$ {w$\in\Sigma$’|$[perp] q_{0}w[perp] \mathrm{i}\mathrm{s}$asuccessful

configuration of M}.

of
We are interested in the classlanguages that are accepted by sATPDAs. As each$\mathcal{L}(\mathrm{s}\mathrm{A}\mathrm{T}\mathrm{P}\mathrm{D}\mathrm{A})$(b)$[perp] u_{1}q_{41’}\neq w[perp]$

Starting from (a) an accepting configuration isreached if and only if $w=v^{R}$ , and starting from(b) an accepting configuration is reached if andonly if $u=v^{R}$ . Thus, these two computations
lead both to acceptance if and only if $u=v^{R}=w$
does indeed accept the lanholds. Hence,$M_{\mathrm{G}1}$

guage$L\mathrm{c}1$.

As the language$\square$$L_{\mathrm{G}1}$

is not growing context-

sensitive, we obtain the following proper inclusion,
which shows that the sATPDA is strictly more
powerful than the sTPDA.
Corollary 2.6. GCSL.

$\underline{\mathrm{c}_{-}}\mathcal{L}(\mathrm{s}\mathrm{A}\mathrm{T}\mathrm{P}\mathrm{D}\mathrm{A})$194
3An upper boundHere we establish an upper bound for the computational power of the sATPDA by showing thefollowing result.

, thatTheorem 3.1. (sAT DA)
sATPDA, thenis, if a language is accepted by
it is deterministic context-sensitive.
$\mathcal{L}$$\mathrm{P}$. Aquantified Boolean for, andrnula is an expression of the form$(F_{1}\wedge F_{2})$$\subseteq \mathrm{D}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(n)$$\grave{s}ome$

Proof. Let $M=(Q, U, \Sigma, \Gamma, \delta, q_{0},1, F)$ be an
sATPDA with weight function , and let cz $:=$
utax $\{g(a)|a\in Q\cup\Gamma\}$ . Obviously, we can restrict
our attention to non-empty inputs. For each in, each computation of $M$ on input
put
contains at most$g$$w\in\Sigma^{+}$$w$$g([perp] q_{0}w[perp])\leq\alpha\cdot(|w|+3)\leq 4\alpha\cdot|w|$$(\neg\Gamma_{1}\sqrt)$$Q_{1}v_{1}Q_{2}v_{2}\cdots Q_{k}v_{k}F$,

is the existential quantifier or thewhere each
universal quantifier , and $F$ is aBoolean formula, .
containing (at most) the variables ,Under the standard logical interpretation eachquantified Boolean formula yields the truth value
true or false. By QBF we denote the languageof all quantified Boolean formulas that yield tlle
truth value true.
Let $\Sigma:=\Sigma_{0}\cup\{x, a\}$ , and let : $Varrow\{x, a\}^{*}$. For
denote the unary encoding,
denotes the string fromathat is obtained from at by replacing each variable. The
occurrence by its unary encoding
language LQBF is then defined as$\exists$$Q_{i}$$\forall$$v_{1}$$\mathrm{c}$$v_{i}\vdash\Rightarrow x^{2}a^{i}(i\geq 0)$$\in(V\cup\Sigma_{0})^{*}$$\Sigma^{*}$$c(\alpha)$$c(v_{f})$$v_{i}$

many steps. Thus, the behaviour of the sATPDA$M$ on an input $w\in\Sigma^{+}$ can be described byacomputation tree of depth at most , where$n:=4\alpha\cdot|w|$ . As in the proof of Theorem 3.2 of[4] adeterministic Turing machine can traverse
this computation tree calculating the result of $M$ ’scomputation on input . At any point in its computation needs to store only the actual node of
the computation tree of $M$ it is currently visiting
and the position of this node in the computation
tree. As each configuration that $M$ can reach duris linearly bounded ining its computation on
depth of the computathe
andaslengthofto,thenumber , it follows
bythebounded
tree
is
tion
away that it is
such
in
be
realizedcanthatlanguageHence,
thespace-bounded.
linearcontext-sensitive.
is indeed deterministic
Thus, while alternation increases the expressive power of the pushdown automaton from theclass CFL to the complexity class[4], it increases the power of the sTPDA, which isstricly more powerful than the pushdown automaton, just to deterministic linear space.

$v_{k}$$\ldots$$L_{\mathrm{Q}\mathrm{B}\mathrm{F}}:=\{c(\alpha)$|$\alpha\in \mathrm{Q}\mathrm{B}\mathrm{F}\}$

.

$n$

$T$

$w$

$T$

$w$

$n$

$T$

$L(NI)\square$$\bigcup_{c>0}\mathrm{D}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(c^{n})$Example 4.1. The formulabelongs to the set QBF,
as is easily verified. Hence, the language LQBF
contains the string$\forall v_{1}\exists v_{2}\forall v_{3}(v_{1}\vee\neg v_{2})\wedge$$(v_{2}\vee(\neg v_{1}\wedge v_{3})\vee\neg v_{3})$$\forall x^{2}a\exists x^{2}a^{2}\forall x^{2}a^{3}(x^{2}a\vee\neg x^{2}a^{2})$$\wedge(x^{2}a^{2}\vee(\neg x^{2}a\wedge x^{2}a^{3})\vee\neg x^{2}a^{3})$From the literature on complexity theory it isis PSPACEthe language
well-known$\mathrm{t}1_{1}\mathrm{a}\mathrm{t}$$\Sigma_{0}:=\{\exists,\forall, \neg, \wedge, \vee, (, )\}$$\neg$$\wedge$$\vee \mathrm{d}\mathrm{e}\mathrm{n}\mathrm{o}\mathrm{t}\mathrm{e}\mathrm{s}$$V$$F_{2}$$\log$

Theorem 4.2. There is an sATPDA that accepts.
the language$L_{\mathrm{Q}\mathrm{B}\mathrm{F}}$Proof. We describe an sATPDA $M$ for the lau. The sATPDA $M$ will work in several
guage
phases as follows:
1. It checks that the input is of the form
$L_{\mathrm{Q}\mathrm{B}\mathrm{F}}$$Q_{1}c(v_{i_{1}})\cdots Q_{k}c(v_{i_{h}})c(F)$,and $F\in(V\cup\Sigma 0)^{*}$ .
,... ’
2. It verifies that all the variables
are pairwise distinct.
3. It checks that the string $F$ only contains occurrences of these variables.
4. It guesses truth values for all variable occur$v_{i_{1}}$,... ’$v_{i_{k}}\in V$$v_{i_{1}}$Next we show that the sATPDA accepts the PSPACE-complete language LQBF, thus providing
alower bound for its computational power.
Let $V:_{-}^{--}\{v_{i}|i\geq 0\}$ be aset of Boolean vari, whereables, alld let
conjunction,
denotes
negation,
symbolfor
theisdisjunction. The set of Boolean forandis defined inductively as usual: formulas overandeach $v\in V$ , is aBoolean formula, and if,
are Boolean formulas, then so are$v$$L_{\mathrm{Q}\mathrm{B}\mathrm{F}}$-space reductions, see, e.g., [20].
Here we establish the following result about thislanguage.

complete under

where

4Alower bound.

$F_{1}$$(F_{1}\vee F_{2})$$v_{\iota_{k}}$rences.

5. For each $j\in\{1, \ldots, k\}$ , it verifies that forthe sameeach occurrence of the variablevalue has been chosen.
6. It checks whether is acorrect Boolean for$v_{i_{j}}$$F$mula while evaluating $F$ under the chosen
assignment

195
Below we describe in short how the sATPDA
does all this. We consider each of the above.
phases in, for which
Then $M$ enters auniversal state
there are exactly two alternatives of how to Proceed, one for each of the last two phases.

Phase 1. This amounts to checking that thegiven input belongs to the regular language, which can simply
be done by moving the input from the right-hand
pushdown store onto the left-hand pushdown store
and back again, using two disjoint copies of the
input alphabet in order to realize this computation in aweight-decreasing manner. If the given
input does not belong to this regular language,
is ofthen $M$ rejects it, otherwise the input
for some string
tlle form

Phase 5. Using the same strategy as in Phase 3
it is checked that each variable occurrence in thestring $F$ has been assigned the sanle truth value
as the corresponding variable in the quantifier prefix. This phase accepts only if the assignment iscorrect.

$\mathrm{J}/I$$\mathrm{t}\mathrm{u}\mathrm{r}\mathrm{n}$$(\{\exists, \forall\}\cdot$$x^{2}\cdot a^{*})^{+}\cdot(\{\neg, \wedge, \vee, (, )\}\cup x^{2}\cdot a^{*})^{+}$$w$$Q_{1}x^{2}a^{i_{1}}\cdots Q_{k}x^{2}a^{i_{k}}F$$F\in$$(\{3, \wedge, \vee, (, )\}\cup x^{2}\cdot a^{*})^{+}$. In the latter caseenters auniversal state q\^u,, for which there areexactly three alternatives of how to proceed, one
for each of the Phases 2to 4.
$M$

Phase 2. Universally $M$ chooses two indicesand satisfying $1\leq r<s\leq k$ , and it compares. to . If andcoincide, then $M$ halts andrejects, otherwise it accepts.
As we use universal states, we can guaranteethat all different choices of and are considered.
Thus, this phase does not lead to rejection only
if all tlie variables in the quantifier prefix of thegiven input are pairwise distinct.
$r$

$s$

$i,$

$i_{s}$$i_{s}$$i_{r}$$r$$s$$q_{U_{2}}$Phase 6. Finally $M$ verifies that the string $F$ isin fact (the encoding of) aBoolean formula in thesense of the above definition, and that it evaluates
to the truth value true under the actual assignment chosen in Phase 4. For doing so the quantifier prefix is deleted, and in the string $F$ eachis simply rcvariable occurrence of the form
placed by the truth value . Then by simulating
adeterministic pushdown automaton $M$ checks
whether $F$ is of the correct syntactical form, andit evaluates $F$ under the given replacement of variables by truth values. It accepts if aacd only if $F$ isof the correct syntactical forlll and if it evaluates
to $tme$ .
From this description we see that the sATPDA$M$ satisfies, which proves the$xtb^{\mathrm{J}}$$t$$L(M)=L\mathrm{Q}\mathrm{B}\mathrm{F}$$\mathrm{t}11\mathrm{G}-\square$

orem.

Phase 3. Universally $M$ chooses avariable ocwithin the string $F$ , and then it
currence
existentially chooses an index $r\in\{1, \ldots, k\}$ . It
now compares the numbers and . If and do
not coincide, then $M$ halts and rejects, otherwise
it accepts.
As we use universal states, we can guaranteethat all different choices of variable occurrences
in $F$ are considered. Thus, this phase leads toacceptance only if all variables occurring in $F$ arelisted in the quantifier prefix.

Together with Theorem 3.1 this theorem yields
the following.

Phase 4. For each variable in the quantifier prefix
atruth value , $1\leq j\leq k$ , is chosen, where thischoice is realized using auniversal state if the corresponding variable is universally quantified, andotherwise it is realized using an existential state.
Next also each variable occurrence in the string$F$
is associated with atruth value. This is doneby pushing $F$ from the right-hand pushdown store
onto the left-hand pushdown store and back, whilebyreplacing each variable occurrence$t\in\{0,1\}$
1
in
Phase
.
As
for some truth value
areusedalphabet
input
copiesoftheadditionalin order to realize this computation in aweightdecreasing manner.

5Closure properties$x^{2}a^{j}$$i_{r}$$j$$i_{r}$

Corollary 4.3. LOG .

$\mathrm{C}(\mathrm{s}\mathrm{A}\mathrm{T}\mathrm{P}\mathrm{D}\mathrm{A})$$=\mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}$.

$j$Recall from $[2, 5]$ that LOG CFL
holds, that is, with respect,
LOG-space reductions the uso
to the closure underof alternation increases the power of the sTPDA
from the cornplexity class LOG CFL to the c.omplexity class PSPACE.

$=\mathrm{L}\mathrm{O}\mathrm{G}\cdot \mathrm{G}\mathrm{C}\mathrm{S}\mathrm{L}=$$\cdot \mathcal{L}(\mathrm{s}\mathrm{T}\mathrm{P}\mathrm{D}\mathrm{A})$$\subseteq \mathrm{P}$$\log$$t_{j}$$x^{2}a^{j}$$xtb^{7}$Finally we turn to the closure properties of l.he
language class (sATP DA).
$\mathcal{L}$isTheorem 5.1. The language classcornplernenintersection,
andunion,
underclosedtation, reversal, product and iteration, -free rnorphisms, and inverse morphisms.
$\mathrm{C}(\mathrm{s}\mathrm{A}\mathrm{T}\mathrm{P}\mathrm{D}\mathrm{A})$$\epsilon$

All these closure properties can be shown byconstructing corresponding sATPDAs [19]. Howis not closed under arbitraryever,morphisms, as already its subclass GCSL is abasis
for the recursively enumerable languages [3]$\mathcal{L}(\mathrm{s}\mathrm{A}\mathrm{T}\mathrm{P}\mathrm{D}\mathrm{A})$196
It remains the question of whether the lancan be characterized as
guage classthe closure of the class GCSL under certain language-theoretical operations. The class GCSL is
not closed under intersection or complementation[3], but as it is contained in the complexity class ,) of GCSL,
wc see that the Boolean closurethat is, the closure of GCSL under intersection,
union and complementation, is still contained in P.
-space reunderThus, the closure ofductions is contained in , and sowould imply by Corollary 4.3 thatancl PSPACE coincide.
$\mathcal{L}(\mathrm{s}\mathrm{A}\mathrm{T}\mathrm{P}\mathrm{D}\mathrm{A})$$\mathrm{P}$$\mathrm{B}\{\mathrm{G}\mathrm{C}\mathrm{S}\mathrm{L}$$\log$$B(\mathrm{G}\mathrm{C}\mathrm{S}\mathrm{L})$$\mathrm{P}$$\mathcal{B}(\mathrm{G}\mathrm{C}\mathrm{S}\mathrm{L})$$=$$\mathrm{P}$$\mathrm{L}’(\mathrm{s}\mathrm{A}\mathrm{T}\mathrm{P}\mathrm{D}\mathrm{A})$$|$6Concluding remarks[7] J.E. Hopcroft, J.D. Ullman. Introduction to Autornata Theory, Languages, and Computation
Addison-Wesley, Reading, M.A., 1979.
[8] P. Jancar, F. Mraz, III. Plitek, J. Vogel. Restal 1ing automata.
In H. Reichel, ed., Fundamentals of Computation Theory, Proc. FCT’95,
Lect. Notes Comput. Sci. 965, pp. 283-292.
Springer, Berlin, 1995.
[9] P. Jancar, F. Mraz, M. Platek, J. Vogel. On
restarting automata with rewriting. In G. Paun,
A. Salomaa, eds., New Trends in Formal Languages, Lect. Notes Comput. Sci. 1218, pp. 119136. Springer, Berlin, 1997.
10] P. Jancar, F. Mraz, M. Platek, J. Vogel. On
monotonic automata with arestart operation.
J. Autom. Lang. Comb., 4:287-311, 1999.
[11] T. Jurdzinski, K. Loryi, G. Niemann, F. 0 , , .
Some results on RRW- and RRWW-anion Otto.
and their relationship to the class of growing context-sensitive languages.
Schriften Kassel 14/01, Universitat Kassel, December 2001.
[12] R. McNaughton. An insertion into the Chornsky hierarchy? In J. Karhuzniki, H. Maurer, , G.
, Jewels are Forever,, 1)1).
PKun, G. Rozenberg,
204-212. Springer, Berlin, 1999.
[13] R. McNaughton, P. Narendran, F. Otto. ChurcbRosser Thue systems and formal languages.
J. A CM, 35:324-344, 1988.
$($

In [17] it has been observed that there is an RRWW-complete language
al 比 omaton that accepts the. Further, this result has been improved in[11] by showing that there is already an RV 珂珂珂accepting avariant of this language.
mmary, we obtain the following sequence ofIn
denotes the deterinclusions, where-automata:lllinistic.
$\mathrm{N}\mathrm{P}$$L_{3\mathrm{S}\mathrm{A}\mathrm{T}}$$\mathrm{a}\mathrm{u}\mathrm{t},\mathrm{O}\mathrm{l}\mathrm{n}\mathrm{a}\mathrm{t}\mathrm{o}\mathrm{n}$$\mathrm{s}\mathrm{u}$$\mathrm{D}\mathrm{R}(\mathrm{R})\mathrm{W}\mathrm{W}$$\mathrm{R}(\mathrm{R})\mathrm{W}\mathrm{W}$CRL$=\mathcal{L}(\mathrm{s}\mathrm{D}\mathrm{T}\mathrm{P}\mathrm{D}\mathrm{A})$$=$$\subseteq$$\subseteq$

GCSL$\mathrm{P}$PSPACE$=$$\mathcal{L}(\mathrm{D}\mathrm{R}(\mathrm{R})\mathrm{W}\mathrm{W})$$\subset$$\subseteq$$=\mathrm{L}\mathrm{O}\mathrm{C}$LOG CFL
NP.

$\subset$$=$$\mathcal{L}(\mathrm{s}\mathrm{T}\mathrm{P}\mathrm{D}\mathrm{A})$$\llcorner \mathrm{O}\mathrm{G}$$=\mathrm{L}\mathrm{O}\mathrm{C}$GCSL$\cdot \mathrm{R}(\mathrm{R})\mathrm{W}\mathrm{W}$

$($

$0$

$\mathrm{h}’\mathrm{I}\mathrm{a}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{m}\mathrm{a}1\mathrm{i}\mathrm{s}\mathrm{d}_{1}\mathrm{e}$$\mathrm{e}\mathrm{d}\mathrm{s}.$$\mathcal{L}(\mathrm{s}\mathrm{A}\mathrm{T}\mathrm{P}\mathrm{D}\mathrm{A})$It remains to compare (sATP DA) to. They all contain the classand toGCSL properly, and they are all contained in CSL,
what is the exact relationship between them?
$\mathcal{L}$$\mathcal{L}(\mathrm{R}\mathrm{W}\mathrm{W})$$\mathcal{L}(\mathrm{R}\mathrm{R}\mathrm{W}\mathrm{W})$$])n\mathrm{t}$[14] P. Narendran. Church-Rosser and Related Thue
dissertation, Rensselaer PolytccbSystems.
nic Institute, Troy, New York, 1984.
[15] G. Niemann, F. Otto. The Church-Rosser languages are the deterministic variants 1’1 tlle
growing context-sensitive languages. In . Nivat, ed., Proc. FoSSaCS’98, Lect. Notes Cornput. Sci. 1378, pp. 243-257. Springer, Berlin,$\mathrm{P}\mathrm{h}\mathrm{D}$$\mathrm{h}1$

References[1] G. Buntrock, K. LOry4. On growing contextscnsitive languages. In W. Kuich, ed., Proc.
of 19th ICALP, Lect. Notes Comput. Sci. 623,
pp. 77-88. Springer, Berlin, 1992.
[2] G Buntrock, F. Otto. Growing context-sensitive
languages and Church-Rosser languages. In-

form. Comput, 141:1-36, 1998.

Wachsende kontext-sensitive[3] G. Buntrock.
Habilitationsschrift, Fakult\"at fiir
Sprachen.
Universitat
Mathematik und Informatik,
Wiirzburg, July 1996.
[4] A.K. Chandra, D.C. Kozen, L.J. Stockmeyer. Alternation. J. ACM, 28:114-133, 1981.
[5] E. Dahlhaus, M. Warmuth. Membership for
growing context-sensitive grammars is polyn0mial. J. Comput Sys. Sci., 33:456-472, 1986.
[6] S. Ginsburg, S. Greibach, J.E. Hopcroft. Studies
in Abstract Families of Languages. Memoirs of
the AMS, vol. 87. AMS, 1969.

1998.
,[16] G. Niemann, F. Otto. Restarting auton
ofrepresentations
andlanguages,
Church-Rosser,. languages. In G. Rozenberg, W.
, Proc. $DLT$ 1999, pp. 103-114. World Scientific, Singapore, 2000.
the power of RRWW[17] G. Niemann, F. Otto.
,
automata. In M. Ito, G. Paun, S. Yu,, . 341Words, Semigroups, and$\mathrm{l}\mathrm{a}\mathrm{t},\mathrm{a}$’$\Gamma 1\mathrm{l}\mathrm{O}\mathrm{l}\mathrm{n}\mathrm{a}\mathrm{s}$$\mathrm{r}.\mathrm{e}$$\mathrm{e}\mathrm{d}\mathrm{s}.$$\mathrm{O}_{11}$$\mathrm{e}\mathrm{d}\mathrm{s}.$$I\mathrm{h}_{7}\iota sdu\mathrm{c}tions$$\mathrm{p}\mathrm{p}$355. World Scientific, Singapore, 2001.
[18] G. Niemann, F. Otto. Further results on restart-, Words,. World ScieuLanguages, andtific, Singapore, to appear.
[19] F. Otto, E. Moriya. Shrinking alternating twOpushdown automata Mathematische Schriften
Kassel 12/01, Universit\"at Kassel, August 2001.
[20] R. Reischuk. Komplexitdtstheorie. Teubner,
Stuttgart, 1999
ing automata. In M. Ito, T. Imaoka,$Comb^{l}inatoncs$ $III$$\mathrm{e}\mathrm{d}\mathrm{s}.$