them without using hyper-arcs. Therefore, metric and symbolic constraints among intervals and timepoints can be fully integrated, represented and managed by means of a *labeled* metric point-based Temporal Constraint Network (TCN). Particularly, the model proposed here handles constraints proposed in QA (Meiri, 1996), IDSA (Badaloni & Berati, 1996), and Distance Constraint Arrays model (Staab & Hahn, 1998). Moreover, several added functionalities are also provided:

- Management of alternative *temporal contexts*. Each input constraint can be associated to a given context. A hierarchy of alternative temporal contexts can be defined, such that constraints between points and intervals are dependent on each context. To my knowledge, these features improve existing temporal models, where contexts are not managed.

- Reasoning algorithms on labeled constraints are based on a closure process. These processes guarantee consistency and obtain a minimal disjunctive context-dependent TCN. Additionally, a special type of *globally labeled-consistent* TCN is obtained. This property allows us to obtain solutions by backtrack-free search (Freuder, 1982).

- Management of a special type of non-binary constraints. Reasoning algorithms are able to manage disjunctions of disjunctive constraints. This supposes an extension of disjunctions of non-disjunctive metric constraints proposed by Stergiou and Koubarakis (1998). Moreover, given a set of disjunctive constraints, the model can handle logical relations among disjunctions of different constraints. Thus, we can express that a set of atomic disjuncts in disjunctive constraints are mutually disjunctive among them. Therefore, a special type of and/or TCN can be managed as a conjunctive (and) TCN. Likewise, the model can also handle special non-binary constraints representing implications among temporal constraints as were identified by Meiri (1996).
With these features, the proposed temporal model is suitable for modeling problems where these requirements appear. The computational cost of reasoning methods is non-polynomial, given the complexity of the underlying problem. However, several improvements are also proposed.

A brief revision of the main temporal reasoning concepts is presented in Section 2. In Section 3, a temporal algebra for labeled point-based disjunctive metric constraints is described. This temporal algebra introduces the concept of labeled constraints and their temporal operations. Reasoning algorithms for guaranteeing a minimal (and consistent) TCN are specified in Section 4. By using this model, the integration of interval and point-based constraints and management of non-binary constraints are respectively described in Sections 5 and 6. Association of constraints to temporal contexts and management of context-dependent constraints are detailed in Section 7. Finally, Section 8 concludes.

## 2. Basic Temporal Concepts

Temporal reasoning deals with reasoning on temporal constraints. The syntax and semantics of constraints are defined by an underlying temporal algebra, which is the basis for performing the reasoning processes. A temporal algebra can be defined according to the following elements:
- *Temporal primitive* (or variable) 'xi', usually time-points (ti) or intervals (Ii).

- *Interpretation domain* D for primitives xi. The interpretation domain represents the time line.