Information Technology Reference
In-Depth Information
from state constraints, i.e., by avoiding the roundabout way of constructing
normal forms. On the other hand, the generation of causal relationships is
a pre-processing step which is carried out only once for a xed set of state
constraints. This computational eort is therefore of minor importance.
Talking about complexity, a related crucial issue concerns the number of
causal relationships generated from a set of state constraints. This number
is, in the worst case, exponential as regards the size of the input. The rea-
son is that formulas exist which admit only CNF's of exponentially increased
length. Moreover, up to quadratic many relationships exist for a single con-
junct, namely, if all involved fluents have the potential to aect each other.
Despite this negative result, fortunately there is a decisive characteristic due
to which especially in large domains the number of relationships is small
compared to the worst case: The state constraints do not interfere when de-
termining causal relationships. In general, large domains tend to be locally
structured in that each single state constraint relates only a small fraction
of the entire set of fluents. More precisely, let
k
be the maximum size of a
state constraint
13
and
n
their overall number. Then the number of required
causal relationships is of magnitude
O
(2
k
n
). Granted that
k
remains con-
stant with increasing domain size, the number of causal relationships thus
is linear in the number of state constraints. E.g., in our example involving
n
sub-circuits (recall Fig. 2.2), each of the
n
state constraints relates only
three fluents. Consequently, as we have seen (c.f. (2.8)) they give rise to a
linear number of causal relationships (4
n
, to be precise). Incidentally, the
fact that state constraints do not interfere in determining causal relationships
solves the second problem mentioned in the introduction to the Ramication
Problem. No existing causal relationship requires modication or needs to be
removed if state constraints are added. Introducing a new switch-bulb pair
up
(
s
n
+1
)
;
light
n
+1
in the example just mentioned, for instance, amounts to
adding four new causal relationships but requires no further changes.
Thus far we have conned ourselves to the extraction of causal relation-
ships from quantier-free state constraints. As for the general case, notice
rst that since we assume niteness of sets of entities
E
, it is always possible
to rewrite any state constraint so as to become quantier-free. Namely, each
sub-formula
8x: F
V
e2E
F fx 7! eg
, and each sub-formula
is replaced by
9x: F
is replaced by
W
e2E
F fx 7! eg
. Awkward as it is, this is unavoidable
when dealing with unrestricted state constraints and influence information.
To see why, consider some arbitrary formula like
8x9y8z: f
(
x; y; z
) as state
constraint. Which causal relationships are determined by this constraints de-
pends on how the various possible instances
f
(
e
1
;e
2
;e
3
) interact. Each of
the instances may behave dierently with this respect. In general, therefore,
there is no better way than grounding a state constraint and proceeding as
above. On the other hand, it is possible to exploit the expressiveness of causal
relationships having variables in case a state constraint and influence infor-
mation obey well-dened restrictions. In the following, we discuss two such
13
As the size of a formula we take the number of literal occurrences.
