Proof. PSPACE-hardness of S-PLANEX follows from a result by Bylander (1994, Corollary 3.2).

Membership of SBIC -PLANEX in PSPACE follows because we could, step by step, guess a sequence of operators, verifying at each step that the operator application leads to a legal follow up state specification and that the last operator application leads to a state specification that entails the goal specification. For each step, this verification can be carried out in polynomial space. The reason for this is that all the conditions in the definition of R are verified by polynomially many calls to an NP-oracle. Therefore, SBIC can be decided on a non-deterministic machine in polynomial space, hence it is a member of PSPACE.

From that it follows that the plan existence problem for all formalisms that are in expressiveness between S and SBIC —including both formalisms—is PSPACE-complete.

## 3. Expressiveness And Compilability Between Planning Formalisms

Although there is no difference in the computational complexity between the formalisms in the SBIC -family, there might nevertheless be a difference in how concisely planning domains and plans can be expressed. In order to investigate this question, we introduce the notion of *compiling planning formalisms.*

## 3.1 Compiling Planning Formalisms

As mentioned in the Introduction, we will consider a planning formalism X *as expressive as* another formalism Y if planning domains and plans formulated in formalism Y are *concisely expressible* in X . We formalize this intuition by making use of what we call *compilation schemes*, which are *solution preserving mappings* with *polynomially sized results* from Y domain structures to X
domain structures. While we restrict the size of the result of a compilation scheme, we do not require any bounds on the computational resources for the compilation. In fact, for measuring the expressibility, it is irrelevant whether the mapping is polynomial-time computable, exponential-time computable, or even non-recursive. At least, this seems to be the idea when the notion of expressive power is discussed in similar contexts (Baader, 1990; Erol et al., 1996; Gogic et al., 1995; Cadoli et al., 1996). If we want to use such compilation schemes in practice, they should be reasonably efficient, of course. However, if we want to prove that one formalism is *strictly more expressive* than another one, we have to prove that there is no compilation scheme regardless of how many computational resources such a compilation scheme might use.

So far, compilation schemes restrict only the size of domain structures. However, when measuring expressive power, the size of the generated plans should also play a role. In B¨ackstr¨om's ESP-reductions (1995), the plan size must be identical. Similarly, the translation from SLC to S
proposed by Gazen and Knoblock (1997) seems to have as an implicit prerequisite that the plan length in the target formalism should be almost the same. When comparing the expressiveness of different planning formalisms, we might, however, be prepared to accept some growth of the plans in the target formalism. For instance, we may accept an additional constant number of operators, or we may even be satisfied if the plan in the target formalism is linearly or polynomially larger. This leads to the schematic picture of compilation schemes as displayed in Figure 2.

Although Figure 2 gives a good picture of the *compilation framework*, it is not completely accurate. First of all, a compilation scheme may introduce some auxiliary propositional atoms that are used to control the execution of newly introduced operators. These atoms should most likely have an initial value and may appear in the goal specification of planning instances in the target