数理解析研究所講究録
第 871 巻 1994 年 1-7

1
A Hierarchy Result of Cooperating Systems of Two-Way
Counter Machines

王躍 (Yue Wang) 井上克司 (Katsushi Inoue) 高浪五男 (Itsuo Takanami)
Department of Competer Science and Systemtt Engineering,

Faculty of Engineering, Yamagrchi University,the, 755 Japan

1

Introduction

Cooperating systems of counter machines were introduced in [3] as language acceptors, which may be considered
as a model of paraUel computation. InformaUy, a cooperating system of counter machines consists of (one-)counter
$k$

$k$

, and a read-only input tape where these counter machines independently work step bymachines $CM_{1},$ $CM_{2},$step. Each step is assumed to require exactly one time for its completion. Those counter machines whose input heads
scan the same cell of the input tape can communicate with each other, that is, every counter machine is aUowed to know
the internal states and the signs (positive or zero) of counters of other counter machines on the cell it is scanning at the
moment. The input tape holds a string of input symbols delimited by left and right endmarkers. The system starts witheach $CM$; on the left endmarker in its initial state with the counter empty, and accepts the input tape if eachentersan accepting state and halts when reading the right endmarker. In [3], several basic properties of cooperating systemsof one-way counter machines were investigated, and some relations between cooperating systems of counter machines andmulticounter machines regarding the polynomial time (space) complexity were established.
In this paper we show that for languages over a one-letter alphabet, cooperating systems of $k+1$ two-way countermachines are more powerful than cooperating systems of two-way counter machines, with space bound . The method
used here is based on a transformational method used in [1]. An open problem in [1] is whether for languages over a
one-letter alphabet, two-way nondeterministic $(k+1)$ -counter machines are more powerful than two-way nondeterministick-counter machines, with space bound. (For the deterministic case, the answer is positive [1].) Our result can also be
considered as an answer for another version of this problem.
$\cdots,$$CM_{k}$$CM_{i}$

$k$

$n$

$n$

2

Preliminaries

