Information Technology Reference
In-Depth Information
with eect E = f
s 1 ) g . Then the only causal minimizing-change succes-
sor of S and a is T = f
(
up
g . For (( S \ T ) [ E;E )=
( f up ( s 2 ) ; up ( s 1 ) g; f up ( s 1 ) g ) allows to derive light . In contrast, the unin-
tended T 0 = f up ( s 1 ) ; : up ( s 2 ) ; : light g does not satisfy Equation (2.11).
For (( S \ T 0 ) [ E;E )=( f: light ; up ( s 1 ) g; f up ( s 1 ) g ), which does not allow
for deriving :
(
s 1 ) ;
(
s 2 ) ;
up
up
light
s 2 ), i.e., the literal which is missing to regain T 0 . 16
The following observation justies formally our name \minimizing-change
successor." Namely, any state T satisfying Equation (2.11) has minimal dis-
tance from S in that there is no state T 0
(
up
with less (wrt. set inclusion)
changes while also satisfying this equation.
Observation 2.6.1. Let E and F be sets of entities and fluent names, R
a set of causal relationships, S a state, and E a consistent set of fluent
literals. For any two xpoints T;T 0
of T: f` :(( S \ T ) [ E;E ) R `g,if
T n S T 0 n S, then T = T 0 .
Proof. Since each of S; T; T 0 is a state, T n S = T 0 n S implies T = T 0 .
The assumption T n S ! T 0 n S leads to the following contradiction. Let
` 2 T n S such that ` 62 T 0 n S , then ` 2 T and ` 62 S , hence :` 2 S
and :` 2 T 0 as both S and T 0 are states. Since T 0 is consistent and
xpoint, we have (( S \ T 0 ) [ E;E ) 1 R ` due to :` 2 T 0 . On the other hand,
we know that (( S \ T ) [ E;E ) R ` due to ` 2 T . Operator R being
monotonic, (( S \ T 0 ) [ E;E ) 1 R ` and (( S \ T ) [ E;E ) R ` together imply
S \ T 6 S \ T 0 . Thus we can nd some ` 0 2 S; T such that ` 0 62 T 0 . Then
:` 0 62 S; T and :` 0 2 T 0 , which contradicts premise T n S T 0 n S .
Qed.
Before we enter the analysis of the relation between minimization based
on causal relationships on the one hand, and their operating on preliminary
successors on the other hand, we present an iterative characterization of the-
ories induced by causal relationships. This alternative view will be helpful for
later purpose.
Proposition 2.6.1. Let E and F be sets of entities and fluent names,
respectively, and R a set of causal relationships. For each pair ( Ψ; ) con-
sisting of a set of fluent formulas and a set of fluent literals, we dene
1. Ψ 0 = Ψ and 0 = .
2. For i> 0 ,
a) Ψ i = Th ( Ψ i− 1 ) [f% : " causes % if 2R;2 Ψ i− 1 ;%62 Ψ i− 1 ;"2 i− 1 g
b) i = i− 1 [f% : " causes % if 2R;2 Ψ i− 1 ;%62 Ψ i− 1 ;"2 i− 1 g
Then
Ψ = S i =0 Ψ i and
= S i =0 i , where ( Ψ; ^ )= Th R ( Ψ; ) .
^
16
It is also interesting to see why T 00 = f up ( s 1 ) ; up ( s 2 ) ; : light g , where only
the direct eect is computed, does not satisfy (2.11): Pair (( S \ T 00 ) [ E; E )=
( f up ( s 2 ) ; : light ; up ( s 1 ) g; f up ( s 1 ) g ) additionally entails light with the help
of R . Thus, T 00 is not a xpoint. This illustrates that all material implica-
tions ^ " % induced by some causal relationship " causes % if hold in
minimizing-change successors.
Search WWH ::




Custom Search