Information Technology Reference
In-Depth Information
10.20 A finite-state machine
M
computes the function
f
(
n
)
M
Ψ
n
that maps
the initial state in
Q
and an input string
x
of length
n
over the input alphabet
Σ
onto
an output string
y
of the same length over the output alphabet
Ψ
. Such a machine
can compute a function
f
:
Σ
n
:
Q
×
→
n
by associating inputs and outputs of
f
with
inputs and outputs of
f
(
n
M
. A computation of an FSM
M
of a function
f
is
input-
output oblivious
if the times at which inputs of
f
are read and its outputs produced
are independent of the value of its input variables.
Show that Theorem
10.4.1
can be generalized from straight-line computations to com-
putations by input-output-oblivious FSMs.
Hint:
Try to parallel the proof of Theorem
10.4.1
using the FSM
M
instead of the
pebble game. What correspondence can you make between the values under pebbles
before the interval
n
A
→A
I
and the state of
M
?Let
log
2
|
Q
|
,where
Q
is the set of states of
M
, be the measure of space associated with it.
10.21 Give a design of an FSM that computes a function
f
from straight-line programs for it
using a number of steps and storage locations proportional to the time and space used
by a pebbling strategy for this straight-line program.
Hint:
Design the FSM so that it receives the inputs provided to the pebbling strategy
as well as instructions to specify which operations are performed on the inputs and
temporary storage locations of the FSM.
TRANSITIVE FUNCTIONS
10.22 Many functions for which space-time lower bounds have been derived are transitive.
Such functions have the property that for subsets
X
and
Y
of their inputs and outputs,
respectively,
=
n
, the (control) inputs not in
X
canbechosensoastocause
the outputs in
Y
to be equal to an arbitrary permutation drawn from the set
G
(
n
)
of the inputs in
X
. For example, the cyclic shifting function studied in Section
2.5.2
has a set of control inputs that specify the amount by which value inputs are permuted
cyclically and assigned to the output variables.
|
X
|
=
|
Y
|
DEFINITION
10.13.2
Let
G
(
n
)
be a group of permutations of the integers
(
n
)=
{
0,
1, 2,
...
,
n
(
n
)
.Wedenoteby
π
(
i
)
the integer to which integer
i
is mapped by
π
.Afunction
f
G
(
n
)
:
−
}
.Thatis,if
π
is in
G
(
n
)
,then
π
:
(
n
)
→
1
n
,where
(
y
n−
1
,
...
,
y
1
,
y
0
)=
f
G
(
n
)
(
x
n−
1
,
...
,
x
1
,
x
0
,
c
s−
1
,
...
,
c
0
)
, is said to have
value in-
puts
x
n−
1
,
...
,
x
1
,
x
0
,
control inputs
c
s−
1
,
...
,
c
0
,and
outputs
y
n−
1
,
...
,
y
1
,
y
0
.
Such a function is
transitive of order
n
with respect to the group
G
(
n
)
if
n
+
s
A
→A
≤
i
≤
n
−
≤
j
≤
n
−
1
, there exists a permutation
π
∈
G
(
n
)
a) For each
0
1
and
0
such that
π
(
i
)=
j
,and
b) For each
π
∈
G
(
n
)
, there is an assignment to
c
s−
1
,
...
,
c
0
such that
y
π
(
i
)
=
x
i
for
0
≤
i
≤
n
−
1
.
Show that every transitive function of order
n
with respect to the permutation group
G
(
n
)
,
f
G
(
n
)
:
n
,is
(
2,
n
+
s
,
n
,
n/
2
)
-independent.
10.23 Show that the cyclic shifting function
f
(
n
)
n
+
s
A
→A
n
+
log
n
n
defined in Sec-
cyclic
:
B
→B
tion
2.5.2
is transitive of order
n
.
Search WWH ::
Custom Search