Let $M$ be a cooperating system of counter machines (see [3] for the formal definition of cooperating system ofcounter machines), and let $L(n)$ be a function
to $N$ , whereis the set of natural numbers. $M$ is said to be$L(n)$ -space bounded if for each input
accepted by $M$ , there is a computation of $M$ on in which each counter requires
space not exceeding $L(|w|)$ .
We denote a cooperating system of two-way deterministic (nondeterministic) counter machines by CS-DCM $(k)$$(CS- NCM(k))$ , and for each $M\in\{CS- DCM(k), CS- NCM(k)\}$ , if $M$ is $L(n)$ -space bounded, we denote it by M[Space(L(n))].
Let[ $CS$ -DCM(k)[Space(n)]] (-NCM(k)[Space(n)]]) denote the class of languages over the alphabet
accepted by CS-DCM(k)[Space(n)]’s (CS-NCM(k)[Space(n)]’s), for each $k\geq 1$ . Let $DSPACE_{\Sigma}(f(n))(NSPACE_{\Sigma}(f(n)))$accepted by deterministic (nondeterminsitic) Turing machines withdenote the class of languages over the alphabet
space bound $f(n)$ .
-NCM(k)[SpaceIn the following we only consider languages $L\subseteq\{0^{2}" |n\geq 1\}$ . Let [$CS$-DCM(k)[Space(n)]] ($(n)]])$ be the class of all languages
such that$bom\mathcal{N}$$\mathcal{N}$

$w$

$w$

$k$

$f_{\Sigma}JCS$$f_{\Sigma}$$\Sigma$$\Sigma$$\tilde{\ell}$$\tilde{f}[CS$$L$[$LEf_{\{0\}}$ $CS$and

$L\subseteq\{0^{2^{n}}|n\geq 1\}$. Let

-DCM(k)[Space(n)]]$DS\overline{PA}CE(\log n)(NS\overline{PA}CE(\log n))$$(L\in f_{\{0\}}[CS- NCM(k)[Space(n)||)$

be the dass of all languages$L$such that$L\in DSPACE_{\{0\}}(\log n)(L\in NSPACE_{\{0\}}(\log n))$and$L\subseteq\{0^{2^{n}}|n\geq 1\}$.

For each $L\subseteq\{0^{2}|n\geq 1\}$ and $j\geq 1$ , let$T_{j}(L)=\{0^{2^{j\cdot n}}|n\geq 1\ 0^{2’}\in L\}$.

In all the proofS there is no difrerence at all between the deterministic and the nondeterministic cases. Therefore
we will always consider only the deterministic case.

2
3

ResultLemuna 1. For each $k\geq 1$ ,(1) $\tilde{\ell}[CS- DCM(k)[Space(n)]]\subsetneq DS\overline{PA}CE(\log n)$, and(2) $\tilde{f}[CS- NCM(k)[Space(n)]]\subsetneq NS\overline{PA}CE(\log n)$ .

au$k\geq 1,\tilde{x}[DHA(k)]5^{DS\overline{PA}CE(\log n)}$ and
NSPACEis accepted by a two-way, where $\tilde{f}[DHA(k)](\tilde{f}[NHA(k)])$ is the dass of au languages such that
deterministic (nondeterministic) k-head finite automaton. On the other hand, one can easily show that for each $k\geq 1$ ,$\tilde{f}[CS- DCM(k)[Space(n)]]\subseteq\tilde{f}[DHA(2k+1)]$ and $\tilde{f}[CS- NCM(k)[Space(n)]]\subseteq\tilde{f}[NIIA(2k+1)]$. From those facts, the lemma
follows.

Proof: It was shown in [1] (Lemma 1) that for$\tilde{f}[NHA(k)]\subsetneq$$L\subseteq\{0^{2^{n}}|n\geq 1\}$$L$$(\log n)$$O$

Lemma 2.

For each $L\in DS\overline{PA}CE(\log n)(NS\overline{PA}CE(\log n))$ , there exists an integer $j\geq 1$ such that

$DCM(2)[Space(n)]](\tilde{f}[CS- NCM(2)[Space(n)||)$$T_{f}(L)\in\tilde{\ell}[CS-$.

be any language in DSPACE(log ), and $M$
Proof: The proof is very similar to that of Lemma 2 in [1]. Let
be a deterministic Turing machine accepting within space bound $\log n$ . Let $M’$ be the following modification of $M$ :(1) $M’$ writes $bi(n)$ on its working tape, where is the length of input tape and bi: the set of natural numbers,
is the binary notation of .
, be the bijective mapping defined by:(2) During the rest of the computation $M’$ never uses its input tape“again. $M’$ simulates $M$ and during thissimulation its working tape is divided into 3 tracks. On the first track $M’$ stores $bi(n)$ , on the second track the positionof the input head of $M$ in binary notation and on the third track the inscription of the worktape of $M$ .
Furthmore we can define $M’$ in such a way that it has only two worktape symbols. There exists some $j\geq 1$ such$M’$cells on its worktape.
uses for every computation at mostthat
accepting $T_{j}(L)$ . $M”$ first tests whether the input tape is of the
We now define a deterministic CS-DCM(2)$n\geq 1$ , using its two counters. If this is the case, thensimulates the action of $M’$ on the input tape
.
form
$M’$
is divided by the head position into two parts as described in Fig. 1, and $M”$ stores this during
The working tape of) as described in Fig.
the simulation on its input tape by using the input heads of its two counter machines (and2 (with the counters empty).
$L$

$n$

$L$

$n$

$bi(n)=\varphi\Leftrightarrow 1\varphi$$\mathcal{N}arrow\{0,1\}$$n$$j\cdot\log_{2}n$$M^{n}$$M^{n}$$0^{2^{j\cdot n}},$$0^{2^{n}}$$CM_{2}$$CM_{1_{-}}$

$f$

$u$

$v$

\dagger (working head)Fig. 1. The working tape of At’.

Fig. 2. The input tape of$M^{u}$, where un: $\{0,1\}arrow N$ is the inverse mapping of bi.

In order to simulate one step of $M’,$ $CM_{1}(CM_{2})$ has to divide or multiply the number un $(v^{R})(un(u))$ by two, andhas to add $+1$ or $-1$ to the number un $(v^{R})(un(u))$ (where “un” is the inverse mapping of “bi”). Moreover,andhave to communicate with each other. All of this can be easily done with the help of their empty counters.
sets the position of the input head of
to un
In order to initialize this simulation,$CM_{1}$$CM_{2}$$M^{n}$$CM_{1}$$( bi(2^{\mathfrak{n}})^{R})=un(00\cdots 0)\bigvee_{n}=2^{n}$to the right endmarker $. This can be done using two counters.
and then moves the input head of
if and only if $M’$ accepts
accepts an input tape
It is clear that.
$CM_{2}$$0^{2^{j}}$$M^{u}$

Lemma 3.
$T_{j}(L)\in\tilde{\ell}$

For each $L\subseteq\{0^{2}" |n\geq 1\}$ and for[ $CS$-DCM(k)[Space(n)]] ($\tilde{f}[CS$$j,$ $k\geq 1$$0^{2’}$$0$:-NCM(k)[Space(n)]])$\Rightarrow L\in\overline{f}[CS- DCM(jk+1)[Space(n)]](\tilde{\ell}[CS- NCM(jk+1)[Space(n)]])$.

It was shown in [2] (Lemma 3.3) that $T_{j}(L)\in\overline{f}[SeDIIA(k)](\overline{f}[SeNIIA(k)])\Rightarrow L\in\tilde{f}[SeDHA(jk)]$, where $\tilde{\ell}[SeDHA(k)](\tilde{\ell}[SeNIIA(k)])$ is the class of all languages such thatisaccepted by a sensing two-way deterministic (nondeterministic) k-head finite automaton. On the other hand, one caneasily show that for each $k\geq 1$ ,Proof :$(\tilde{f}[SeNI\ddagger A(jk)])$$L$$L\subseteq\{0^{2^{n}}|n\geq 1\}$

3$\tilde{f}[CS- DCM(k)[Space(n)]](\tilde{f}[CS- NCM(k)[Space(n)]])\subseteq\tilde{\ell}[SeDHA(2k)](\tilde{f}[SeNHA(2k)])$,and$\tilde{f}[SeDHA(k)](\tilde{f}[SeNIIA(k)|)\subseteq\tilde{f}[CS- DCM(k+1)[Space(n)|](\tilde{f}[CS- NCM(k+1)[Space(n)]])$.

Iilom those facts, the lemma follows.
Lemma 4.

$\square$and for $j>3k,$ $k\geq 1$ :For each-NCM(k)[Space(n)]])[ $CS$-DCM(k)[Space(n)]] ($L\subseteq\{0^{2^{n}}|n\geq 1\}$

$T_{j+1}(L)\in\tilde{f}$$\tilde{f}[CS$$\Rightarrow T_{j}(L)\in\tilde{f}[CS- DCM(k+1)[Space(n)]](\tilde{f}[CS- NCM(k+1)[Space(n)]])$.

Let $M=$ $(CM_{1}, CM_{2}, \cdots , CM_{k})$ be a CS-DCM(k)[Space(n)] accepting $T_{j+1}(L)$ . We will construct a
Proof :
CS-DCM $(k+1)[Space(n)]M’=(CM_{1}’, CM_{2)}’\cdots , CM_{k+1}’)$ accepting $T_{f}(L)$ .
It can be tested easily (using 2 counters) whether the input is of the form
for some $n\geq 1$ . If this is the case,is accepted by $M$ . In order to do so $M’$ encodes the input head position,then $M’$ has to test whetherof each, where for each $1\leq v\leq k,$ $0\leq h_{v},$ $c_{v}\leq 2^{(j+1)n}+1$ , by the input head
, and the counter contents, , of each, and two additional numbers
position, , ofthe counter contents, , of
, in such a form that always$0^{2^{j\cdot n}}$$0^{2^{(j+1)n}}$$CM_{v}$$h_{v)}$$CM_{v}$$c_{v}$$h_{v}’$$CM_{v)}’$$c_{v}’$$CM_{v}’$$\sigma_{2v},$$0\leq h_{v}’,$ $c_{v}’\leq 2^{j\cdot n}+1,0\leq\sigma_{2v},$ $\sigma_{2k+v}<2^{n}$,$h_{v}=h_{v}’+\sigma_{2v}\cdot 2^{j\cdot n},$.

$\sigma_{2k+v}$

and$c_{v}=c_{v}’+\sigma_{2k+v}\cdot 2^{j\cdot \mathfrak{n}}$Note that $h_{v}=2^{(j+1)}"+1$ iff $h_{v}’=2^{j}"‘+1$ and $\sigma_{2v}=2"-1$ , and that $h_{v}=h_{u}$ iff either ( $h_{v}’=h_{u}’$ and) holds.
or ( $h_{v}’-h_{u}’=\pm 2^{j}$ “ and$M’$ uses the counter of $CM_{k+1}’$ to store the $2k$ numbeIs$\sigma_{2v}=\sigma_{2u}$)$\sigma_{2v}-\sigma_{2u}=\mp 1$$\sigma_{2},$$\cdots,$ $\sigma_{2k)}\sigma_{2k+1},$$\cdots,$$\sigma_{3k}$in the fofm$c_{k+1}’=\sigma_{1}+\sigma_{2}\cdot 2^{n}+\sigma_{3}\cdot 2^{2n}+\cdots+\sigma_{3k}\cdot 2^{(3k-1)n}+2^{(j-1)n}$where

denotes the counter contents of $CM_{k+1}’$ and $\sigma_{2i-1}=1$ for $1\leq i\leq k$ . This is possible since $j>3k$ .
First $M’$ has to encode the initial head positions and initial counter contents of $M$ . That means it has to set$d_{k+1}$$c_{k+1}’arrow 2^{0\cdot n}+2^{2\cdot n}+\cdots+2^{(2k-2)n}+2^{(j-1)n}$.

This can be done easily (using two counter machines).
$CM_{2’}’CM_{k}’$ can communicate with each other by means of $CM_{k+1}’$
During the simulation of one step of $M,$
(since the input head of $CM_{k+1}’$ is free in the computation), and every $CM_{v}’(1\leq v\leq k)$ always stores in its finite memory, encoded by, are equal to $2^{n}-1$ and the information whether
holdsorwhich of thehas to distinguish twofor each $u\in\{1,2, \cdots, k\}$ , and $v\neq u$ . Furthermore, in order to simulate the action of $CM_{v},$$CM_{1}’,$$\sigma_{2v}’ s$$c_{k+1}’$$\sigma_{2v}=\sigma_{2u}$$\sigma_{2v}=\sigma_{2u}\pm 1$$CM_{v}’$$v,$

cases:(1)does not scan either of the endmarkers) and $0<c_{v}’<2^{j\cdot n}+1$ .
(i.e., the input head ofcan check with the help of $CM_{k+1}’$ whether or not its counter contents is equal to $2^{j}"‘+1$ . In this(Note thatcase, the input head ofsimply changes its input head
does not scan either of the endmarkers, and $c_{v}>0$ .
would do.
position and its counter contents in the same way as$h_{v}’\neq 0,$$h_{v}’\neq 2^{j}""+1$$CM_{v}’$$CM_{v}’$$CM_{v}$$CM_{v}’$$CM_{v}$would move the input head. toor $d_{v}=0$ or $d_{v}=2^{j\cdot n}+1$ . If $h_{v}’=0$ (or $c_{v}’=0$ ) and(2) $h_{v}’=0$ or(or $d_{v}arrow 2^{j\cdot n}-1$
and
has to set
the left (or would decrease the counter), then$h_{v}’=2^{j\cdotn}+1$$c_{v}’=2^{j}"+1$$\sigma_{2k+v}arrow\sigma_{2k+v}-1$) andwould move the input head to the right (or
(or
). If
and
(or
and $\sigma_{2k+v}arrow\sigma_{2k+v}+1$ ).
andhas to set
would increase the counter), thenwould do.
simply changes its input head position and its counter contents in the same way as
Otherwise,$h_{v}’=2^{j\cdot \mathfrak{n}}+1$$CM_{v}$$h_{v}’arrow 2^{j\cdot n}-1$$CM_{v}’$$\sigma_{2v}arrow\sigma_{2v}-1$$CM_{v}$$h_{v}’arrow 2$$CM_{v}’$$c_{v}’arrow 2$$\sigma_{2v}arrow\sigma_{2v}+1$$CM_{v}$$CM_{v}’$) is the difficulty in this proof, and the other operations(or
In the simulation, performing the operation on$CM_{k+1}’$). In the following we will show how $M’$ can perform the operation on
may be easily done (with the help of$\grave{\sigma}_{2v}$$\sigma_{2k+v}$$\sigma_{2v}’ s$(or$\sigma_{2k+v}’ s$).

) is equal to $2”-1$ , using(or(or) and test whether the newcan perform the $operation\pm 1$ on
the algorithms described in 1 and 2 in the proof of Lemma 4 in [1]. Below, we refer to these algorithms as Algorithm 1
and Algorithm 2. For the sake of completeness, we recaU them here, pointing out the necessary changes.
$M’$$\sigma_{2v}$$\sigma_{2k+v}$

We will denote the counter contents of $CM_{k+1}’$ by$\sigma_{2v}$$\lambda$

as follows:$\lambda=\sum_{\mu=1}^{j-1}\sigma_{\mu}\cdot 2^{(\mu-1)n}+2^{(j-1)n}$$\sigma_{2k+v}$

4with $\sigma_{b-1}=1$ for $1\leq i\leq k$ , and $\sigma_{3k+1}=\sigma_{3k+2}=\cdots=\sigma_{j-1}=0$ .
by moving the input head
. (Note that $M’$ can test whether
Furthermore we can assume that$c_{v}’=2^{j\cdotn}-1$
then we set
and store the difference in the finite control of. We
two cells to the right.) If
in the form
decompose$c_{v}’<2^{j\cdot n}$$c_{v}’<2^{j\cdot \mathfrak{n}}$$c_{v}’\geq 2^{j\cdot n}$$CM_{v}’$$d_{v}$$c_{v}’=\psi_{v1}+\psi_{v2}\cdot 2^{n}$with $0\leq\psi_{v1}<2^{n},$ $0\leq\psi_{v2}<2^{(j-1)n}$ .
andwould move the input head to the right. (The cases $h_{v}’=0$ ,Algorithm 1: Now suppose that$d_{v}=0$ anddoes not store anything
will lead to analogous considerations.) Note that the input head ofand therefore it is free for intermediate computations.
“, $0\leq\psi_{v1}<2^{n},$ $0\leq\psi_{v2}<2^{(j-1)n}$ , and,and $CM_{k+1}’$ change$\sigma_{2i-1}=1$ for $1\leq i\leq k,$ $\sigma_{3k+1}=\sigma_{3k+2}=\cdots=\sigma_{j-1}=0$ , into$h_{v}^{\prime r}=2^{j\cdot n}+1$$CM_{v}$$d_{v}=2^{j\cdot \mathfrak{n}}+1$$CM_{v}’$$c_{v}’=\psi_{v1}+\psi_{v2}\cdot 2$$CM_{v}’$$\lambda=\sum_{\mu=1}^{j-1}\sigma_{\mu}\cdot 2^{(\mu-1)\mathfrak{n}}+2^{(j-1)\mathfrak{n}}$$c_{v}’=\psi_{v2}+2^{(j-1)n}$,$\lambda=R_{\mathfrak{n}}(\psi_{v1})+\sigma_{1}\cdot 2^{n}+\cdots+\sigma_{j-1}\cdot 2^{(j-1)n}$,where for any $x<2$ “, $R.(x)$ is defined in the following way:
Let $\varphi_{n}(x)\in\{0,1\},$ $|\varphi_{n}(x)|=n$ , be the binary notation of lengthened by an appropriate number of leading“is that number whose binary notation of length (again aUowing leading zeros) is the reversal ofzeros. Then
$R_{n}(R_{n}(x))=x$$x<2$ “.
for. Note that
$CM_{k+1}’$
can do the above by executing the following:and$x$$R_{\mathfrak{n}}(x)<2$

$n$

au

$\varphi_{n}(x)$$CM_{v}’$$d_{v}arrow d_{v}+2^{j\cdot \mathfrak{n}}$,$\lambda<2^{j}$ “‘$While_{1}$$Do_{1}$$Begin_{1}$$d_{v}arrow[c’\not\in]$

, and
,

$\alphaarrow d_{v}-2[c’\not\in]$,$\lambdaarrow\alpha+2\lambda$$End_{1}$$\lambdaarrow\lambda-2^{j\cdot n}$.

and $CM_{k+1}’$ can perform this computation, since their input heads are free now. The loop
It is clear thatjEnd_{1})$ is carried out exactly
times and this leads to the counter contents and which we wanted. Note
, we can, in
is given by the position of the right endmarker, and du ing the computation, ifthat$CM_{v}’$$(Begin_{1}, \cdot.

$\lambda$$d_{v}$$n$$2^{j\cdot n}$$d_{v},$

fact, store$[ \frac{c’}{2^{f\hslash}}L+1-],$$[ \frac{\lambda}{2^{J^{n}}+1}]$$\lambda-(2^{j\cdot n}+1)[\frac{\lambda}{2^{J^{\mathfrak{n}}}+1}]$

Algorithm 2:$CM_{v}’$in the finite controls ofin the counters of$CM_{v}’$and $CM_{k+1}’$ change$d_{v}$$CM_{v}’$and $CM_{k+1}’$ , and the residues,

and $CM_{k+1}’$ , respectively.
and$\lambda$

into$c_{v}’=\sigma_{j-1}+\psi_{v2}\cdot 2^{n}$,$\lambda=R_{n}(\psi_{v1})+\sigma_{1}\cdot 2^{n}+\cdots+\sigma_{j-2}\cdot 2^{(j-2)\mathfrak{n}}+2^{(j-1)n}$

Let $Bit_{m}(x)$ denote the m-th least significant bit of the binary notation ofzeros).
first changes into
$CM_{k+1}^{/}$$\lambda\geq 2^{j\cdot n}+1$$c_{v}’-(2^{j\cdot n}+1)[ \frac{c}{2^{J^{n}}}/L+-1]$$x$.
with length $\geq m$ (aUowing leading$\lambda$,$\lambda=R_{n}’(\psi_{v1})+\sigma_{1}\cdot 2^{\mathfrak{n}}+\cdots+\sigma_{j-2}\cdot 2^{(j-2)n}+2^{(j-1)\mathfrak{n}}$where$R_{\mathfrak{n}}’(\psi_{v1})=\{\begin{array}{l}R_{\mathfrak{n}}(\psi_{vl})R_{n}(\psi_{vl})+l\end{array}$That is, only the lowest bit of is changed in such a way thatwhether
is odd or even.)
and $CM_{k+1}’$ execute the foUowing:
Afterwards$\lambda$$R_{\mathfrak{n}}(\psi_{v1})$$CM_{v}’$$c_{v}’<2^{j}$ “‘$While_{2}$$Do_{2}$$Begin_{2}$$If_{1}$$2\lambda\geq 2^{j\cdot n}$$then_{1}$$\lambdaarrow 2\lambda-2^{j\cdot n},$$d_{v}arrow 1+2c_{v}’$,$\lambda$$ifBit_{1}(\psi)=1otherwise^{v.1}$

becomes an odd number. (It is stored in the finite control

5$else_{1}$$d_{v}arrow 2c_{v}’$$\lambdaarrow 2\lambda,$,

Endifi$End_{2}$In order to see what is done by the above execution, we consider the decompsition$\lambda=\lambda’+\alpha\cdot 2^{j\cdot n-1}$’

Then $\alpha=1$ if and only if“. Note that Bitj.
) is carried out exactly times and the number
are changed by this execution into$2\lambda\geq 2^{j}$$\ldots,$$End_{2}$$n(\lambda)=\alpha$$n$,$\lambda’<2^{j\cdot n-1}$.

. As in Algorithm 1 it can be seen that the loop $(Begin_{2}$ ,is carried over from to
bit by bit. Therefore,
and$\lambda$$\sigma_{j-1}$$d_{v}=\sigma_{J^{-1}}+\psi_{v2}\cdot 2^{n}+2^{j\cdot n}$’$c_{v}’$$\lambda$$d_{v}$,$\lambda=R_{n}’(\psi_{v1})2^{n}+\sigma_{1}\cdot 2^{2n}+\cdots+\sigma_{j-2}\cdot 2^{(j-1)n}$.

Then, we obtain the counter contents which we wanted by:(a) subtracting(b) adding$2^{j\cdot \mathfrak{n}}$(c) dividing(d) changing$\lambda$$2^{j\cdot n}$from$c_{v}’$,

to ,$\lambda$by 2 as long as the remainder is ,$0$

$R_{\mathfrak{n}}’(\psi_{v1})$

into$R_{n}(\psi_{v1})$.

Instead of$c_{v}’=\psi_{v1}+\psi_{v2}\cdot 2^{n}$,$\lambda=\sum_{\mu=1}^{j-1}\sigma_{\mu}\cdot 2^{(\mu-1)\mathfrak{n}}+2^{(j-1)n}$,

we write$(c_{v}’;\lambda)=(\psi_{v1}; \sigma_{1}, \cdots,\sigma_{j-1})$

The application of Algorithms

$J,$

$2$

.

induces the transition.

$(\psi_{v1)}\cdot\sigma_{1}, \cdots, \sigma_{j-1})arrow(\sigma_{j-1};R_{\mathfrak{n}}(\psi_{v1}), \sigma_{1, )}\sigma_{j-2})$

Therefore, by $j-2v$ applications, we get$(\psi_{v1} ; \sigma_{1)}\cdots, \sigma_{j-1})arrow(\sigma_{j-1};R_{\mathfrak{n}}(\psi_{v1}), \sigma_{1}, \cdots, \sigma_{j-2})arrow\cdots$$arrow(\sigma_{2v}; R_{n}(\sigma_{2v+1}), \cdots, R_{n}(\sigma_{j-1}), R_{\mathfrak{n}}(\psi_{v1}), \sigma_{1}, \cdots,\sigma_{2v-1})$.

Now Algorithm 1 is applied again. Since during the computationis arried over from to bit by bit,
and $CM_{k+1}’$ are able to $add+1$ and to test whether the newis equal to $2^{n}-1$ (this is true if and only if all bits which
are carried over are equal to one). Afterwards we apply Algorithm 2 and get$\sigma_{2v}$$c$$d_{v}$$\lambda$$CM_{v}’$$\cdot$$\sigma_{2v}$$(\sigma_{2v-1)}\cdot R_{n}(\sigma_{2v}+1), R_{n}(\sigma_{2v+1}),$Since $R_{n}(R_{n}(x))=x$ forau$x<2^{n}$$\cdots,$$R_{\mathfrak{n}}(\sigma_{j-1}),$$R_{n}(\psi_{v1}),$ $\sigma_{1},$ $\cdots,\sigma_{2v-2}$, further applications of Algorithms 1,

lead to$\ell$$(\psi_{v1};\sigma_{1,}\sigma_{2v-1}, \sigma_{2v}+1, \sigma_{2v+1,-1} \sigma_{\dot{f}})$

).

.

(or
) and test
This shows that by the applications of Algorithms 1,2, $M’$ can perform the $operation\pm 1$ on(or) is equal to $2”-1$ .
whether the newcan decide whether the new
Next we show how
for each $u\in\{1,2, \cdots, k\}$ and $v\neq u$ (when $k\geq 2$ ),andby the application of Algorithm 3 below. We will use
and $CM_{k+1}’$ . (Note that the input heads of$CM_{k+1}’$ are free.) As in the above, we decompose
andin the form$\sigma_{2v}$$\sigma_{2v}$$M^{l}$$\sigma_{2v}=\sigma_{2u}$$CM_{v}’,$$c_{v}’$$CM_{v}’$$CM_{u}’$$d_{u}$$c_{v}^{/}=\psi_{v1}+\psi_{v2}\cdot 2^{n}$with $0\leq\psi_{v1}<2^{n},$ $0\leq\psi_{v2}<2^{(j-1)n}$ , and$c_{u}’=\psi_{u1}+\psi_{u2}\cdot 2^{\mathfrak{n}}$with $0\leq\psi_{u1}<2^{n},$$\sigma_{2k+v}$$\sigma_{2k+v}$$0\leq\psi_{u2}<2^{(j-1)\mathfrak{n}}$. The counter contents of$CM_{k+1}’$

is denoted by$\lambda=\sum_{\mu=1}^{j-1}\sigma_{\mu}\cdot 2^{(\mu-1)n}+2^{(j-1)n}$$\lambda$

as follows:6with $\sigma_{2i-1}=1$ for $1\leq i\leq k$ , and $\sigma_{3k+1}=\sigma_{3k+2}=--$ $=\sigma_{j-1}=0$ .

Algorithm 3: We first apply Algorithms 1, 2 to$(d_{v}; \lambda)=(\psi_{v1} ; \sigma_{1}, \cdots , \sigma_{j-1})$

by $(j-2v)$ times to get$(\psi_{v1)}\cdot\sigma_{1}, \cdots, \sigma_{j-1})$$\Rightarrow(\sigma_{2v};R_{n}(\sigma_{2v+1}))$)$R_{\mathfrak{n}}(\sigma_{j-1}),$After that, we apply Algorithms 1, 2 totimes to get$(\psi_{u1};R_{n}(\sigma_{2v+1}))$$R_{n}(\psi_{v1}),$$\sigma_{1},$$\cdots,$ $\sigma_{2v-1}$).

