Information Technology Reference
In-Depth Information
{ In case
j
=1
;k
= 2 we have (
(
s
3
)
;
)
2I
, which yields
up
relay
:
(
s
3
) causes
:
if
>
up
relay
{ In case
j
=2
;k
= 1 we have (
relay
;
up
(
s
3
))
62 I
.
3. The minimal CNF of
relay
:
up
(
s
2
)is
:
relay
_:
up
(
s
2
)
Regarding the only conjunct
C
1
=
:
relay
_:
up
(
s
2
) we obtain the
following:
{ In case
j
=1
;k
= 2 we have (
relay
;
up
(
s
2
))
2I
, which yields
relay
causes
:
up
(
s
2
) f
>
{ In case
j
=2
;k
= 1 we have (
)
62 I
.
Altogether, the output is exactly the nine causal relationships which we have
obtained in the preceding section by intuitive analysis of causal dependencies.
up
(
s
2
)
;
relay
As a small exercise, the reader may verify that the algorithm applied to the
switches and spring-domain (Example 2.4.1 and Fig. 2.5) as well produces
the correct outcome: The input consisting of the state constraint
s
1
)
up
(
s
2
) and influence information
I
=
f
(
up
(
s
1
)
;
up
(
s
2
))
;
(
up
(
s
2
)
;
up
(
s
1
))
g
results in the output of all four expected causal relationships, (2.4).
The causal relationships
"
causes
%
if
generated by our procedure all
have a restricted syntax. Namely, context
is a conjunction of fluent literals
instead of an arbitrarily complex fluent formula. This does not imply, how-
ever, that some causal information otherwise being representable cannot be
obtained through automatic generation. This is so, because any causal rela-
tionship can be transformed into an operationally equivalent set of causal rela-
tionships which obey the restriction. For suppose
1
_:::_
n
is a disjunctive
normal form (DNF, for short)
12
of some formula
Ψ
, then a causal relation-
ship
"
causes
%
if
Ψ
and the collection
"
causes
%
if
1
; :::; "
causes
%
if
n
are interchangeable. On the other hand, in certain cases exploiting full ex-
pressiveness leads to considerably more compact representations. This can
be accomplished by considering all automatically extracted causal relation-
ships for a particular
"
and
%
, i.e.,
"
causes
%
if
1
; :::; "
causes
%
if
n
,
and constructing formula
Ψ
as compact equivalent of
1
_ :::_
n
. Then
"
causes
%
if
Ψ
replaces the aforementioned
n
relationships. This rst trans-
forming state constraints into a normal form, then extracting causal rela-
tionships, and nally retransforming the result into non-normal form may of
course require extensive computation. In certain cases it might be much faster
to employ more sophisticated means to straightly extract causal relationships
(
up
12
On the analogy of CNF, a DNF of a formula is some logical equivalent of the
form
D
1
_ :::_ D
n
(
n
1) such that each
D
i
is of the form
`
i
1
^ :::^ `
im
i
(
m
i
1) with each
`
ij
being a fluent literal.