Information Technology Reference
In-Depth Information
e
(
j
)
j
6
1
5
4
2
3
3
2
3
2
1
1
123
i
Figure 9.10
Let
f
(
n
)
are
(
n/
2
)
-tuples. The dots in
the
j
th row show the inputs on which
τ
j
depends.
e
(
j
)
is the number of dots in the
j
th row.
merge
(
x
y
)=(
τ
1
,
...
,
τ
n
)
,where
x
y
,
and
are sorted,
x
r
+
1
=
=
x
k
=
0. On the other hand, if
x
r
=
1, by monotonicity the value
of
τ
r
+
s
cannot change under variation of the values
x
r
+
1
,
...
,
x
k
.Thus,
τ
j
is essentially
dependent on
x
i
for
i
and
j
satisfying 1
···
i
+
k
.(SeeFig.
9.10
.) Let
e
(
j
)
denote the number of variables in
x
on which
τ
j
depends; then
e
(
j
)=
j
for
j
≤
i
≤
k
and
i
≤
j
≤
≤
k
and
e
(
j
)=
2
k
j
+
1for
j>k
.
We show by induction that there exist vertex-disjoint paths between
x
1
and
τ
s
+
1
,
x
2
and
τ
s
+
2
,
...
,
x
k
and
τ
s
+
k
for 0
−
k
.(SeeFig.
9.11
.) Thus, there are
k
+
1setsof
vertex-disjoint paths connecting the
k
=
n/
2inputsin
x
and
k
consecutive outputs.
≤
s
≤
τ
1
τ
2
τ
3
τ
4
τ
5
τ
6
τ
7
τ
8
τ
5
τ
2
x
1
x
2
x
3
x
4
y
1
y
2
y
3
y
4
x
1
x
2
x
1
x
2
x
3
x
4
(a)
(b)
Figure 9.11
(a) In a monotone circuit for
f
(
n
)
merge
,
n
=
2
k
,
k
+
1setsof
k
disjoint paths exist be-
tween the
k
inputs
x
and
k
consecutive outputs. (b) The paths to an output
τ
j
form a binary tree.
Search WWH ::
Custom Search