$(c_{u}’; \lambda)=(\psi_{\tau\iota 1_{1}}\cdot R_{n}(\sigma_{2v+1}), \cdots, R_{n}(\sigma_{j-1}), R_{n}(\psi_{v1}), \sigma_{1}, \cdots, \sigma_{2v-1})$$R_{\mathfrak{n}}(\sigma_{j-1}))R_{n}(\psi_{v1}),\sigma_{1},$$\Rightarrow(\sigma_{2u}; R_{n}(\sigma_{2u+1}), \cdots, R_{\mathfrak{n}}(\sigma_{2v-1}))R_{n}(\psi_{\tau\iota 1})$$\cdots,$ $\sigma_{2v-1}$

by $2(v-u)$

)

,

),
$1\lequ<v\leq
j$
.
of
that
suppose,generality,
wewithoutloss
where
by executing the following
to
with
from
and $CM_{k+1}’$ compareNowreverse)(or
computation,
its
used
as
an
identifier for distinguishingiscomputation. Note that in the following
bytechnique.
using
are
over
to
a
rotationbitsofcarriedthe bits offrom when the,$R_{n}(\sigma_{2v+1}),$$CM_{u}’$$CM_{v}’,$$Bit_{1}(\sigma_{2v})$$\sigma_{2u}$$\sigma_{2v}$)$R_{n}(\sigma_{j-1}),$$R_{\mathfrak{n}}(\psi_{v1}),$$\sigma_{1},$$\cdots,$ $\sigma_{2u-1}$$Bit_{\lceil\frac{\mathfrak{n}}{2}\rceil}(\sigma_{2v})$$Bit_{2}(\lambda)$$\sigma_{2v}(\sigma_{2u})$$\sigma_{2v}(\sigma_{2u})$$\lambda$$\lambda$$\lambdaarrow\overline{\alpha}+2\lambda$$\alphaarrow Bit_{2}(\lambda)$$\beta=\gammaarrow 0$,$else_{3}$and$\lambda<2^{j\cdot n}$$While_{3}$$\beta=\gamma$$Do_{3}$$\betaarrow Bit_{1}(c_{v}’)$$\gammaarrow Bit_{1}(d_{u})$$2\lambda<2^{j\cdot n}$$If_{3}$$Begin_{3}$$If_{2}$,$\lambdaarrow\beta+2\lambda$

