
## Proposition 4 The Relations Xand X P Are Transitive And Reflexive.

Furthermore, it is obvious that when moving upwards in the diagram displayed in Figure 1, there is always a polynomial-time compilation scheme preserving plan size exactly. If i denotes the projection to the i-th argument and ; the function that returns always the empty set, the generic compilation scheme for moving upwards in the partial order is f h1; ;; ;; 2 ; 2i.

## Proposition 5 If X V Y, Then X 1 P Y. 4. Compilability Preserving Plan Size Exactly

Proposition 5 leads to the question of whether there exist other compilation schemes than those implied by the specialization relation. Because of Proposition 5 and Proposition 4, we do not have to find compilation schemes for every pair of formalisms. It suffices to prove that X is compilable to Y, in order to arrive at the conclusion that all formalisms that are below X are compilable to Y
and formalisms above Y.

A preview of the results of this section is given in Figure 3. We will establish two equivalence classes such that all members of each class are compilable to each other preserving plan size exactly.

These two equivalence classes will be called SLI - and SLIC -class, in symbols SLI and SLIC ,
naming them after their respective largest elements.

![0_image_0.png](0_image_0.png)

Figure 3: Equivalence classes of planning formalisms created by polynomial-time compilation schemes preserving plan size exactly