Hardware Reference
In-Depth Information
Proposition 3.30.
FSM
M
B
is a solution of the equation
M
A
˘
M
X
M
C
,where
M
A
and
M
C
are FSMs, iff
M
B
is a reduction of the FSM
M
S
FSM
associated to
S
FSM
,where
S
FSM
is obtained by applying Procedure
3.1.3
to
S
,where
S
D
A
˘
.C
D;
then no FSM solution exists.
The largest complete FSM solution
M
Prog.S
FSM
/
\
.IO/
?
/
.If
S
FSM
is found, if it exists, by
Procedure
3.1.4
.
A complete FSM is a solution of
M
A
˘
M
X
M
C
iff it is a reduction of the
largest complete solution
M
Prog.S
FSM
/
.
Given the largest (complete) solution
M
Prog.S
FSM
/
of the equation
M
A
˘
M
X
M
C
,let
M
A
˘
M
X
Š
M
C
.Then
M
Prog.S
FSM
/
is the largest (complete) solution of
the equation
M
A
˘
M
X
Š
M
C
.
The worst-case complexity of computing the largest solution of a parallel
equation is of 2
j
S
A
j
:2
j
S
C
j
, the same as for a synchronous equation. The same analysis
applies (restriction plays the same role as projection in introducing nondetermin-
ism).
3.4.2
Restricted FSM Compositional Solutions
It is interesting to compute the subset of compositionally I
?
O-progressive solutions
B, i.e., such that A
*
I
2
[
O
2
\
B
*
I
1
[
O
1
\
.IO/
?
*
U
[
V
is an I.U
[
V/
?
O-progressive
FSM language
.I.U
[
V/
?
O/
?
. Thus the composition (after restriction to I
[
O)
is the language of a complete FSM over inputs I
1
[
I
2
and outputs O
1
[
O
2
.Since
A
*
I
2
[
O
2
\
.IO/
?
*
U
[
V
(after restriction to I
[
O)isIO-prefix-closed
and hence corresponds to a partial FSM, we have to restrict it so that it is also
I.U
[
V/
?
O-progressive, which corresponds to a complete FSM.
If S
FSM
is compositionally I.U
[
V/
?
O-progressive, then S
FSM
is the largest
compositionally I.U
[
V/
?
O-progressive solution of the equation. However, not
every non-empty subset of S
FSM
inherits the feature of being compositionally
I.U
[
V/
?
O-progressive. If S
FSM
is not compositionally I.U
[
V/
?
O-progressive,
then denote the largest compositionally I.U
\
B
*
I
1
[
O
1
[
V/
?
O-progressive subset of S
FSM
[
V/
?
OP r og.S
FSM
/. Conceptually, the language cI.U
[
V/
?
OP r og
by cI.U
.S
FSM
/ is obtained from S
FSM
by deleting each string ˛ such that, for some i
2
I ,
there is no .
u
[
v
/
?
[
V/
?
and no o
2
O for which ˛i.
u
[
v
/
?
o
2
A
*
I
2
[
O
2
\
2
.U
S
FSM
*
I
1
[
O
1
.IO/
?
*
U
[
V
holds. We expect that a procedure to compute the largest
compositionally I.U
[
V/
?
O-progressive prefix-closed solution, cP rog.S
FSM
/,
can be designed following the pattern of Procedure
3.3.1
, but as yet have not worked
out the details. A procedure to compute the largest compositionally progressive
solution of a parallel equation over regular languages for the rectification topology
was provided in [78].
To characterize subsets of solutions well-behaved with respect to deadlocks and
livelocks (endless cycles of internal actions), we introduce a few more language
definitions.
\
Search WWH ::
Custom Search