The application of this operator satisfies A S; *post* o)) P S; *post* o)) iff either 1. p and q are true in the state specification, or 2. u and v are true in the state specification, or 3. one of p and q is false and one of u and v is false.

In all other cases, we get A S; *post* o)) 6 P S; *post* o)) and the result is the illegal state. In order to test for this condition in a formalism with complete states we introduce four new sets of atoms:

$$\begin{array}{r l}{p+}&{{}p}\end{array}$$
$\uparrow$  . 
p p ;

+ p+ p ;
 p p ;
 xi;j for the jth conditional effect of oi :
The atom p is true if either p or p is part of the original partial state specification. The atom p+ is set true by an operator if one of the conditional effects adds p or if p does not appear as an effect in the operator. The atom p is set true by an operator if one of the conditional effects deletes p or if p does not appear as an effect in the operator. Finally, atoms of the form xi;j are added by an action if the jth conditional effect in the ith operator is blocked by some effect condition. Using these new atoms, we could translate the above operator to

$${\hat{O}}_{i}$$

oei h>; f fp ; q ; p; q ) p ; p; p ;
$$\begin{array}{l l l l}{{p\ ,\ q\ ,p,}}&{{q}}&{{\Rightarrow}}&{{p\ ,p_{-}\ ,}}\\ {{u\ ,\ v\ ,u,v}}&{{\Rightarrow}}&{{p\ ,p_{-},}}\\ {{p\ ,}}&{{p}}&{{\Rightarrow}}&{{x_{i,1}\ \ ,}}\end{array}$$

q ; q ) xi;1 ;
u ; u ) xi;2 ;
v ; v ) xi;2 ;
) +   p ;

$\rho$. 
) xm;j  m 6 iggi:
Let  i; j be a function that returns p+ or p, if p or p, respectively, is the effect of the jth conditional effect in the ith operator. Assuming now that the atoms from are set according to their intended semantics and that the previous operator deleted all atoms from +  , the following *test* operator checks whether the original operator would have led to an inconsistent result:

test ;

$$x_{i,j},\quad v\,\,i,j\quad\Rightarrow\quad\quad x_{i,j}\quad\Upsilon\left\{\right\}$$
$\uparrow$ . 
:

Whenever we have xi;j , it means the jth conditional effect in the ith operator (which must be the previously executed operator) was not blocked. If in addition to that the effect of this conditional effect was not activated, i.e.,  i; j is true, we would have A S; *post* o)) 6 P S; *post* o)) in the original formalism. For this reason, we force the illegal state. Conversely, if either xi;j is true for all i and j or if it is false for one j, but  i; j is true, we would have A S; *post* o)) P S; *post* o))
in the original formalism and do not need to force the illegal state.

We now could force, by using some extra literals, that after each operator oei the *test* operator is applied. This would result in a compilation scheme that preserves plan size only *linearly*. However, it is possible to do better than that. The key idea is to merge the test operator for the ith step into the operator of step i .