Hardware Reference
In-Depth Information
the FSM yielded by the composition of FSMs M
A
and M
B
is the one whose
language is obtained by the composition of the FSM languages associated with
M
A
and M
B
. The synchronous composition operator models the synchronous
connection of sequential circuits, while the parallel composition operator models
an exchange protocol by which an input is followed by an output after a finite
exchange of internal signals. The latter model, introduced in [107], abstracts a
system with two components and a single message in transit. At any moment
either the components exchange messages or one of them communicates with its
environment. The environment submits the next external input to the system only
after the system has produced an external output in response to the previous input.
3.2.1
Synchronous Composition of FSMs
Consider the pair of FSMs:
1. FSM M
A
has input alphabet I
1
V , output alphabet U
O
1
, and transition
relation T
A
.
2. FSM M
B
has input alphabet I
2
U , output alphabet V
O
2
, and transition
relation T
B
.
We define a synchronous composition operator
that associates with a pair of FSMs
M
A
and M
B
another FSM M
A
M
B
such that:
1. The external input alphabet is I
1
I
2
D
I .
2. The external output alphabet is O
1
O
2
D
O.
The topology for this is shown in Fig. 1a (a variant is in Fig. 1f).
3
Recall that, by
definition of synchronous composition of languages, a sequence ˛
2
.I
1
I
2
O
1
O
2
/
?
is in the language of the synchronous composition of L.M
A
/ and L.M
B
/ iff
˛ is in the projection onto I
1
I
2
O
1
O
2
of the intersection of the lifting of
L.M
A
/ over I
2
O
2
and of the lifting of L.M
B
/ over I
1
O
1
4
:
˛
2
L.M
A
/
L.M
B
/ iff
˛
2
ŒL.M
A
/
"
I
2
O
2
\
L.M
B
/
"
I
1
O
1
#
I
O
:
Notice that the liftings L.M
A
/
"
I
2
O
2
and L.M
B
/
"
I
1
O
1
are needed to have the
languages of M
A
and M
B
defined on the same alphabet; e.g., L.M
B
/ is defined over
I
2
U
V
O
2
, and the lifting
"
I
1
O
1
defines it over I
1
I
2
U
V
O
1
O
2
.
3
Notice that more complex topologies can be handled in the same way, by defining the com-
positions with respect to the appropriate sets of variables, as pointed out when introducing the
composition of automata.
4
Use the same order I
1
I
2
U
V
O
1
O
2
in the languages L.M
A
/
"
I
2
O
2
and L.M
B
/
"
I
1
O
1
.
Search WWH ::
Custom Search