Hardware Reference
In-Depth Information
Due to the commutative and associative properties of the composition operator,
Proposition
12.6
can be extended to more than two equations. This suggests the
following procedure to solve a system of FSM equations:
Procedure 12.3.1.
Input: System of FSM equations
M
X
M
A
j
Š M
C
j
,
j
D
1;:::;k
; Output: Largest complete FSM solution
M
S
of the system of FSM
equations.
1. Compute the largest solution
M
S
j
of each equation
M
X
M
A
j
Š M
C
j
,
j D
.
2. The largest complete submachine of the intersection
1;:::;k
M
S
D\
j D1
M
S
j
(if it
exists) is the largest complete solution of the system.
To compare the efficiency of solving a system of FSM equations vs. solving a
single monolithic equation, consider the topology shown in Fig.
12.5
.Inorderto
capture all the FSMs that can replace the head machine
M
F
we set up the equation
M
X
.M
D
M
E
/ Š M
F
M
D
M
E
. Given the complete and deterministic
machines
M
F
;M
D
and
M
E
and the largest complete solution
M
S
of the equation
over alphabets
I
and
V
(it is solvable because there is at least the solution
M
F
),
each complete and deterministic reduction of
M
S
can replace the FSM
M
F
in the
composition, i.e., given a complete and deterministic FSM
M
K
such that
M
K
is a
reduction of
M
K
M
D
M
E
Š M
F
M
D
M
E
. However, notice
that the numbers of states of the machines
M
S
it holds that
M
F
M
D
M
E
and
M
D
M
E
are equal,
respectively, to
.
Since by Theorem
12.2.2
an FSM is a solution of the equation
jS
F
jjS
D
jjS
E
j
and
jS
D
jjS
E
j
M
X
.M
D
M
E
/ Š M
F
M
D
M
E
if and only if it is a solution of the system of equations
M
X
M
D
Š M
F
M
D
M
X
M
E
Š M
F
M
E
, we can replace the single
monolithic equation by the system of two equations
and
M
X
M
D
Š M
F
M
D
and
M
X
M
E
Š M
F
M
E
.
When a system of equations is solved instead of a monolithic equation the worst-
case complexity of computing the largest solution does not decrease. The reason
is that to obtain the largest solution of the system of equations we need to build
the product of the components of the single equations (respectively,
jS
F
jjS
D
j
and
jS
F
jjS
E
j
). However, since
each single equation of the system has a smaller worst-case complexity, when the
reduced largest solutions of the single equations are smaller than their worst-case
complexity, equations involving FSMs of larger sizes may be solved.
) and then to intersect them (
jS
F
jjS
D
jjS
F
jjS
E
j
Example 12.7.
Consider the FSMs
M
F
;M
D
and
M
E
in Fig.
12.7
a-c. By direct
inspection one can check that the largest solutions
M
S
D
and
M
S
E
to the FSM
equations
M
X
M
D
Š M
F
M
D
and
M
X
M
E
Š M
F
M
E
are isomorphic
to the FSM
M
F
. Therefore, their intersection is also isomorphic to
M
F
. Thus, each
FSM that is not equivalent to
M
F
changes the external behavior of the composition,
i.e.,
M
F
cannot be replaced without changing the behavior of the overall system.
Instead, when solving a single equation, we have to build the FSMs
M
D
M
E
and
Search WWH ::
Custom Search