Machines with Memory - Models of Computation: Exploring the Power of Computing - page 104

Let N ( x , y )= N ( x )

N ( y ) be the Boolean matrix-matrix multiplication of matrices N ( x )
and N ( y ) in which addition is OR and multiplication is AND .Then,foreach x and y the entry
in row i and column j of N ( x )

×

N ( y ) ,namely n ( 2 )

×

i , j ( x , y ) , satisfies the following identity:

i , j ( x , y )=
q t ∈Q

n ( 2 )

n i , t ( x ) · n t , j ( y )

That is, n ( 2 )

Q such that in state q i , M is given input x ,
moves to state q t , and then moves to state q j on input y . Thus, the composition operator

i , j ( x , y )= 1 if there is a state q t ∈

can be realized through the multiplication of Boolean matrices. It is straightforward to show
that matrix multiplication is associative. (See Problem 3.10 .)
Since matrix multiplication is associative, a prefix computation using matrix multiplica-
tion as a composition operator for each prefix x ( j ) =( x 1 , x 2 , ... , x j ) of the input string x
generates a matrix N ( x ( j ) )= N ( x 1 ) × N ( x 2 ) ×···× N ( x j ) defining the state-to-state

mapping associated with x ( j ) for each value of 1 n .

The fourth step, the application of a sequence of state-to-state mappings to the initial state
s = q r , represented by the

≤ j ≤

| Q |

-vector σ ( r ) , is obtained through the vector-matrix multiplica-

tion σ ( r ) N ( x ( j ) ) for 1

n .
The fifth step involves the computation of the output word from the current state. Let
the column

≤ j ≤

-vector λ containinthe t th position the output of the FSM M when in state
q t . Then, the output produced by the FSM after the j th input is the product σ ( r ) N ( x ( j ) ) λ .
This result is summarized below.
THEOREM 3.2.2 Let the finite-state machine M =(Σ , Ψ , Q , δ , λ , s , F ) with |Q| states compute
asubfunction f of f ( T M in T steps. Then f has the following size and depth bounds over the
standard basis Ω 0 for some κ

| Q |

≥

1 :
C Ω 0 ( f )= O ( M matrix (

| Q |

, κ ) T )

)(log T ))
Here M matrix ( n , κ ) is the size of a circuit to multiply two n

D Ω 0 ( f )= O (( κ log | Q |

× n matrices with a circuit of depth

κ log n . These bounds can be achieved simultaneously.

, x an
input, each have a size determined by the size of the input alphabet Σ , which is constant.
The number of operations required to multiply two Boolean matrices with a circuit of depth
κ log

{ n i , j ( x ) | ≤ i , j ≤| Q |}

Proof The circuits realizing the Boolean functions 1

3 .)
Finally, the prefix circuit uses O ( T ) copies of the matrix multiplication circuit and has a
depth of O (log T ) copies of the matrix multiplication circuit along the longest path. (See
Section 2.6 .)

| Q |

, κ

≥

1, is M matrix (

| Q |

, κ ) .(SeeSection 6.3 .Notethat M matrix (

| Q |

, κ )

≤| Q |

When an FSM has a large number of states but its next-state function is relatively simple,
that is, it has a size that is at worst a polynomial in log

,theabovesizeboundwillbemuch
larger than the size bound given in Theorem 3.1.1 because M matrix ( n , κ ) grows exponentially
in log

| Q |

whereas the depth of the next-
state function on which the depth bound of Theorem 3.1.1 depends will typically grow either
linearly or as a small polynomial in log log

| Q | . The depth bound grows linearly with log | Q |

for an FSM with a relatively simple next-state
function. Thus, the depth bound will be smaller than that of Theorem 3.1.1 for very large
values of T , but for smaller values, the latter bound will dominate.

| Q |