Information Technology Reference
In-Depth Information
a
=?
0
1
b
=?
b
=?
0
1
0
1
c
=?
c
=?
c
=?
c
=?
0
1
0
1
0
1
0
1
001
Figure 10.13
A normal-form tree program for table lookup. It has one path for each value of
the input.
110
010
000
011
101
111
100
Delete the original edges and add an edge from vertex
u
in the
i
th copy to vertex
v
in the
(
i
+
1
)
st copy if there was an edge between
u
and
v
in the original graph. Now delete all
edges and vertices that are not reached from the root of the zeroth branching program. (See
Fig.
10.14
.)
This procedure increases the number of vertices by at most a factor of
T
,therebyin-
creasing the space by adding at most
log
T
. However, a branching program with space
S
has 2
S
vertices. Thus, the length of the longest path through the program
T
cannot exceed
2
S
,or
S
+log
T
≤
2
S
.
Generally the space
S
used for a branching program computation will be large by com-
parison with
log
T
, in which case the space bounds for normal-form branching programs and
general branching programs will differ by at most a constant factor.
In the rest of this chapter when we speak of a branching program we mean a general
branching program.
Figure 10.14
Construction of a normal-form general branching program as a level multigraph.
Search WWH ::
Custom Search