Context-Constraints (ni, nj*, context*k)::= Get-upwards (ni, nj, contextk) –
{lecij.p∈lcij / ∃contextq∈Succesor-Contexts(contextk), {contextq}∩{labelij.p}≠∅}.

For instance, given the context-dependent constraint lc12 in Figure 13 *(expression e3)*, the following constraint would hold between (n1, n2) in both contexts W1 and W3:
Context-Constraints(n1, n2, W1) ⊕lc Context-Constraint(n1, n2, W3) =
{[0 50]{R3 R1 W1 W0}, [200 210]{R4 R2 W1 W0}} ⊕lc {[0 25]{R7 R1 W3 W0}, [260 280]{R8 R2 W3 W0}}=
{[0 25]{R7 R3 R1 W3 W1 W0}}
6.

In addition, we can obtain the constraints, which simultaneously hold in a context and in any of its successor ones. For instance, in context W1 and in any of its successor contexts (W11, W12), the following constraint holds:
Context-Constrains(n1, n2, W1) ⊕lc [Context-Constraints(n1, n2, W11) ∪lc Context-Constraints(n1, n2, W12)]=
{[0 50]{R3 R1 W1 W0}, [200 210]{R4 R2 W1 W0}} ⊕lc
{[0 25]{R0 R3 R1 W11 W1 W0}}∪lc {[30 50]{R9 R3 R1 W12 W1 W0}, [200 205]{R10 R2 R4 W12 W1 W0}}=
{[200 205]{W12 R10 R4 R2 W1 W0}, [0 25]{W11 R0 R3 R1 W1 W0}, [30 50]{W12 R9 R3 R1 W1 W0}}.

On the other hand, each alternative context (Wi) can be associated to an alternative hypothesis
(Hi). Each hypothesis Hi gives rise to a set of constraints, which will be asserted in the associated context Wi. Thus, the proposed reasoning processes assure minimal constraints in the hierarchy of hypotheses. Moreover, if a hypothesis (Hi) becomes unavailable, then the label set {Wi} should be added to the set of I-L-Sets. Thus, all constraints in context Wi (and in all its successor contexts) will be removed. That is, all constraints that depend on the unavailable hypothesis Hi will be removed.

## 7.4 Computational Complexity Of Temporal Context Management

The management of temporal context does not increase the complexity of the reasoning processes detailed in Section 4. In fact, we can consider that each label associated to a disjunct (Ri) in labeled disjunctive constraints is also associated to a context (Wi). Thus, the computational cost of each updating process is also bounded by O(n 2l 2e), where 'l' is the maximum number of input disjuncts between any pair of nodes in all contexts.

The temporal labeled algebra proposed in this paper (Section 3) has been applied on the pointbased disjunctive metric constraints (Dechter, Meiri & Pearl, 1991). However, this labeled algebra can also be applied on other temporal constraints. In this case, the operations ⊕ lc, ⊗ lc, ∪lc and ⊆ lc should be specified (Section 3) on the basis of the operations ⊕, ⊗, ∪T and ⊆T of the underlying algebra. In this way, the management of temporal contexts can also be applied to other types of constraints.

Theorem 13. The computational complexity of the proposed reasoning process applied to contextdependent non-disjunctive metric constraints is polynomial (O(n 2 W
2)) in the number W of managed contexts.