do more modifications than a deordering; a minimum deordering can obviously never have a smaller ordering relation than a minimum reordering. Examples of this difference was shown already in Section 2, where Figure 4a shows a minimum-constrained deordering and Figure 4b shows a minimum-constrained reordering.

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

Other alternative definitions of least-constrainment could be, for instance, to maximize the unorderdness or to minimize the length of the longest chain in the modified plan. However, to find a de-/reordering which has as many pairs of unordered actions as possible is the dual of computing a minimum de-/reordering and it is, thus, already covered. Minimizing the length of the longest ain is a condition whi may be relevant when actions can be executed in parallel and the overall execution time is to be minimized. However, since the nmber of ordering constraints is quadratic in the length of a chain (because of transitive acs), minimizing the size of the relation will often be a reasonable approximation of minimizing the chain length. Furthermore, minimizing the longest chain is still a rather weak condition for this purpose, so it is better to study directly the problem of finding shortest parallel executions of plans, which will be done later in this article.

Another issue is whether to minimize the size of the ordering relation as given, or to reduce the transitive or reductive closure of it. Since plans may have superfluous orderings with no particular purpose, it is reasonable to standardize matters and either add all possible transitive arcs, getting the transitive closure, or to remove all transitive arcs, getting the reductive closure.  The choice between these two is not important for the results to be proven.  However, minimizing the transitive closure will give a preference to plans with many unordered short chains of actions over plans with a few long chains, and so seems to coincide better with the term 'least constrained'.

## 4.2 Computing Least-Constrained Plans

Minimal deordering is weaker than the two other least-constrainment criteria considered, but it is the least costly to achieve  it is the only one of the three criteria which can be satisfied by a polynomial-time modification to a plan.