,

then4

,
,

$Tarrow 0$

,

else4

$\beta=\gamma$$Tarrow 1$$then_{2}$$Endif_{4}$,,,$c_{u}^{v}d_{/}arrowarrow[cs][- d’r]^{)}$$\lambda\lambdaarrow\beta\ddagger^{2\lambda}2\lambdaarrow\alpha$$Endif_{3}$$4\lambda<2^{j\cdot \mathfrak{n}}$$If_{3}$$Endif_{2}$$then_{3}$$\nearrow$$End_{3}$ ,else.
denotes the reverse of , that is, if $\alpha=1$ then$(While_{3}\cdots
Do_{3})$
only one of control conditions $(\lambda<2^{j}")$ and $(\beta=\gamma)$ is changed. It
Note that in the above$(While_{3}\cdots
Do_{3})$(so $M’$ wiu restore the used
is carried out, if
then this means
is clear that after$(Wh;le_{3}\cdots
Do_{3})$
is done, by the application of procedure Replace below),counter machines, respectively, as jsut before) is carried out exactly
times, and this leads to), the loop (Begin 3
and otherwise (i.e., if

where$\overline{\alpha}$$\overline{\alpha}=0$$\alpha$$\beta\neq\gamma$$\overline{\alpha}=1$$\sigma_{2v}\neq\sigma_{2u}$)$End_{3}$$\beta=\gamma$$r\frac{n}{2}\rceil$$\lambda=R_{n}(\sigma_{2u+1})\cdot 2^{2\lceil\frac{n}{}\rceil}+\cdots+\sigma_{2u-1}\cdot 2^{(j-2)n}\cdot 2^{2\lceil\#\rceil}+2^{(j-1)n}\cdot 2^{2\lceil\neq\rceil}$

Note that $\sigma_{2u-1}=1$ andcomparewithfrom$\sigma_{2u}$$\sigma_{2v}$$2^{(j-1)n}\cdot 2^{2\lceil\frac{n}{2}\rceil}=(T+1)2^{\dot{f}}$$Bit_{\lceil^{\underline{n}}\rceil+1}(\sigma_{2v})$

to$Bit_{n}(\sigma_{2v})$“.

$CM_{v}’,$$CM_{u}’$and $CM_{k’+1}$ then execute the following and

if necessary.

$\beta\neq\gamma$$If_{5}$$\lambdaarrow\overline{\alpha}+2\lambda$$then_{5}$Replace$(\lambda, \kappa_{1}, \kappa_{2};\alpha)$,$\lambdaarrow\beta+2\lambda$,,$Endif_{6}$$else_{5}$$\lambdaarrow\lambda-(T+1)2^{j\cdot n}$$\lambda<2^{j}$ “$While_{4}$End4,Replace,and$\beta=\gamma$$Do_{4}$

Begin4$\betaarrow Bit_{1}(d_{v})$$\gammaarrow Bit_{1}(c_{u}’)$$If_{0}$,,$(\lambda, d_{v}, c_{u}’;\alpha)$,$\lambdaarrow\lambda+(T+1)2^{j\cdot \mathfrak{n}}$,$\piarrow Bit_{1}(\lambda)$$d_{v}arrow\pi+2c_{v}’$$then\iota$,,$\lambdaarrow[_{\overline{2}}\lambda_{7]}$Replace$c’d_{u}^{v}arrowarrow[c\not\in^{\prime_{/}}][- cr]^{1}$$Endif_{5}$$\nearrow$

Procedure Replace(
While
Begin

,

$d_{l}arrow\tau+2c\downarrow$$\beta=\gamma$$\lambda,$$d_{v},$$Bit_{2}(\lambda)\neq\alpha$

; a):
Do

$c_{r}^{\prime }$.

$(\lambda, \kappa_{1}, \kappa_{2};\alpha)$,7$\piarrow Bit_{1}(\lambda),$$c_{v}’arrow\pi+2d_{v}{}_{)}C_{l}’arrow\pi+2c_{t)}’\lambdaarrow[_{\overline{2}}\lambda_{7]}$,End
Endprocedure
times, and that during the above
It wiu be easily seen that the loop $(Begin_{4}\cdots End_{4})$ is carried out at mostholds. (See Fig. 3 and Fig. 4.)
computation, the number
is carried over to bit by bit as long as$L\frac{n}{2}\rfloor$$\sigma_{2v}(\sigma_{2u})$Fig. 3. The binary notation of$1\leq i\leq m,$$\beta=\gamma$$\lambda$$\lambda$

