The scheme f obviously satisfies conditions (2) and (3), all the functions can be computed in polynomial time, and F () is a S-instance.

Let S  . Then it is obvious that ti(; R S; o)) R ti(; S ; oe :
Let ehfo1; : : : ; ofni denote a sequence of operators corresponding to a sequence of operators ho1; : : : ; oni. Using induction on plan length, it is easy to show that is a plan for iff eis a plan for F (),
i.e., condition (1) on compilation schemes is also satisfied. This means, f is in fact a compilation scheme. Further, since the plan size does not change, the compilation scheme preserves plan size exactly. Finally, because all functions in f can be computed in time polynomial in their arguments, f is a polynomial-time compilation scheme.

One view on this result is that it does not matter whether, from an expressivity point of view, we allow for atoms only or for literals and it does not matter whether we have complete or partial state specification—provided propositional formulae and conditional effects are not allowed.

## 4.2 Planning Formalisms With Conditional Effects But Without Boolean Formulae

Interestingly, the view spelled out above generalizes to the case where conditional effects are allowed. Also in this case it does not matter whether only atoms or also literals are allowed and whether we have partial or complete state specifications. In proving that, however, there are two additional complications. Firstly, one must compile conditional effects over partial state specifications to conditional effects over complete state specifications. This is a problem because the condition A S; *post* o)) P S; *post* o)) in the definition of the function R must be tested. Secondly, when compiling a formalism with literals into a formalism that allows for atoms only, the condition A S; *post* o)) 6j in the definition of R must be taken care of. For this reason, we will prove this result in two steps.

As a first step, we show that SLIC can be compiled to SLC . The problem in specifying such a compilation scheme is that the execution of an operator o on a partial state specification leads to the illegal state if A S; *post* o)) 6 P S; *post* o)).

When considering our running example (Ex. 1), things are quite obvious. When a state specification does not contain the literal or the negation of the literal that is mentioned in the effect condition, then the illegal state specification results. For example, if a state specification does neither contain bbl nor bbl, then the result of executing latex is . In the general case, however, things are less straightforward because effect literals can be produced by more than one conditional rule and an effect condition can consist of more than one literal.

Assuming without loss of generality (using a polynomial transformation) that the effects are all singleton sets, we have to check the following condition. Either one of the conditional effects with the same effect literal is activated—i.e., the effect condition is entailed by the partial stateor all of the conditional effects with the same effect literal are *blocked*, i.e., each effect condition contains a literal that is inconsistent with the state specification. If this is true, the original operator satisfies A S; *post* o)) P S; *post* o)), otherwise the resulting state specification is inconsistent.

For example, consider the following SLIC operator:

$$\left\langle\quad,\quad p\,,\quad q\quad\Rightarrow\quad\quad p\ \,,\quad u,\,v\quad\Rightarrow\quad$$

oi h>; ffp; q ) f:p ; u; v ) f:pggi: