
## 6.2 Global Syntactical Restrictions

B¨ackstr¨om and Klein (1991a, 1991b), and, subsequently, B¨ackstr¨om and Nebel (1995),
consider other types of restrictions, but using a more refined model (the SAS **formalism) in** which:
1. The state variables are multi-valued, and

2. Two types of preconditions are considered: prevail **conditions, which are variable**
values that are required prior to the execution of the operator and are not affected by the operator, and preconditions**, which are affected by the operator.**
In general, four different restrictions were considered in these works:

(P) Post-uniqueness**: For each effect there is at most one operator that achieves this effect.**
In other words, desired effects determine operators to be used in a plan. Formally, a problem instance is post-unique if and only if, for each vi ∈ V and x ∈ D(vi**), there is**
at most one operator A ∈ **Λ such that** post(A)[i] = x.

(S) Single-valuedness**: At most one value of each state variable appears in the prevail**
conditions of the operators. For instance, if a certain operator requires the light to be on (as a prevail condition), no other operator can use the prevail condition that the light is off. Formally, a problem instance is single-valued iff there exist no two operators A, A′ ∈ Λ and vi ∈ V **such that** prv(A)[i] 6= u, prv(A′)[i] 6= u**, and**
prv(A)[i] 6= prv(A′)[i].

(U) Unariness**: Each operator affects only one state variable.**
(B) Binariness: All state variables have exactly two possible values, i.e. **all state variables**
are propositional.
All these four properties are syntactical. However, the properties P and S differ from the properties U and B by the fact that they have a global **nature: Post-uniqueness and singlevaluedness restrict not the form of the operators, but a global property of the whole set of**
operators. B¨ackstr¨om and Nebel (1995) showed that US (unariness and single-valuedness)
is the extreme problem class for which plan generation is polynomial. 6 The problems that we analyzed in this paper belong to the problem class UB, by definition. As we already mentioned, even determining plan existence for this class of problems is pspace-complete. Now consider the problem class PUB. B¨ackstr¨om **and Nebel (1995)**
showed that: (i) PUB has instances with exponentially long minimal solutions, thus plan generation for PUB is requires exponential time; (ii) existence of bounded length plans for PUB is strongly np**-hard; and (iii) the complexity of general plan existence for PUB is still**
an open question. Informally it means that strengthening restrictions from UB to PUB does not reduce the complexity significantly, at least from the practical point of view.

Proposition 1 **Every UB problem instance with a tree causal graph is either post-unique,**
or can be transformed into an equivalent post-unique problem instance in (low) polynomial time. Thus, TreeUB ⊂ **PUB.**