Problem Solving in Automata, Languages, and Complexity

6.2 Time and Space Complexity 289

input tape input tape

0 b a b a a 0 BbabaaB

4

work tape work tape

bBaacabB

*g\\*.. :b.

bBaa cabB

Figure 6.2: Tape compression.

Proof. It is clear that we only need to prove the theorem for 0 < c < 1. Let
A E DSPACE(s(n)). By Th eorem 6.7, we may assume that A is accepted by
a standard one-worktape DTM M with space bound s(n). We will show that
A is accepted by another standard one-worktape DTM AP with space bound
c l s(n). The basic idea is to group together a number of tape cells of M into
a single cell and simulate the computation of M accordingly. To do this, we
need to enlarge the character set and state set of &V.
Let m. be a positive integer such that m > 6/c. We divide cells in the work
tape of M into groups, each group containing exactly m. cells. Each group of
cells forms a single tape cell of AP. Thus, if the set of tape symbols of M is
I’, then the set of tape symbols of AP is I U I’“; that is, each tape symbol of
AP in the input tape is a symbol a E I, and each tape symbol of AJ’ in the
work tape is of the form [ai,, ai,,... , ui,.,J, where each uik E I. In order to
simulate machine A& AP records the internal position of the work tape head
within a group of cells in its state. That is, if the set of states of M is Q, then
the set of states of M’ is Q’ = Q x {1,2,... , nz). A state (4, j) indicates that

the machine M’ is simulating AJ at state q, with its work tape head scanning

the jth cell within the current group cell scanned by the work tape head of

M’.

With this setting, it is easy to see that each configuration of AP corre-

sponds to a unique configuration of A,C For instance, Figure 6.2 shows the

correspondence between two configurations (where ~2 = 4). From this corre-

spondence between configurations, it is clear how to simulate each move of M

by AP. We omit the detail of the simulation.

Furthermore, we note that M’ visits at most [s(n)/mJ +2 cells of the work

tape (the worst case happens when s(n) = km+2for some K > 1, and M’

encodes the middle km cells into k groups). Note that if s(n) >3/c, - then

In the case of s(n) < 3/ c, we note that M’ visits only one cell of the work