in the first approach, which seems more appropriate for problems where queries on the TCN are more usual tasks than updating processes.

In addition, the proposed reasoning algorithms obtain a sound and complete set of I-L-Sets and a *globally labeled-consistent* TCN. Regrettably, assembling a solution in a labeled TCN, although backtrack free, is also costly due to the exponential number of I-L-Sets. However, these features offer the capability of representing and managing special types of non-binary disjunctive constraints (later detailed in Section 6).

Other reasoning algorithms for query processes on a non-closured TCN, as well as CSP
approaches can be defined on the basis of the labeled temporal algebra described. Less expensive algorithms can be applied on labeled constraints by using the specified operations ⊗lc, ⊕lc, ∪Τlc and ⊆Τlc. For instance, the TCA algorithm as is applied by Allen (1983), and the k-consistency algorithms like those described in (Cooper, 1990; Freuder, 1978). Moreover, a minimal TCN of labeled constraints can be obtained without enforcing global consistency; for example, by applying the naive backtracking algorithm described by Dechter, Meiri and Pearl (1991), which is O(n 3 l e).

## 5. Interval-Based Constraints Through Labeled Point-Based Constraints

The integration of quantitative and qualitative information has been the goal of several temporal models, as was described in Section 1. When intervals are represented by means of their ending points Ii
+Ii
-, integration of constraints on intervals and points seems to require some kind of nonbinary constraints between time-points (Gerevini & Schubert, 1995; Schwalb & Dechter, 1997; Drakengren & Jonsson, 1997). In this section, the proposed temporal model is applied in order to integrate interval and point-based constraints. Constraints on intervals are managed by means of constraints on ending points of intervals and I-L-Sets. Likewise, metric information can also be added to interval constraints such that an expressive way of integrating qualitative and quantitative constraints is obtained.

## 5.1 Symbolic Interval-Based Constraints

Symbolic constraints on intervals express the qualitative temporal relation between two intervals.

Each symbolic constraint is a disjunctive subset of 13 elemental constraints, which are mutually exclusive among them (Allen, 1983). For example, the following constraint I1 {ec1, ec2} I2, ec1, ec2 ∈{b, m, o, d, s, f, e, bi, mi, oi, di, si, fi},
really means 'I1 [ (ec1 ∨ ec2) ∧ ¬(ec1 ∧ ec2) ] I2',since ec1 and ec2 are mutually exclusive, and one and only one elemental constraint should hold. For reasons of simplicity, we only consider two disjuncts in the symbolic constraint. However, these expressions can be easily extended for managing from 2 to 13 disjuncts. The above expression can be expressed as:

$$\mathbf{e}_{1}\wedge(-\mathbf{i}\otimes\mathbf{e}_{2})\wedge(-\mathbf{i}\otimes\mathbf{e}_{1}\wedge\mathbf{i})$$

I1 [ (ec1 ∧ ¬ec2) ∨ (¬ec1 ∧ ec2) ] I2 ≡ 

$\rm I_{1}\left[\left(ec_{1}\vee\neg cc_{1}\right)\wedge\left(ec_{2}\vee\neg cc_{2}\right)\wedge\neg\left(ec_{1}\wedge ec_{2}\right)\wedge\neg\left(\neg cc_{1}\wedge\neg cc_{2}\right)\right]I_{2}$ ($e2$).  
In this way, we have:

$\pi\times\pi\times\pi\times\pi$ 2. 