after $(WhiIe_{3}\cdots Do_{3})$ ends with$\beta;=B|t_{i}(\sigma_{2}.)=Bit_{i}(\sigma_{2*})$

Fig. 4. The binary notation ofand if $m=n$ (i.e.,) then$\beta=\gamma$$\lambda$$\beta\neq\gamma$, where for each(but $Bit_{m+1}(\sigma_{2}.)\neq Bit_{+1}(\sigma_{2*})$ ).

.

after $(While_{4}\cdots Do_{4})$ is carried out, where$\rho_{n}\rho_{n-1}\cdots\rho_{1}$is the binary representation of$\sigma_{2}$

$=$

tel

$(=\sigma_{2*})$.

, then, and otherwise(if
Now $M’$ has finished the comparison between
and
) and
restored the used counter contents as just before $(While_{3}\cdots Do_{3})$ . Then, further applications of Algorithms 1, 2 lead to$\sigma_{2v}$$\sigma_{2u}$$\beta=\gamma$$\sigma_{2v}=\sigma_{2u}$$\sigma_{2v}\neq\sigma_{2u}$$(c_{u}’; \lambda)=(\psi_{u1}; R_{n}(\sigma_{2v+1}), \cdots, R_{n}(\sigma_{j-1}), R_{n}(\psi_{v1}), \sigma_{1}, \cdots, \sigma_{2v-1})$

