Information Technology Reference
In-Depth Information
ʩ
Suppose thus that
P
nr
must
Q
, then
P
,
Q
are distinguished by some
ʩ
-test
T
∈ T
n
[0, 1]
ʩ
, so that
and reward
h
∈
h
(
T
,
P
)
h
(
T
,
Q
)
.
A
≤
A
(4.26)
Without loss of generality, assume that the success actions in
T
are
ˉ
1
,
...
,
ˉ
n
.We
construct a new test
T
with only one success action
ˉ
as follows. For each transition
s
ʱ
−ₒ
can perform a success action, we keep this transition;
otherwise, we form a distribution
ʔ
to substitute for
ʔ
in this transition.
ʔ
in
T
, if no state in
ʔ
1. First we partition
ʔ
into two disjoint sets
{
s
i
}
i
∈
I
and
{
s
j
}
j
∈
J
. For each
i
∈
I
,
ˉ
i
−ₒ
ʔ
i
for some distribution
ʔ
i
and success action
ˉ
i
; for each
j
∈
J
, no success action is possible from
s
j
.
2. Next, we introduce a new state
s
to replace the states in the first state set, together
with a deadlock state
u
.Soweset
we have
s
i
ʔ
s
,
u
:
={
s
j
}
j
∈
J
∪{
}
and
i
∈
I
h
(
ˉ
i
)
ʔ
(
s
):
=
·
ʔ
(
s
i
)
ʔ
(
s
j
):
=
ʔ
(
s
j
)
for each
j
∈
J
j
∈
J
ʔ
(
s
j
)
.
ʔ
(
u
):
ʔ
(
s
)
=
1
−
−
ˉ
−ₒ
3. Finally, a new transition
s
u
is added.
We do similar modifications for other transitions in
T
. Since there are finitely many
transitions in total, the above procedure will terminate and result in a new test
T
.
The effect of changing
T
into
T
is to replace each occurrence of
ˉ
i
by
ˉ
with
discount factor
h
(
ˉ
i
) (the other part 1
h
(
ˉ
i
) is consumed by a deadlock). For any
process
P
, the overall probability of
ˉ
's occurrence, in any resolution of [[
T
|
Act
P
]] ,
is therefore the
h
-weighted reward
h
−
·
o
for the tuple
o
in the corresponding resolution
of [[
T
|
Act
P
]] .
Thus from (
4.26
), we have that
P
,
Q
can be distinguished using the scalar test
T
with its single success action
ˉ
; that is, we achieve
P
We are now in a position to prove that scalar testing is as powerful as finite-
dimensional vector-based testing.
nr
must
Q
as required.
Theorem 4.7
For any n
∈ N
and finitary processes P
,
Q, we have
pmay
Q
pmay
Q
P
iff
P
pmust
Q
P
iff
P
pmust
Q.
Proof
Combining Theorems
4.5
and
4.6
yields the coincidence of
pmay
with
nr
may
,
pmay
is the
no matter what is the size of
ʩ
, as long as it is finite. It follows that
same as
pmay
. The must case is similar.
Search WWH ::
Custom Search