Lemma 7 SLIC *is polynomial-time compilable to* SLC *preserving plan size exactly.* Proof. Let h ; I; Gi be a SLIC -instance with h ; Oi. Without loss of generality, we assume that the postconditions of operators oi O have the following form:

```
post oi Li;1 ) l
                    i;1; : : : ; Li;mi ) li;mi
                                         
                                          ;
                                           

```

with Li;j  and l i;j .

First, we introduce a number of new sets of symbols that are pairwise disjoint and disjoint from
:
p p ;

0 1

```
+ p
       0
       
       + p ; + p
       1
       
       + p ;

 p
        0
         
         p ;

 p
        1
         
         p ;

```

0 x0 i;j for the jth conditional effect of oi ;
1 x1 i;j for the jth conditional effect of oi :
For a given set of literals L  , L denotes the set of primed literals, i.e., L p p L
f:p p L and the function s  denotes the successor function modulo 2, i.e., s k k 1) mod 2. Further, the functions kfor k ; shall be functions from kto k
+
k such that

0

1

$$v^{k}\,\,\,i,\,j\qquad\left\{\begin{array}{l l l l}{{q_{+}^{k}}}&{{\quad\;\;\;\;k\;\;\;\mathrm{if}\;\;\;L_{i,\,j}\Rightarrow q\;\;\;\;\;\;p o s t\,\,o_{i}\;\;,}}\\ {{q_{-}^{k}}}&{{\quad\;\;\;\;k\;\;\;\;\mathrm{if}\;\;\;L_{i,\,j}\Rightarrow\;\;\;\;q\;\;\;\;\;\;p o s t\,\,o_{i}\;\;.}}\end{array}\right.$$

Now let *post*koi for k ; be defined as follows postkoi L  L ) p; p ; pk
+ p ; L ) p *post* oi L  L ) f:p; p ; pk p ; L ) p *post* oi ;
let *block*koi for k ; be defined as

$$\begin{array}{c c c}{{x^{k}}}&{{o_{i}}}&{{\quad}}&{{q,q}}&{{\Rightarrow x_{i,j}^{k}}}&{{L_{i,j}\Rightarrow l_{i,j}}}\\ {{}}&{{}}&{{}}&{{q,q}}&{{\Rightarrow x_{i,j}^{k}}}&{{L_{i,j}\Rightarrow l_{i,j}}}\end{array}$$

i;j Li;j ) li;j *post* oi ; q Li;j i;j Li;j ) li;j *post* oi ; q Li;j ;
and let *test*kbe defined as

```
testk
        ff:x
             
             s(k)
                 
             i;j ; 
                     s(k)
                        
                         i; j ) x
                                       
                                       s(k)
                                           
                                       i;j s(k):

```

Further, let c 1
, c 2
, and g be fresh symbols not appearing in k
+
k k. Now we can

define the pair of compiled operators o
k i i hpre oi c k
(k ; ) corresponding to the original operator oi O:
o

k

k ; postkoi blockkoi testk f> ) f:c k ; g; cs(k) gg f> ) k + k   ki; j gg f> ) xk m;j k m 6 igg f> ) s(k) + s(k)  s(k):
$${\dot{\imath}}\,,\,j$$

$$287$$