Exploitation of Flexibility in Sequential Networks - The Unknown Component Problem: Theory and Applications - page 223

I 1

O 1

M A 1 M A 4

I 2 O 2

M A 2 M A j M A 5

...

M A 3

O k

M A n

I m

Fig. 14.2 FSM composition

The next proposition characterizes the solutions over a restricted set of input
alphabets: an FSM M C j over the set P [ O is a valid replacement of the FSM M A j

if the following holds.
Proposition 14.4. Given the equation M X M Context Š M Aj M Context ,where

Df I 1 ;:::;I l M Aj is defined over the set of input alphabets I g and of output

Df O 1 ;:::;O r g , and given a proper subset P f I 1 ;:::;I j alphabets O

l g ,
assume that either the composition M A j M Context is loop-free or that M Context
is a Moore FSM. Let M S be the largest FSM solution of the equation over input
alphabets I and output alphabets O .
If there exists a complete deterministic FSM M C j over P [ O such that the
language of the FSM M C j lifted to the set f I 1 ;:::;I l ;O 1 ;:::;O r g is contained in
the language of the largest FSM solution M S ,then M C j can replace the component
FSM M A j without changing the external behavior of the overall system.
If M C j is a Moore FSM, then M C j can replace the component FSM M A j without
changing the external behavior of the overall system, independently of the properties
of the initial composition.

In order to minimize the number of communication wires, we look for a reduction
M C j of the largest FSM solution M S that depends essentially on a minimal number
of input alphabets I 1 ;:::;I l . For this purpose, for each input alphabet I k we check
whether the projection of the FSM M S onto the subset of input alphabets without
I k ,i.e.,I 1 I k 1 I k C 1 I l , satisfies the conditions of Proposition 14.4 .
If it is so, we obtain by projection and determinization the largest FSM solution on
the subset of input alphabets I 1 I k 1 I k C 1 I l ;thenwetryto