A Survey of Relevant Literature - The Unknown Component Problem: Theory and Applications - page 85

possible languages generated by M A by changing the output function, but keeping
the state transition function unchanged . Say that M A has k transition edges and
an output alphabet U with

k possible
output functions, if its transition function is kept unchanged. For each such output
function 0 1 one must check whether the corresponding FSM M A is such that
M A ! M B D M A ! M B .
Comparing Wang's and Rho's procedures, the former implicitly enumerates
infinite-length output don't care sequences, but it is restricted by the assumption
that the state transition function must be kept unchanged; the latter is restricted to
sequences of finite-length and also uses a restricted notion of equivalent sequences.
So neither procedure is complete.

j U j symbols, then M A may produce j U j

5.1.3.2 Computation of Complete Output Don't Care Sequences

in a Series Topology

The complete flexibility for the head FSM of a series composition was derived by
Yevtushenko and Petrenko [111, 112, 152] by means of a NDFSM whose states are
the Cartesian product of the components' states, and whose transition relation is
unspecified for the inputs such that no internal signal produces the reference output,
otherwise it includes all transitions with allowed internal signals.
The first result [152] solved the special case of Moore FSMs where the
tail component produces different outputs for different states. Consider a series
composition M A ! M B of two Moore FSMs M A D .S A ;I;U;ı A ; A ;r A / and
M B D .S B ;U;O;ı B ; B ;r B /, such that 8 s 1 ;s 2 2 S B s 1 ¤ s 2 implies B .s 1 / ¤
B .s 2 /. The FSM representing all behaviors that can be realized at the head
component is given by the NDFSM M D D .S A S B ;I;U;ı D ; D ;.r A ;r B //,where
ı D ..s A ;s B /;i/ D .ı A .s A ;i/;ı B .s B ; A .s A /// and D .s A ;s B / Df u j ı B .s B ;y/ D
ı B .s B ; A .s A // g , i.e., the output of M D at state .s A ;s B / is the set of u 2 U that drive
M 2 from s B into the same state to which A .s A / does.
Theorem 5.2. [152] M C ! M B D M A ! M B iff M C is a reduction of M D .
The method was then extended to arbitrary tail machines through two more
contributions [111, 112]. The first one described in [112] proposes an algorithm
for output don't care sequences dual to the one by Kim and Newborn for input don't
care sequences.
Consider a series composition M A ! M B of two FSMs M A D .S A ;I;U;ı A ;
A ;r A / and M B D .S B ;U;O;ı B ; B ;r B /. The FSM representing all classes of
input sequences of M B equivalent with respect to M B (M B produces the same
output sequence under these input sequences, which are the don't care output
sequences of M A ) is given by the NDFSM M D D .S B S B ;U;U;T;.r B ;r B //,
where the transition ..s B ; s B /; u 1 ; u 2 ;.s 0 B ; s 0 B // 2 T iff B .s B ; u 1 / D B .s B ; u 2 /,
s 0 B D ı B .s B ; u 1 / and s 0 B D ı B .s B ; u 2 /. In other words, the output sequences
produced by FSM M D under a given input sequence ˛ are those under which M B
produces the same output sequence that it generates under ˛.