In order to address the problem of measuring the relative expressive power of planning formalisms, we start with the intuition that a formalism X is *at least as expressive* as another formalism Y if *planning domains* and the corresponding *plans* in formalism Y can be *concisely expressed* in the formalism X . This, at least, seems to be the underlying intuition when expressive power is discussed in the planning literature.

B¨ackstr¨om (1995) proposed to measure the expressiveness of planning formalisms using his ESP-reductions. These reductions are, roughly speaking, polynomial many-one reductions1on planning instances that *do not change the plan length*. Using this notion, he showed that all of the propositional variants of basic STRIPS not containing conditional effects or arbitrary logical formulae can be considered as expressively equivalent. However, taking our point of view, ESPreductions are too restrictive for two reasons. Firstly, plans must have identical size, while we might want to allow a moderate growth. Secondly, requiring that the transformation can be computed in polynomial time is overly restrictive. If we ask for how concisely something can be *expressed*,
this does not necessarily imply that there exists a polynomial-time transformation. In fact, one formalism might be as expressive as another one, but the mapping between the formalisms might not be computable at all. This, at least, seems to be the usual assumption made when the term expressive power is discussed (Baader, 1990; Cadoli, Donini, Liberatore, & Schaerf, 1996; Erol, Hendler, & Nau, 1996; Gogic, Kautz, Papadimitriou, & Selman, 1995).

Inspired by recent approaches to measure the expressiveness of knowledge representation formalisms (Cadoli et al., 1996; Gogic et al., 1995), we propose to address the questions of how expressive a planning formalism is by using the notion of *compiling* one planning formalism into another one. A compilation scheme from one planning formalism to another differs from a polynomial many-one reduction in that it is not required that the compilation is carried out in polynomial time. However, the result should be expressible in polynomial space. Furthermore, it is required that the operators of the planning instance can be translated *without* considering the initial state and the goal. While this restriction might sound unnecessarily restrictive, it turns out that existing practical approaches to compilation (Gazen & Knoblock, 1997) as well as theoretical approaches
(B¨ackstr¨om, 1995) consider only *structured* transformations where the operators can be transformed independently from the initial state and the goal description. From a technical point of view this restriction guarantees that compilations are non-trivial. If the entire instance could be transformed, a compilation scheme could decide the existence of a plan for the source instance and then generate a small solution-preserving instance in the target formalism, which would lead to the unintuitive conclusion that all planning formalisms have the same expressive power.

As mentioned in the beginning, not only the space taken up by the domain structure is important, but also the space used by the plans. For this reason, we distinguish between compilation schemes in whether they preserve plan size exactly, *linearly*, or *polynomially*.

Using the notion of *compilability*, we analyze a wide range of propositional planning formalisms, ranging from basic STRIPS to a planning formalism containing conditional effects, *arbitrary boolean formulae*, and *partial state specifications*. As one of the results, we identify two equivalence classes of planning formalisms with respect to *polynomial-time* compilability preserving plan size exactly. This means that adding a language feature to a formalism without leaving the class does not increase the expressive power and should not affect the principal efficiency of