Hardware Reference
In-Depth Information
a
b
i
1
/o
1
a
a
2
i
1
v
1
/u
3
o
1
i
1
/o
2
i
2
/o
2
i
1
v
2
/u
1
o
2
i
2
v
1
/u
1
o
2
i
2
v
2
/u
2
o
2
i
2
/o
2
i
3
/o
2
i
3
/o
2
i
3
v
1
/u
2
o
1
i
3
v
2
/u
3
o
2
c
d
u
1
/v
1
u
3
/v
2
i
1
/o
1
u
2
/v
2
u
1
/v
2
as
ap
s
p
i
1
/o
2
i
2
/o
2
u
1
/v
1
u
2
/v
2
i
2
/o
2
u
3
/v
1
i
3
/o
2
i
3
/o
2
u
3
/v
2
Fig. 3.7
Illustration of Example
3.18
.(
a
) Context FSM M
A
;(
b
) Specification FSM M
C
;(
c
)
Largest Solution FSM M
S
;(
d
) M
A
M
S
Š
M
C
a new determinization is needed before performing the final complementation: this
explains the outer exponential 2
j
S
A
j
:2
j
S
C
j
.
There are “easier” topologies, like supervisory control, where there is no projec-
tion onto a subset of signals of the product automaton; therefore non-determinism is
not introduced and so the final complementation is linear, resulting in the complexity
of
j
S
A
j
:2
j
S
C
j
. Moreover, if S
C
is deterministic, the exponential 2
j
S
C
j
is replaced
by
j
S
C
j
, and so the final complexity of supervisory control is bounded by only
j
S
A
j
:
j
S
C
j
.
The operations on the language S to extract from it an FSM language, a complete
FSM language or a Moore solution (see below) are linear in the number of edges of
the automaton representing S .
3.3.2
Restricted FSM Compositional Solutions
It is interesting to compute the subset of compositionally I -progressive solutions
B, i.e., such that A
"
I
2
O
2
\
B
"
I
1
O
1
is an I -progressive FSM language
.I
U
V
O/
?
. Thus the composition (after projection on the external signals) 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
\
S
FSM
"
I
1
O
1
is prefix-closed and hence corresponds to a partial FSM, we have
to restrict it so that it is also I -progressive, which corresponds to a complete FSM.
Search WWH ::
Custom Search