Hardware Reference
In-Depth Information
Fig. 2.6
Largest prefix-closed solution S
D
PS ˘ PC ˘ PR ˘ SS of the converter problem of
Sect. 2.3.2
a1xc - d0cx ), which are deadlocks with respect to the external input Acc ,i.e.,the
composition is not complete. So the largest solution S is not compositionally prefix
.U [ V/-convergent due to the existence of internal cycles, but since the latter can
be exited by selecting the internal output DSis compositionally prefix .U
[ V/-
deadlock-free (and therefore compositionally .I ? O/-progressive).
The protocol conversion problem was addressed in [78], as an instance of
supervisory control of discrete event systems, where the converter language is
restricted to be a sublanguage of the context A, and in [56] with the formalism of
input-output automata. In [78] the problem is modeled by the equation A ˘ X D C
over regular languages with the rectification topology (see Fi g. 1 d). The solution
is given as a sublanguage of A of the form A ˘ C n A ˘ C (not the largest
solution). An algorithm to obtain the largest compositionally progressive solution
is provided that first splits the states of the automaton of the unrestricted solution
(refining procedure, exponential step due to the restriction operator), and then
deletes the states that violate the desired requirement of progressive composition
(linear step). This algorithm does not generalize as it is to topologies where the
unknown component depends also on signals that do not appear in the component A.
 
Search WWH ::




Custom Search