Information Technology Reference
In-Depth Information
E
is an
m
1 column vector of nonnegative
integers.
M
and
M
0
denote the current and initial markings, respectively.
x
is called the firing count vector and the
j
th element of
x
denotes
the number of times that
t
j
must fire to transform
M
0
to
M
. The state-
shift equation can be easily transformed to another type denoted by
Ax
m
unit matrix.
x
is an
n
ð
p
p
Þ
to denote the
k
th fired input
transition and the
l
th fired output transition of
p
, we can rewrite the
state-shift equation as
M
0
ð
¼
M
M
0
. If we use
Þ
and
ð
Þ
P
ð
p
þ
P
ð
k
l
.
p
Þ
p
Þ¼
M
ð
p
Þ
5.3.3 Definition of Subgraphs and Solutions
In this section, we define subgraphs in an SC-net and solutions for the
state-shift equation and clarify the relationship between the structural
properties of subgraphs and the algebraic characteristics of solutions.
Definition 5.9.
In an SC-net, a subgraph that corresponds to a realizable
configuration process (CP) consists of the fired transitions, their input
places, and the nonzero element of current marking
M
.
For example, for the SC-net in Figure 5.3, a realizable CP can be
p
0
g;
p
0
;
CP
1
¼fð
P
;
T
Þj
P
¼f
T
¼
1
g
,
CP
2
¼fð
P
;
T
Þj
P
¼f
p
1
g;
T
¼
t
3
gg
.InCP,
p
0
has single output arc and the other nonleaf place has single input arc and
single output arc.
p
0
;
f
t
1
gg
or
CP
3
¼fð
P
;
T
Þj
P
¼f
p
1
;
p
3
;
p
4
g;
T
¼f
t
1
;
Theorem 5.2.
The set of places of a CP in which no transition can be
enabled under M is a candidate SFC
.
Proof:
Since
p
0
does not have any input arc and
M
0
ð
p
0
Þ¼
1.
1, we have
p
0
Þþ
P
ð
1or
P
ð
p
0
Þ
l
p
0
Þ
l
p
0
Þ¼
M
1, which
means the set of places of CP contains
p
0
. This satisfies property
(a) of SFC in Definition 5.5.
ð
¼
1. Then
M
ð
¼
2.
Without
loss
of
generality,
suppose
that
M
0
½
t
1
>
M
1
½
t
2
>
M
2
...
½
M
. Since each transition has only one input arc,
suppose that the input places of the fired transitions are
p
0
,
p
1
,
p
2
, . . . , denoted as a place set
P
F
. Since no transition under
M
can be enabled,
t
n
>
p
i
,
t
iþ
1
,
p
is i
n
8
p
i
2
P
F
in CP,
9
t
iþ
1
2
8
p
2
P
F
or
M
ð
p
Þ >
0. This satisfies property (b) of SFC.