Information Technology Reference
In-Depth Information
The state-to-state mappings in
S
will be obtained by composing the mappings
{
Δ
x
:
Q
→
Q
|
x
∈
Σ
}
using this operator.
Below we show that the operator
satisfies the property
(
h
1
is
associative
,thatis,
h
2
)
h
3
=
h
1
(
h
2
h
3
)
. This means that for each
q
∈
Q
,
((
h
1
h
2
)
h
3
)(
q
)=
(
h
1
(
h
2
h
3
))(
q
)=
h
3
(
h
2
(
h
1
(
q
)))
. Applying the definition of
in Equation (
3.2
), we
have the following for each
q
∈
Q
:
((
h
1
h
2
)
h
3
)(
q
)=
h
3
((
h
1
h
2
)(
q
))
=
h
3
(
h
2
(
h
1
(
q
)))
(3.3)
=(
h
2
h
3
)(
h
1
(
q
))
=(
h
1
(
h
2
h
3
))(
q
)
Thus,
)
is a semigroup. (See Section
2.6
.) It follows that a prefix
computation can be done on a sequence of state-to-state mappings.
We now use this observation to construct a shallow circuit for the function
f
(
T
M
.Let
w
=
(
w
1
,
w
2
,
...
,
w
T
)
be a sequence of
T
inputs to
M
where
w
j
is supplied on the
j
th step. Let
q
(
j
)
be the state of
M
after receiving the
j
th input. From the definition of
is associative and
(
S
,
it follows that
q
(
j
)
has the following value where
s
is the initial state of
M
:
q
(
j
)
=(Δ
w
1
Δ
w
2
···
Δ
w
j
)(
s
)
The value of
f
(
T
)
M
on initial state
s
and
T
inputs can be represented in terms of
q
=(
q
(
1
)
,
...
,
q
(
T
)
)
as follows:
f
(
T
M
(
s
,
w
)=
q
(
n
)
,
λ
(
q
(
1
)
)
,
λ
(
q
(
2
)
)
,
...
,
λ
(
q
(
T
)
)
Λ
(
T
)
be the following sequence of state-to-state mappings:
Let
Λ
(
T
)
=(Δ
w
1
,
Δ
w
2
,
...
,
Δ
w
T
)
It follows that
q
can be obtained by computing the state-to-state mappings
Δ
w
1
Δ
w
2
···
Δ
w
j
,1
≤
j
≤
T
, and applying them to the initial state
s
.Because
is associative, these
T
(
T
)
P
Λ
(
T
)
state-to-state mappings are produced by the prefix operator
on the sequence
(see
Theorem
2.6.1
):
(
T
)
Λ
(
T
)
)=(Δ
w
1
,
(Δ
w
1
P
(
Δ
w
2
)
,
...
,
(Δ
w
1
Δ
w
2
...
Δ
w
T
))
Restating Theorem
2.6.1
for this problem, we have the following result.
THEOREM
3.2.1
For
T
=
2
k
,
k
an integer, the
T
state-to-state mappings defined by the
T
inputs
to an FSM
M
can be computed by a circuit over the basis
Ω=
{}
whose size and depth satisfy
the following bounds:
C
Ω
(
T
)
P
≤
2
T
−
log
2
T
−
2
D
Ω
(
T
)
P
≤
2
log
2
T
Search WWH ::
Custom Search