Information Technology Reference
In-Depth Information
3Hyp rMod s
Here is an example to motivate our definition of hyper models:
You have noideahow four cities
A, B, C, D
are connected (by train or bus). Now
suppose thatsomeone tells you thatthere is a bus going to either
B
or
C
from
A
,there
is a train connection from
C
to
D
, and all thebuses departing from
B
are going to
C
.
Nowwhatdoyouknowabouttheroute from
A
to
D
?
Again, let
b
denote the bus connections and let
t
denote the train connections. Let
p
x
be the basic proposition denoting the location of town
x
for
x
∈{
A, B, C, D
}
.The
imperfect procedural information can be formalized as:
p
A
,b
∃
,p
B
∨
p
C
,t
∃
,p
D
p
B
,b
∀
,p
C
p
C
,
,
.
The simple-minded learning process is to add those information as special transitions
in the map, as illustrated below (note that the
b
∃
transition is from
A
to
{
B,C
}
):
=
⃒
A
B
A
B
b
∀
b
∃
t
∃
D
C
D
C
Given that the information is truthful, the real situation is still not yet determined,
for example, the following are three of the possible actual situations consistent with the
information available:
b
A
B
A
B
A
B
t
b
t
b
b
t
b
b
b
D
C
D
C
D
C
t
t
t
However, the agent should
know
the following, which may help him to goto
D
from
A
:
There is a busfrom
A
to either
B
or
C
, andifitreaches
C
then
D
can be reached
byatrain,otherwise take any bus(ifavailable) from
B
to get
C
first in order to reach
D
finally.
In the rest of this section, we will introduce hyper models formally, and a semantics
for
epistemic PDL
(
EPDL
) based on them to reason about knowledge of procedures.
3.1
Models with Simple Procedural Information
This subsection is a technical warm-up for the next one. We only consider simple proce-
dures (
a
∀
or
a
∃
) based on singleton sets of initial states. To represent such information,
we introduce the
simple hyper models
based on Kripke models with extra transitions
labelled by
a
∀
or
a
∃
from a
single
state to a
set
of states: