Information Technology Reference
In-Depth Information
where executing
σ
will not impact the result of the synthesis, is utilized to minimize the
guards.
Algorithms 4 and 5 presented below show how to compute the forbidden states
Q
f
and the allowed states
Q
a
by making use of the disjunctive transition functions. Note
that
Q
S
and
Q
x
denote the resultant supervisor states and all the forbidden states yielded
from Algorithm 1. The don't care state set,
Q
dc
can be defined as the complement of
the union of
Q
a
and
Q
f
. The proof can be found in [8].
5.2
Guard Generation
Based on the basic state sets, guards can be extracted. For every automaton in the DES,
anewvariable
v
is introduced to hold the current state of the automaton. For each event
σ
, the following propositional function,
G
σ
:
Q
A
1
Q
A
2
Q
A
n
×
×
...
×
→
B
is defined
as:
⎧
⎨
true
v
A
1
,v
A
2
,...v
A
n
∈
Q
a
G
σ
false
v
A
1
,v
A
2
,...v
A
n
∈
Q
f
v
A
1
,v
A
2
,...v
A
n
=
(9)
⎩
don
tcareotherwise
.
where
is the set of Boolean values and
v
A
i
represents the current state of automaton
A
i
. In particular,
σ
is allowed to be executed from the state
B
v
A
1
,v
A
2
,...v
A
n
if the
guard is true.
By applying minimization methods of Boolean functions (utilizing the don't care
state set) and certain heuristics, the generated guards can be simplified. The procedure
is discussed in details in [8].
Algorithm 4 .
Computation of
Q
f
.
1:
input
:
σ, Q
x
,Q
S
, {
δ
1
,...,δ
n
}
2:
let
Q
σ
f
:=
∅
;
3:
for all
A
i
if
σ ∈ Σ
i
do
4:
Q
x
, δ
i
(
q,σ
)=
q
Q
σ
f
:=
Q
σ
f
∪{
q
|∃
q
∈
}
;
5:
end for
6:
let
Q
σ
f
:=
Q
σ
f
∩ Q
S
;
7:
return
Q
σ
f
Algorithm 5 .
Computation of
Q
a
.
1:
input
:
σ, Q
S
, {
δ
1
,...,δ
n
}
2:
let
Q
σ
a
:=
∅
;
3:
for all
A
i
if
σ ∈ Σ
i
do
4:
a
∪{q |∃q ∈ Q
S
, δ
i
(
q,σ
)=
q}
;
Q
σ
a
:=
Q
σ
5:
end for
6:
let
Q
σ
a
:=
Q
σ
a
∩ Q
S
;
7:
return
Q
σ
a
