Proof: Disjunctions in constraints are only related to the contexts in which input constraints are asserted, if non-disjunctive constraints are managed. That is, constraints between each pair of nodes are in the form:
(ni {(ecij.0{W0 R0}), (ecij.1{W1 R0}), ...... , (ecij.k{Wk R0})} nj) , 0≤k≤W / W=|{Wi}| Thus, the maximum number of disjuncts in constraints is bounded by the maximum number of managed contexts W. Moreover, the maximum length of associated label sets is the maximum depth in the hierarchy of contexts, and the set of I-L-Sets has only 2-length sets (i.e.: pairs of labels associated to each pair of successor contexts of each context). Therefore, the computational cost of operations ⊗lc and ⊕ lc is bounded by O(W
2). ◊
The methods proposed in Section 7.1 for management of temporal contexts can also be applied to other temporal reasoning algorithms, instead of the reasoning methods detailed in Section 4. This requires that these other reasoning algorithms be based on the operations of composition and intersection of temporal constraints. Thus, i) Each elemental constraint should only be associated to the context (Wi) in which it is asserted 7.

Thus, label sets associated to elemental constraints have only one contextual label {Wi}.
ii) The methods for management of temporal contexts described in Section 7.1 should be integrated into the new reasoning algorithms. These algorithms should use the operations ⊕
lc, ⊗lc, get and *get-upwards*. The computational cost of operations ⊕lc and ⊗lc related to management of temporal contexts is polynomial (O(W
2)) in the number (W) of managed contexts. Therefore, the computational cost of the reasoning algorithms is increased by a factor W2when temporal contexts are managed.

For instance, when interval-based constraints are managed, the TCA algorithm can be used to obtain a path-consistent context-dependent IA-TCN, with a O(n 3 W
2) cost. Similarly, when a contextdependent reasoning is applied to PIDN networks (Pujari & Sattar, 1999), the computational cost of specific reasoning algorithms on PIDN constraints is increased by a factor W2. When the proposed temporal algebra in Section 3 is applied to tractable classes of constraints, the specific reasoning algorithms for management of these classes of constraints can also be applied. The computational cost of these reasoning algorithms (which should be based on combination and intersection operations on constraints) is increased by a polynomial factor W2. For instance, when nondisjunctive metric constraints are managed, the TCA algorithm can be used as the closure algorithm in Section 7.1. This algorithm will obtain a minimal context-dependent TCN with a computational cost O(n 3 W
2).

## 8. Conclusions

Several problems remain pending in representation and reasoning problems on temporal constraints.

In relation to this, we have dealt with reasoning on complex qualitative and quantitative constraints between time-points and intervals, which can be organized in a hierarchy of alternative temporal