and$(c_{v}’; \lambda)=(\psi_{v1} ; \sigma_{1)}\cdots, \sigma_{j-1})$.

This shows that $M’$ is able to simulate $M$ step by step.
Theorem 1.

$O$

For each $k\geq 1$ ,(1) $\ell_{\Sigma}[CS- DCM(k)[Space(n)|1\subsetneq x_{\Sigma}[CS- DCM(k+1)[Space(n)||$ ,(2) $f_{\Sigma}[CS- NCM(k)[Space(n)||\subsetneq x_{\Sigma}[CS- NCM(k+1)[Space(n)||$ ,even if the alphabet$\Sigma$

is restricted to a one-letter.

Proof: Suppose there exists some $k\geq 1$ such that $f_{\{0\}}[CS- DCM(k)[Space(n)]]=f_{\{0\}}[CS- DCM(k+1)[Space(n)]]$.
This implies $\tilde{\ell}[CS- DCM(k)[Space(n)]]=\tilde{\ell}[CS- DCM(k+1)[Space(n)]]$, and therefore the following is true:$\forall L\in DS\overline{PA}CE(\log n)$(Lemma 2)$\Rightarrow\exists j(>3k),T_{j}(L)\in\tilde{f}[CS- DCM(2)[Space(n)]]$[$\Rightarrow T_{j}(L)\in\tilde{f}[CS- DCM(k+1)[Space(n)]]=\tilde{\ell}$ $CS$

-DCM(k)[Space(n)]]$\Rightarrow T_{j-1}(L)\in\tilde{\ell}[CS- DCM(k+1)[Space(n)]]=\tilde{f}[CS- DCM(k)[Space(n)]]$(Lemma 4)$\Rightarrow\cdots$$\Rightarrow T_{3k+1}(L)\in\tilde{f}[CS- DCM(k+1)[Space(n)]]=\tilde{f}[CS- DCM(k)[Space(n)]]$$\Rightarrow L\in\tilde{f}[CS- DCM(k(3k+1)+])[Space(n)]]$(Lemma 4)(Lemma 3)

Therefore $\ell_{\{0\}}[CS- DCM(k)[Space(n)]]=\ell_{\{0\}}[CS- DCM(k+1)[Space(n)]]$ implies DSPACE $(\log n)\subseteq\tilde{f}[CS- DCM(k$$(3k+1)+1)[Space(n)]]$ , which is a contradiction to Lemma 1.
$O$

REFERENCES
1. B. Monien, “Two-way multihead automata over r oneletter alphabet”, RAIRO Inform. Theor. 14, (1980) .67-82.

2. Y. Wang, K. Inoue and I. Takanami, Some hierarchy results on multihead automata over a one-letter alphabet, IEICE TRANS. INF. &SYST., Vol. E76-D, No.6, $(1993)625-633$ .
3. Y. Wang, K. Inoue and I. Takanami, Cooperating systems of one-Way counter machines (in Japanese), RIMS $Koky-rok\iota 79\theta$ , (Kyoto

University, June 1992)$8_{!}-14$.