

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

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

$$\mathbf{1}$$

It is obvious that reordering is a more powerful operation than deordering, since the reordered plan in Figure 5a allows for a shorter schedule than the optimal deordering in Figure 4a. On the other hand, if the original plan had been

$$\mathbf{1}$$
$$\mathbf{\Sigma}_{2}$$
$$2$$

then deordering would have been sufficient for arriving at the optimal plan in Figure 5a.

## 3. Planning Formalisms

This section defines actions, plans and related concepts, which basically appear in two different guises in this article. Definitions and tractability results will mostly be cast in a general, axiomatic framework in order to be as general and independent of formalism as possible. Hardness results, on the other hand, will mostly be cast in a specific formalism, GROUND TWEAK, and often subject to further restrictions, this in order to strengthen the results. Both these formalisms are defined below. In addition to these, a third formalism will be used, but its definition will be deferred until it is used, in Section 7.