Information Technology Reference
In-Depth Information
Let us observe that it need not be the case that
d
glb
is a waiting period of
Π
for
r
with respect to
∆
. To see this, let us consider the timed protection system
Π
shown in table 7. It is easy to see that for all positive real numbers
d
,5
<d
iff
d
is a waiting period of
Π
for
r
5
with respect to the protection state
∆
defined
by table 1 whereas
Π
is not 5-unsafe for
r
5
with respect to
∆
.
Theorem 3.
1. MIN TIMED SAFETY
(
C
timed
(
∞
,
1))
is solvable,
+
timed
(1
,
2. MIN TIMED SAFETY
(
C
∞
))
is solvable,
+
timed
(2
,
))
is unsolvable.
Proof.
(1) To prove that MIN TIMED SAFETY(
3. MIN TIMED SAFETY
(
C
∞
,
1)) is solvable, let
HRU
(
Π
) be the HRU protection system obtained from
Π
by removing all its
timed constraints “
since at least duration
d
”. If the sequence
∆
0
=(
S
0
,O
0
,A
0
),
...
,
∆
n
=(
S
n
,O
n
,A
n
),
∆
n
+1
=(
S
n
+1
,O
n
+1
,A
n
+1
) of protection states leaks
r
with respect to
HRU
(
Π
)and
∆
then following the line of reasoning suggested
by Harrison, Ruzzo, and Ullman [8], we may assume that
n
C
timed
(
∞
≤
(
|
S
|
+1)
×
(
|
O
|
+
1)
+1, where
∆
=(
S, O, A
) is the given protection state. The corresponding
waiting period necessary if one wants to reach
∆
n
from
∆
0
by performing timed
commands in
Π
is computable in linear time. To finish the proof we only need
to note that the number of requisite waiting periods that we should compute
and compare is finite.
(2) To prove that MIN TIMED SAFETY(
×|
R
|
+
)) is solvable, let
HRU
(
Π
)
be the HRU protection system obtained from
Π
by removing all its timed
constraints “
since at least duration
d
”. If the sequence
∆
0
=(
S
0
,O
0
,A
0
),
...
,
∆
n
=(
S
n
,O
n
,A
n
),
∆
n
+1
=(
S
n
+1
,O
n
+1
,A
n
+1
) of protection states leaks
r
with respect to
HRU
(
Π
)and
∆
then following the line of reasoning suggested
by Harrison and Ruzzo [7], we may assume that
n
C
timed
(1
,
∞
,where
∆
=(
S, O, A
)
is the given protection state. The corresponding waiting period necessary if one
wants to reach
∆
n
from
∆
0
by performing timed commands in
Π
is computable
in linear time. To finish the proof we only need to note that the number of req-
uisite waiting periods that we should compute and compare is finite.
(3) If we had an algorithm
A
for solving MIN TIMED SAFETY(
≤
3
×|
R
|
+
timed
(2
,
))
then we would be able to derive an algorithm for deciding UNIVERSAL TIMED
SAFETY(
C
∞
+
timed
(2
,
)): given input (
r, Π, ∆
), we would be able to decide whe-
ther there exists a positive real number
d
such that
Π
is
d
-unsafe for
r
with
respect to
∆
by simply telling whether
A
(
r, Π, ∆
) is defined. Since UNIVER-
SAL TIMED SAFETY(
C
∞
+
timed
(2
,
C
∞
)) is undecidable, then MIN TIMED SAFE-
+
timed
(2
,
TY(
)) is unsolvable.
Sometimes it is less important to know the greatest lower bound of the set of
all waiting periods of timed protection system
Π
C
∞
∈C
timed
for right
r
than to
know given a positive rational number
d
, that there is no history
h
modelling
Π
and leaking
r
between time points 0 and
d
. This observation leads us to the
following decision problem:
Problem:
BOUND TIMED SAFETY(
C
timed
),
Input:
aright
r
, a timed protection system
Π
∈C
timed
, a protection state
∆
=(
S, O, A
), and a positive rational number
d
,
Output:
determine if
Π
is
d
-unsafe for
r
with respect to
∆
.
