Information Technology Reference
In-Depth Information
P
with input variables
x
over the set
A
and output variables
y
over
A
branching program
is a rooted directed acyclic multigraph that has a query
q
(
x
)
associated with each vertex
except for sink vertices and has a query outcome associated with every edge directed away from a
vertex. Each edge may also carry as a label the values of some output variables, with the proviso that
each output variable is assigned exactly one value along any one path from the root to a sink vertex.
F
the set
The
decision branching program
is a special kind of branching program in which the
queries
q
(
x
)
compare two variables and produce either the two outcomes
{≤
,
>
}
or the three
outcomes
.Figure
10.11
shows an example of a decision branching program that
merges two 2-element sorted lists
(
u
1
,
u
2
)
and
(
v
1
,
v
2
)
(
u
1
≤
{
<
,
=
,
>
}
v
2
)byusing
queries that compare the values of two input variables. Each vertex in the example has two
out-directed edges corresponding to the results of the query. The outputs appear in sorted
order along a path from the root to a leaf.
A
decision tree
is a decision branching program whose DAM (directed acyclic multigraph)
is a tree. A decision tree may be constructed for a sequential comparison-based sorting algo-
rithm, such as Batcher's odd-even merging algorithm of Section
6.8
, by associating the first
comparison with the root, the second comparisons with the roots of the left and right subtrees,
etc.
u
2
and
v
1
≤
DEFINITION
10.9.2
A
computation on a branching program
P
is a traversal of the unique
path in the DAM from the root to a leaf determined by the values of the input variables in
x
=
(
x
1
,
x
2
,
...
,
x
n
)
over the set
A
.The
output of the computation
is the sequence of output values
in
y
=(
y
1
,
y
2
,
...
,
y
m
)
over the set
F
encountered on the edges of the path traversed.
m
with input variables in
x
and output variables in
y
,namely
Afunction
f
(
n
)
:
n
A
→F
f
(
n
)
(
x
1
,
x
2
,
...
,
x
n
)=(
y
1
,
y
2
,
...
,
y
m
)
u
1
:
v
1
≤
>
u
1
v
1
u
2
:
v
1
u
1
:
v
2
≤
≤
>
>
v
1
u
1
u
2
:
v
2
≤
>
u
2
v
1
v
2
u
2
v
2
v
2
u
2
v
2
u
1
u
2
Figure 10.11
A decision branching program that merges the lists
(
u
1
,
u
2
)
and
(
v
1
,
v
2
)
when
u
1
≤ u
2
and
v
1
≤ v
2
.
Search WWH ::
Custom Search