
## 4.1 Least-Constrainment Criteria

There is, naturally, an infinitude of possible definitions of least-constrainment.  Some seem more reasonable than others, however. Three intuitively reasonable candidates are defined and analyzed below. Although other definitions are possible, it is questionable whether considerably better or more natural definitions, with respect to the purposes mentioned above, can be defined without using more information than is usually present in a t.o. or

p.o. plan.  **Definition 4.1**: _Let $=$ and $=$ ' be two p.o. plans and $\Pi$ a PP1. Then,_  1. _is a reordering of wrt. $\Pi$ iff both and are $\Pi$-valid._ 2. _is a_ **ordering** _of wrt. $\Pi$ iff _is a reordering of and'$\subseteq$_ 3. _is a_ **proper** _deordering of wrt. $\Pi$ iff _is a reordering of and'$\subseteq$_  **Definition 4.2**: _Given a_ **PP1** _and two p.o. plans $=$ _and_ $=$ ',_  1. _is a_ **minimal-constrained** _deordering of wrt. $\Pi$ iff_
$$\begin{array}{l l l}{{(a)}}&{{\quad i s\ a\ d e o r d\,e r i n g\quad}}&{{\quad w r t.\ \ \Pi\ a n d}}\\ {{}}&{{}}&{{}}\\ {{(b)\ \,t h e r e\ i s\ n o\ p r o p r e p r\ d e o\,r d e r i n g\ o f}}\end{array}$$

$$w r t\;\;\;\Pi;$$
2.

is a minimum-constrained deordering of 

$(a)$ _is a reorderingering wrt._ $\Pi$ _and_ $(b)$ _there is no reordering_ ${}^{\prime\prime}$ _of_ $wrt.$$\Pi$ _s.t._ $\mid$ _${}^{\prime\prime\prime}$_  _is a_ minimum-constrained reordering _of_ $wrt.$$\Pi$ _iff_  $(a)$ _is a reordering wrt_ $\Pi$ _and_  $(b)$ _there is no reordering_ ${}^{\prime\prime}$ _of_ $wrt.$$\Pi$ _s.t._ $\mid$ _${}^{\prime\prime\prime}$_
wrt. II iff ----- wrt. Π s.t. |  " | wrt. Π s.t. |  " |  |  |;
s.

Note that the previous publication (Backstrom, 1993) used the terms LC1-minimality for minimal-constrained deordering and LC2-minimality for minimum-constrained reordering.

This change in terminology has been done with the hope that more will be gained in clarity than is lost by confusion.

It is easy to see that minimum-constrainment is a stronger criterion than minimalconstrainment any minimum-constrained deordering of a plan    is a minimal-constrained deordering of , but the opposite is not true. As an example, consider the plan in Figure 6a.

If removing all ordering constraints from action C, the result is the plan in Figure 6b, which is still valid. This plan has an order of size 3 (there is one implicit transitive order) and it is a minimal-constrained deordering since no further deordering can be made. It is not a minimum-constrained deordering, however, since if instead breaking the ordering constraints between the subsequences AB and CB, the result is the plan in Figure 6c, which is also valid.

This plan has an ordering of size 2 and it can easily be seen that it is a minimum-constrained deordering, and that it happens to coincide with the minimum-constrained reordering in this case. This coincidence is not always the case, however, since a reordering is allowed to