Federico Barber fbarber@dsic.upv.es

Two main lines of research are commonly recognized in the temporal reasoning area. The first approach deals with reasoning about temporal constraints on time-dependent entities. The goal is to determine what consequences (T) follow from a set of temporal constraints, "{Temporal-Constraints}|=T?", or to determine whether a set of temporal constraints is consistent, with no assumptions about properties of temporal facts. The second approach deals with reasoning about change, events, actions and causality. Here, the goal is to obtain the consequent state from a set of actions or events which are performed on an initial state: "[Si, {A₁, A₂, ..., A_n}]|= S_j?". Both these approaches constitute active fields of research with applications in several artificial intelligence areas such as reasoning about change, scheduling, temporal planning, knowledge-based systems, natural language understanding, etc. In these areas, time plays a crucial role, problems have a dynamic behavior, and it is necessary to represent and reason about the temporal dimension of information.

In this paper, we deal with the first of these approaches. Our goal is reasoning on qualitative and quantitative constraints between intervals or time-points in temporal contexts. Moreover, special cases of non-binary constraints are also managed. These tasks are pending issues in the temporal reasoning area, as well as important features to facilitate modeling of relevant problems in this area (including planning, scheduling, causal or hypothetical reasoning, etc.).

Several temporal reasoning models have been defined in the literature, with a clear trade-off between representation expressiveness and complexity of reasoning algorithms. Qualitative Point Algebra (PA) (Vilain, Kautz & Van Beek, 1986) is a limited subset of interval-based models. Interval Algebra (IA) introduced by Allen (1983) represents symbolic (qualitative) constraints between intervals but metric information, such as 'interval₁ starts 2 seconds before interval₂', cannot be included. Metric (quantitative) point-based models (Dechter, Meiri & Pearl, 1991) include the 'time line' (metric) in their constraints, but they can only represent a limited subset of disjunctive constraints between intervals. Thus, constraints like 'interval₁ {bef, aft} interval₂' cannot be represented (Gerevini & Schubert, 1995).

Some efforts have been made to integrate qualitative and quantitative temporal information on points and intervals (Kautz & Ladkin, 1991; Drakengren & Jonsson, 1997; etc.). Particularly, Meiri (1996) introduces Qualitative Algebra (QA), where each interval is represented by three nodes (one representing the interval and the other two representing its extreme points) such that QA can represent qualitative and metric constraints on points and intervals. Badaloni and Berati (1996) define the Interval Distance Sub Algebra (IDSA), where nodes are intervals. These intervals are related by disjunctive 4-tuple-metric constraints between their ending time points {(I^-_i, I^-_j), (I⁺_i, I^-_j), (I^-_i, I⁺_j), (I⁺_i, I⁺_j)}. Staab and Hahn (1998) propose a model for reasoning on qualitative and metric boundaries of intervals. However, these models cannot handle constraints on interval durations, which were identified earlier by Allen (1983). Constraints such as 'interval₁ lasts 2 seconds more than interval₂' require a high-order expression (Dechter et al., 1991), or a duration primitive which should be integrated with interval and point constraints (Allen, 1983; Barber, 1993). Particularly, Barber (1993) proposes two orthogonal networks to relate constraints on durations and time points. Navarrete (1997) and Wetprasit and Sattar (1998) relate disjunctive constraints on durations and time points, but only a limited subset of interval constraints is managed. More recently, Pujari and Sattar (1999) propose a framework for reasoning on points, intervals and durations (PIDN). Here, variables represent points or intervals, and constraints are an ordered set of three intervals representing (Start, End, Duration) subdomains. However, no specialized algorithms for management of PIDN constraints are proposed.

In relation to the complexity of reasoning algorithms, the consistency problem is polynomial in PA (Vilain, Kautz & Van Beek, 1986) and in non-disjunctive metric networks (Dechter et al., 1991). However, Vilain, Kautz and Van Beek (1986) also showed that determining the consistency of a general-case temporal network (i.e.: disjunctive qualitative and metric constraints between points, intervals or durations) is NP-hard. Thus, in previous qualitative or quantitative models, the consistency problem is tractable only under some properties on constraints, relationships between variable domains and constraints, or by using restricted subsets of constraints (Dechter et al., 1991; Dechter, 1992; van Beek & Detcher, 1995; Wetprasit & Sattar, 1998; Jeavons et al., 1998; etc.). For instance, tractable subclasses of IA have been identified by Vilain, Kautz and Van Beek (1986), Nebel and Burckert (1995), Drakengren and Jonsson (1997), etc. Moreover, some interesting results have been obtained in identification of tractable subclasses of QA. Specifically, Jonsson et al. (1999) identified the five maximal tractable subclasses of the qualitative point-interval algebra. However, to my knowledge the maximal tractable subclass of PIDN model (maximal tractable subclass of qualitative and quantitative point, interval and duration constraints) is still not identified. In any case, these restricted tractable subclasses are not able to obtain expressiveness of full models, and the problem of reasoning on disjunctive constraints on points and intervals remains NP-complete.

On the other hand, these qualitative and metric temporal models do not manage certain types of non-binary constraints, which are important for modeling some problems (scheduling, causal reasoning, etc.). For instance, disjunctive assertions like ‘(interval₁ {bef, meets} interval₂) Ú (time-point₃ is [10 20] from time-point₄)’, or temporal-causal relations like ‘If (interval₁ {bef, meets} interval₂) then (time-point₃ is [10 20] from time-point₄)’ should be incorporated in these models (Meiri, 1996). Moreover, the global consistency property introduced by Dechter (1992) is an important property in temporal networks, since it allows us to obtain solutions by backtrack-free search (Dechter, 1992; Freuder, 1982). In particular, a global consistent network would allow us to handle conjunctive queries like ‘does ‘(interval₁ {bef, meets} interval₂) Ù (time-point₃ is [10 20] from time-point₄) hold?’ without propagation of the query, as it is required in (van Beek, 1991).

Stergiou and Koubarakis (1996), Jonsson and Bäckström (1996) dealt with the representation of temporal constraints by means of disjunctions of linear constraints (linear inequalities and inequations) also named Disjunctive Linear Relations (DLRs). These expressions are a unifying approach to manage disjunctive constraints on points, intervals and durations, such that these expressions subsume most of the formalism for temporal constraint reasoning (Jonsson & Bäckström, 1998). Moreover, DLRs are able to represent disjunctions of non-disjunctive metric constraints (x₁-y₁£c₁ Ú x₂-y₂£c₂ Ú ....Ú x_n-y_n£c_n), where x_i and y_i are time points, c_i real numbers and n³1 (Stergiou & Koubarakis, 1998). Obviously, the satisfiability problem for an arbitrary set of disjunctions of linear constraints is NP-complete. Interesting tractable subclasses of DLRs and conditions on tractability are identified in (Cohen et al., 1996; Jonsson & Bäckström, 1996; and Stergiou & Koubarakis, 1996). The two main tractable subclasses are Horn linear and Ord-Horn linear constraints (Stergiou & Koubarakis, 1996; Jonsson & Bäckström, 1998). However, these subclasses subsume temporal algebras whose management is also polynomial.

The management of a set of disjunctions of linear constraints is mainly based on general methods from linear programming, although some specific methods have been defined for tractable subclasses (Stergiou & Koubarakis, 1998; Cohen et al., 1996; etc.). As Pujari and Sattar outline (1999), the linear programming approach, though expressive, does not take advantage of the underlying structures (e.g., domain constraints) of temporal constraints. In addition, usual concepts in temporal reasoning, as composition and intersection operations on constraints, minimal constraints, k-consistency (Freuder, 1982), decomposability (Montanari , 1974), globally consistency (Dechter, 1992), etc., and their consequences should be adapted to reasoning on disjunctive linear constraints, which is not a trivial issue.

In spite of the expressive power of the previous models, some problems (including planning, scheduling, hypothetical reasoning, etc.) also need to reason on alternative contexts (situations, intentions or causal projections) and to know what holds in each one of them (Dousson et al., 1993; Gerevini & Schubert, 1995; Garcia & Laborie, 1996; Srivastava & Kambhampati, 1999). This gives rise to the need to reason on context-dependent constraints. This feature is not supported in the usual temporal models in a general way, nor described in the usual expressive power of constraints (Jeavons et al., 1999). Therefore, ad-hoc methods should be used when reasoning on temporal contexts is required.

These issues will be addressed in this paper. We describe a temporal model, which integrates qualitative and metric disjunctive constraints on time-points and intervals. The temporal model is based on time-points as primitive, such that intervals are represented by means of their end time-points. However, the representation of interval constraints seems to imply some kind of relation among endpoint constraints (Gerevini & Schubert, 1995). The proposed temporal model introduces labeled constraints, where each elemental constraint (disjunct) in a disjunctive point-based metric constraint is associated to one unique label. In this way, point-based constraints can be related among them without using hyper-arcs. Therefore, metric and symbolic constraints among intervals and time-points 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.

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) 'x_i', usually time-points (t_i) or intervals (I_i).
• Interpretation domain D for primitives x_i. The interpretation domain represents the time line. Time points are instantiated on D (t_iÎD), and temporal intervals can be modelled as pairs of ending time points that can be instantiated on D: I_i = (I_i^-, I_i⁺), I_iÎDxD, I_i^-£I_i⁺.
• Temporal constraints between primitives, where each constraint relates n primitives: c_1,2..n(x₁, x₂, ..., x_n). As particular cases, the 'empty constraint' {Æ} is named the Inconsistent-Constraint and 'U' is the Universal-Constraint. Unary-constraints restrict the interpretation domain D for variables. They are not usually used in symbolic algebras, where an infinite domain is assumed. Binary-constraints are temporal constraints between two variables (x_i c_ij x_j), and n-ary-constraints represent temporal constraints among n variables. By default, binary constraints are assumed in this paper. We can also have qualitative (relative relation) or quantitative (metric relation) constraints, as well as disjunctive (c_ij is a set of disjunctive basic constraints, |c_ij|³1) or non-disjunctive constraints.
• Operations between constraints. Mainly, Temporal Composition (Ä), Temporal Intersection (Å), Temporal Union (È_T), and Temporal Inclusion (Í_T).

A temporal problem is specified by a set of n variables X= {x_i}, an interpretation domain D and a finite set of temporal constraints between variables {(x_i c_ij x_j)}. A temporal problem gives rise to a Temporal Constraint Network (TCN) which can be represented as a directed graph where nodes represent temporal primitives (x_i) and labeled-directed edges represent the binary constraints between them (c_ij). The Universal Constraint U is not usually represented in the graph, and each direct edge (representing c_ij) between x_i and x_j implies an inverse one (representing c_ji) between x_j and x_i. According to the underlying Temporal Algebra, we mainly have IA-TCNs based on the Interval Algebra (Allen, 1983), PA-TCNs based on the Point Algebra (Vilain et al., 1986), or Metric-TCNs based on the Metric Point Algebra (Dechter et al., 1991; Dean & McDermott, 1987). In this later case, disjunctive metric point-based constraints give rise to a Temporal Constraint Satisfaction Problem (TCSP) (Dechter et al., 1991).

Reasoning on temporal constraints can be seen as a Constraint Satisfaction Problem (CSP). An instantiation of the variables X is a n-tuple (v₁, v₂, v₃, ...,v_n) / v_iÎD which represents the assignments of values {v_i} to variables {x_i}: (x₁=v₁, x₂=v₂, ...,x_n=v_n). A (global) solution of a TCN is a consistent instantiation of the variables X in their domains such that all TCN constraints are satisfied. A value v is a consistent (or feasible) value for x_i if there exists a TCN solution in which x_i=v. The set of all feasible values of a variable x_i is the minimal domain for the variable. A constraint (x_i c_ij x_j) is consistent if there exists a solution in which (x_i c_ij x_j) holds. A constraint c_ij is minimal iff it consists only of consistent elements (or feasible values) that is, those which are satisfied by some interpretation of TCN constraints. A TCN is minimal iff all its constraints are minimal.

A TCN is consistent (or satisfiable) iff it has at least one solution. Freuder (1982) generalizes the notion of consistency as: 'a network is k-consistent iff (given any instantiation of any k-1 variables satisfying all the direct constraints among those variables) there exists at least one instantiation of any k_th variable such that the k values taken together satisfy all the constraints among the k variables'. As consequences: (i) all (k-1)-length paths in the network are consistent, (ii) for each pair or nodes, there exists an interpretation that satisfies each (k-1)-length path between them, and (iii) each sub-TCN of k-nodes is consistent. As particular cases, 1-consistency, 2-consistency and 3-consistency are called node-consistency, arc-consistency and path-consistency, respectively (Mackworth, 1977; Montanari, 1974).

Path-consistency is a common concept in constraint networks. From Montanari (1974) and Mackworth (1977), ‘a path of k-length through nodes (x₁, x₂, ..., x_k, x_j) is path-consistent iff for any value v₁Îd₁ and v_jÎd_j such that (x₁=v₁ c_1j x_j=v_j) holds, there exists a sequence of values v₂Îd₂, v₃Îd₃, ..., v_kÎd_k such that (v₁ c_l2 v₂), (v₂ c₂₃ v₃),...., and (v_k c_k,j v_j) hold’. A TCN is path-consistent iff all its paths are consistent. Moreover, Montanari (1974) proves that to ensure path-consistency it suffices to check every 2-length path. Thus, path-consistency and 3-consistency are equivalent concepts. Alternatively, Meiri (1996) outlines a path of k-length (x_i, x₁, x₂, ...,x_k, x_j) is path-consistent iff c_ij Í_T (c_i1 Ä c₁₂Ä ... Ä c_kj). However, this definition disregards domain constraints, such that it is equivalent to the former definition if variable domains are infinite or the TCN is also node and arc-consistent, as the usual case in symbolic algebras. In metric algebras, path-consistency usually assumes node and arc-consistency. Therefore, taking into account that it is only necessary to test 2-length paths to assure path-consistency, a TCN is path-consistent iff "c_ij,c_ik,c_kjÍTCN, c_ij Í_T (c_ik Ä c_kj). This condition gives rise to the more usual path-consistent algorithm: the Transitive Closure Algorithm (TCA) which imposes local 3-consistency in each sub-TCN of 3 nodes, such that all 2-length paths become consistent paths (Mackworth, 1977; Montanari , 1974). The TCA algorithm will obtain an equivalent path-consistent TCN if it exists. Otherwise, it fails.

"c_ij,c_ik,c_kjÍTCN: c_ij¬c_ij Å (c_ik Ä c_kj)

A network is strong k-consistent iff the network is j-consistent for all j£k (Freuder, 1982). An n-consistent TCN is a consistent TCN, and a strong n-consistent TCN is a minimal TCN. Alternatively, Dechter (1992) introduces the concepts of local and global consistency: A partial instantiation of variables (x₁=v₁, x₂=v₂, ...,x_k=v_k) / 1£k<n is locally consistent if it satisfies all the constraints among these variables. A subTCN is globally consistent if any locally consistent instantiation of the variables in the subTCN can be extended to a consistent instantiation of all TCN. A globally consistent TCN is one in which all its subTCNs are globally consistent. Thus, a TCN is strong n-consistent iff it is globally consistent (Dechter, 1992).

The first reasoning task on a TCN is to determine whether the TCN is consistent. If the TCN is consistent, we can then obtain the minimal-TCN, all TCN solutions (by assuming a discrete and finite model of time), only one solution, a partial solution (consistent instantiation of a subset of TCN variables, which is a part of a global solution), etc.

Deductive closure, or propagation, is one of the basic reasoning algorithms. The closure process is a deductive process on a TCN, where new derived constraints are deduced from the explicitly asserted ones by means of the composition (Ä) and intersection (Å) operations. Thus, the process of determining the consistency and the minimality of a TCN is related to a sound and complete closure process (Vilain et al., 1986). Alternatively, CSP-based methods (with several heuristic search criteria) are also used for guaranteeing consistency and obtaining TCN solutions. In this paper, we are mainly interested in TCN closure processes.

Determining the consistency of a general-case TCN is NP-hard, and Minimal TCNs can be obtained by a polynomial number of consistency processes (Vilain et al., 1986). Particularly, Dechter, Meiri and Pearl (1991) showed that determining consistency and obtaining a minimal disjunctive metric TCN can be achieved in O(n³ l^e), where ‘n’ is the number of TCN nodes, ‘e’ is the number of explicitly asserted (input) constraints, and ‘l’ is the maximum number of intervals in an input constraint. However, specific levels of k-consistency can guarantee consistency and obtain a minimal TCN, depending on the TCN topology or the underlying temporal algebra. For example, path-consistency guarantees consistency and obtains a minimal non-disjunctive metric TCN (Dechter et al., 1991). The path-consistency TCA Algorithm has an O(n³) cost (Allen, 1983; Vilain, Kautz & Van Beek, 1986). However, assuring path-consistency can become a complex task in disjunctive metric-TCNs if the variable domain D is large or continuous. As was stated by Dechter, Meiri and Pearl (1991), the number of intervals in |c_ij Ä c_jk| is upper bounded by |c_ij|x|c_jk|. Thus, the total number of disjuncts (subintervals) in a path-consistent TCN might be exponential in the number of disjuncts per constraints in the initial (input) TCN. Schwalb and Dechter (1997) call this the fragmentation problem, which does not appear in non-disjunctive metric TCNs. Thus, the TCA algorithm is O(n³ R³) in disjunctive metric-TCNs if time is not dense (Dechter et al., 1991), where the range ‘R’ is the maximum difference between the lowest and highest number specified in any input constraints.

The main elements of the point-based disjunctive metric temporal algebra are (Dechter et al., 1991):

An elemental constraint (ec) is one disjunct in a disjunctive constraint. Similar terms are atomic, basic or canonical constraints. However, let’s use this term due to the special structure of labeled elemental constraints which are introduced further on. Thus, a disjunctive constraint c_ij can be considered as a disjunctive set of l mutually exclusive elemental constraints {ec_ij.k}.

Definition 1 (Labeled constraints). A labeled elemental constraint lec_ij.k is an elemental constraint ec_ij.k associated to a set of labels {label_ij.k}, where each label_ij.k is a symbol. A labeled constraint lc_ij is a disjunctive set of labeled elemental constraints {lec_ij.k}. That is,

Each label in a labeled-TCN can be considered as a unique symbol. The following cases can occur:

1. If an input (or explicitly asserted) constraint lc_ij has only one elemental constraint, that is, only one disjunct, this elemental constraint has the label 'R₀'. The labeled Universal-Constraint is {U_{R0}}. In a given TCN, the set of all elemental constraints labeled with 'R₀' is the ‘common context’. Thus, the label R₀ represents the set of elemental constraints which have no other alternatives (disjuncts). All elemental constraints labeled only with R₀ should hold since they have no other alternative disjuncts.
2. If an input constraint lc_ij has more than one elemental constraint, each elemental constraint lec_ij.kÎlc_ij has a single and exclusive label associated to it (|{label_ij.k}|=1). Thus, each label in the TCN represents bi-univocally an elemental constraint in an explicitly asserted constraint.
3. Each derived elemental constraint (obtained by combining (Ä_lc) or intersecting (Å_lc) two labeled elemental constraints) has a set of labels associated to it. This set of labels is obtained from the label sets associated to the combined (or intersected) labeled elemental constraints. It will be detailed in the later specification of operations (Ä_lc, Å_lc) in Section 3.2. In consequence, the label set associated to a derived elemental constraint represents the conjunctive support-set of explicitly asserted elemental constraints that imply this derived elemental constraint.

Let's see a simple example on labeled constraints, which was introduced by Dechter, Meiri and Pearl (1991).

Figure 1: The labeled point-based disjunctive metric TCN of the Example 1

Definition 2 (Inconsistent-Label-Sets). An Inconsistent-Label-Set (I-L-Set) is a set of labels {label_i} and represents a set of overall inconsistent elemental constraints. That is, they cannot all simultaneously hold. à

Theorem 1. Any label set that is a superset of an I-L-Set is also an I-L-Set. The proof is obvious. If a set of elemental constraints is inconsistent, any superset of it is also inconsistent. à

Definition 3. Elemental constraints {lec_ij.k} of an input disjunctive constraint lc_ij are pairwise disjoint. Thus, each 2-length set of labels from each pair of {lec_ij.k} is added to the set of I-L-Sets. That is, for each input constraint lc_ij º {lec_ij.1, lec_ij.2, ..., lec_ij.l}, where lec_ij.kº(ec_ij.k{label_ij.k}) and |{label_ij.k}|=1:

"k,pÎ(1,..,l) / k¹p, I-L-Sets ¬ I-L-Sets È ({label_ij.k}È{label_ij.p}) à

In the example of Figure 1, {R₁ R₂} and {R₃ R₄} are I-L-Sets. Other I-L-Sets existing in a labeled TCN will be detected in the reasoning processes later detailed in Section 4.

The following points define the main operations on labeled constraints.

3.2.1 Temporal Inclusion Í_lc

The temporal inclusion operation Í_lc should take into account the inclusion of temporal intervals and the inclusion of associated label sets:

lec_ij.k Í_lc lec_ij.p = (ec_ij.k {label_ij.k}) Í_lc (ec_ij.p {label_ij.p}) =_def ec_ij.k Í_T ec_ij.p Ù {label_ij.k}Í {label_ij.p}.

3.2.2 Temporal Union È_lc

Operation È_lc performs the disjunctive temporal union of labeled constraints as the set-union of their elemental constraints. However, all labeled elemental constraints whose associated labels are I-L-Sets should be rejected.

Inconsistent({label_ij.k}) : lc’_ij

$lec_ij.pÎlc’_ij / lec_ij.pÍ_lc lec_ij.k : lc’_ij (s₁)

Other : ({lc’_ij} È {lec_ij.k}) - ({lec_ij.p}, "lec_ij.pÎlc’_ij Ù lec_ij.kÍ_lclec_ij.p) (s₂).

The function Inconsistent({label_ij.k}) returns true if the set {label_ij.k} is an I-L-Set or a superset of any existing I-L-Set (Theorem 1). Otherwise, it returns false:

The operation È_lc simplifies the resulting constraint. Equal or less-restricted elemental constraints with equal or bigger associated label sets are removed. For instance:

{([10 30]_{{R1 R3 R5 R9}}), ([40 40]_{{R6 R7}})} È_lc {([10 20]_{{R1 R3}}), ([40 40]_{{R6 R7 R8}})} =

{([10 20]_{{R1 R3}}), ([40 40]_{{R6 R7}})}.

In the resulting constraint, ([10 30]_{{R1 R3 R5 R9}}) and ([40 40]_{{R6 R7 R8}}) are eliminated, as examples of the cases s₁ and s₂, respectively. That is, ([10 20]_{{R1 R3}}) Í_lc ([10 30]_{{R1 R3 R5 R9}}) and ([40 40]_{{R6 R7}}) Í_lc ([40 40]_{{R6 R7 R8}}). These simplifications can seem counter-intuitive. However, note that the label set associated to each derived-labeled elemental constraint represents the support set (composed of input elemental constraints) from which the derived-labeled elemental constraint is obtained. Thus, only the minimal associated label set should be represented, for reason of efficiency. Moreover, the more labels are in the associated label set {label_ij.k}, the elemental constraint (ec_ij.k) should be equal or more restricted.

3.2.3 Temporal Composition Ä_lc

Operation Ä_lc performs the temporal composition of labeled constraints. It is based in the operation Ä of the underlying disjunctive metric point-based algebra.

lc_ij Ä_lc lc_jk =_def "lec_ij.pÎlc_ij, "lec_jk.qÎlc_jk È_lc [ (ec_ij.p Ä ec_jk.q {label_ij.p}È{label_jk.q})].

For instance: {([0 10]_{R1}), ([20 30]_{R2})} Ä_lc {([100 200]_{R3}), ([300 400]_{R4})} =

{([320 430]_{{R4 R2}}), ([300 410]_{{R4 R1}}), ([100 210]_{{R3 R1}}), ([120 230]_{{R3 R2}})}.

Note that elemental constraints in a labeled derived constraint may not be pairwise disjoint. However, these labeled derived elemental constraints cannot be simplified. This is related to the fragmentation problem of the disjunctive metric algebra (Schwalb & Dechter, 1997). We have that each derived-labeled elemental constraint should have its own associated label set. In the example, (([320 430]_{{R4 R2}}), ([300 410]_{{R4 R1}})) cannot be simplified to ([300 430]_{{R4 R2 R1}}) since each subinterval depends on a different set of labels (that is, on a different support-set of elemental constraints). If the label set {R₄ R₂} becomes an I-L-Set, only ([320 430]_{{R4 R2}}) should be removed. On the other hand, if [300 410] becomes an inconsistent interval between the implied time points, only {R₄ R₁} should be asserted as an I-L-Set.

3.2.4 Temporal Intersection Å_lc

Operation Å_lc performs the temporal intersection of labeled constraints and is based on the operation Å.

lc_ij Å_lc lc’_ij =_def "lec_ij.kÎlc_ij, "lec_ij.pÎlc’_ij , È_lc [lec_ij.k Å_lc lec_ij.p]

As example:

{([0 10]_{R1}), ([20 25]_{R2})} Å_lc {([0 30]_{R3}), ([40 50]_{R4})} = {([20 25]_{{R3 R2}}), ([0 10]_{{R3 R1}})}

In the operations Ä_lc and Å_lc, the label set {label_ij.r} associated to each derived labeled-elemental constraint (ec_ij.r) is obtained from the set-union of labels associated to combined (Ä_lc) or intersected (Å_lc) labeled-elemental constraints. Therefore, {label_ij.r} represents the support set (composed of input elemental constraints) that implies the derived elemental constraint (ec_ij.r).

Definition 4. A set of I-L-Sets is complete if it represents all inconsistent sets of TCN elemental constraints. A set of I-L-Sets is sound if each I-L-Set represents an inconsistent set of elemental constraints. à

Theorem 2. Assuming a complete and sound set of I-L-Sets, a labeled elemental constraint is consistent iff it has an associated label set which is not an I-L-Set. The proof is trivial, since the label set associated to each labeled elemental constraint represents its support-set. à

Theorem 3. Assuming a complete and sound set of I-L-Sets, no inconsistent labeled elemental constraint is obtained in operations Ä_lc and Å_lc.

Proof: The operations Ä_lc and Å_lc use the operation È_lc to obtain their results. This operation È_lc rejects all labeled elemental constraints whose associated labels are I-L-Sets. Thus, all elemental constraints derived in operations Ä_lc and Å_lc are consistent (Theorem 2). à

3.3 Distributive Property Ä_lc Over Å_lc in Disjunctive Labeled Constraints

Operations Ä and Å are distributive (i.e.: Ä distributes over Å) in non-disjunctive metric TCN, but this property does not hold in disjunctive metric constraints. Dechter, Meiri and Pearl (1991) show the following example. Given the disjunctive metric constraints:

a= {[0 1], [10 20]}, b= {[25 50]}, c= {[0 30], [40 50]},

we have:

Thus, clearly (a Ä (b Å c) ¹ (a Ä b) Å (a Ä c). However, the distributive property holds for operations Ä_lc and Å_lc in labeled TCN.

Theorem 4. By using labeled constraints and I-L-Sets, Ä_lc distributes over Å_lc.

Proof: Let’s consider the labeled constraints lc_i, lc_j and lc_k. Thus,

(lc_i Ä_lc lc_j) Å_lc (lc_i Ä_lc lc_k)

can be expressed, according to the definition of operation Ä_lc, as:

("lec_pÎlc_i, "lec_qÎlc_j, È_lc[(lec_p Ä_lc lec_q)]) Å_lc ("lec_rÎlc_i, "lec_sÎlc_k, È_lc[(lec_r Ä_lc lec_s)]) =

"lec_pÎlc_i, "lec_qÎlc_j, "lec_rÎlc_i, "lec_sÎlc_k (È_lc[(lec_p Ä_lc lec_q)] Å_lc È_lc[(lec_r Ä_lc lec_s)])

which, according to the definition of Å_lc, can be expressed as:

In this expression, lec_p and lec_r are elemental constraints of the same-labeled constraint lc_i. However, the set-union of label sets associated to each pair of elemental constraints in any (input or derived) labeled constraint is an I-L-Set (Definition 3). That is, if lec_p¹lec_r, then {label_p}È{label_r} is an I-L-Set. Thus, if lec_p¹lec_r, the label set associated to (lec_p Ä_lc lec_q) Å_lc (lec_r Ä_lc lec_s) is an I-L-Set. In consequence, (lec_p Ä_lc lec_q) Å_lc (lec_r Ä_lc lec_s) is rejected in operation È_lc. That is,

"lec_pÎlc_i, "lec_qÎlc_j, "lec_rÎlc_i, "lec_sÎlc_k / lec_p¹lec_r (È_lc[(lec_p Ä_lc lec_q) Å_lc (lec_r Ä_lc lec_s)]) = Æ.

Thus, the above expression (e1) results:

"lec_pÎlc_i, "lec_qÎlc_j, "lec_sÎlc_k (È_lc [(lec_p Ä_lc lec_q) Å_lc (lec_p Ä_lc lec_s)]).

In this expression, Ä_lc clearly distributes over Å_lc for elemental constraints (i.e.: non-disjunctive constraints). Therefore:

"lec_pÎlc_i, "lec_qÎlc_j, "lec_sÎlc_k (È_lc [(lec_p Ä_lc (lec_q Å_lc lec_s))]) =

"lec_pÎlc_i, È_lc [lec_p Ä_lc ("lec_qÎlc_j, "lec_sÎlc_k, È_lc [lec_q Å_lc lec_s])] = lc_i Ä_lc (lc_j Å_lc lc_k).

That is, Ä_lc distributes over Å_lc for labeled constraints.à

For instance, following the previous example:

a= {[0 1]_{R1}, [10 20]_{R2}}, b= {[25 50]_{R0}}, c= {[0 30]_{R3}, [40 50]_{R4}}

and {R₁ R₂}, {R₃ R₄} are I-L-Sets. Thus, we have:

(a Ä_lc (b Å_lc c) = {[0 1]_{R1}, [10 20]_{R2}} Ä_lc ({[25 50]_{R0}} Å_lc {[0 30]_{R3}, [40 50]_{R4}}) =

{[0 1]_{R1}, [10 20]_{R2}}Ä_lc {[25 30]_{{R3 R0}}, [40 50]_{{R4 R0}}} =

{[25 31]_{{R1 R3 R0}}, [40 51]_{{R1 R4 R0}}, [35 50]_{{R3 R2 R0}}, [50 70]_{{R4 R2 R0}}}.

Also,

(a Ä_lc b) Å_lc (a Ä_lc c) =

({[0 1]_{R1}, [10 20]_{R2}} Ä_lc {[25 50]_{R0}}) Å_lc

È_lc ([25 31]_{{R1 R3 R0}}, [40 51]_{{R1 R4 R0}}, [25 50]_{{R1 R2 R3 R0}},

However, {R₁ R₂}, {R₃ R₄} are I-L-Sets. Thus, ([25 50]_{{R1 R2 R3 R0}}, [50 51]_{{R1 R2 R4 R0},} [40 51]_{{R1 R2 R4 R0}}) are removed in operation È_lc. Therefore,

(a Ä_lc b) Å_lc (a Ä_lc c) = {[25 31]_{{R1 R3 R0}}, [40 51]_{{R1 R4 R0}}, [35 50]_{{R3 R2 R0}}, [50 70]_{{R4 R2 R0}}}.

That is, (a Ä_lc (b Å_lc c) = (a Ä_lc b) Å_lc (a Ä_lc c).

Several algorithms for reasoning on disjunctive constraints can be applied for the management of labeled temporal constraints, by using the Ä_lc, Å_lc, È_lc and Í_lc operations. For instance, the well-known Transitive Closure Algorithm, general closure algorithms as in (Dechter, 1992; Dechter et al., 1991; van Beek & Dechter, 1997), CSP-based approaches, etc. However, Montanari (1974) shows that when composition operation distributes over intersection, any path-consistent TCN is also a minimal TCN. From Theorem 4, we have that Ä_lc distributes over Å_lc. Thus, application of a path-consistent algorithm on the proposed-labeled TCN will obtain a minimal TCN. Thus, the TCA algorithm could be used as the closure process on labeled constraints, in a similar way as Allen (1983) uses it. However, an incremental reasoning process is proposed on the basis of the incremental path-consistent algorithm for non-disjunctive metric constraints described by Barber (1993). An incremental reasoning process is useful when temporal constraints are not initially known but are successively deduced from an independent process; for instance, in an integrated planning and scheduling system (Garrido et al., 1999). The proposed reasoning algorithm is similar to the TCA algorithm. However, updating and closure processes are performed at each new input constraint. Thus, each new input constraint is updated and closured on a previously minimal TCN (Figure 9). Therefore, no further propagation of modified constraints in the closure process is needed. Moreover, the proposed reasoning algorithms will obtain a complete and sound set of I-L-Sets.

The specification of reasoning processes is described in Section 4.1. The properties of these processes will be described later in Section 4.2.

Given a previous labeled-TCN, composed by a set of nodes {n_i}, a set of labeled constraints {lc_ij} among them, and a set of I-L-Sets, the updating process of each new c’_ij between nodes n_i and n_j constraint is detailed in Figure 2.

Figure 2: Updating process on labeled constraints

The function Put-Labels(c’_ij) returns a labeled-constraint lc’_ijº{lec’_ij.1, lec’_ij.2, ..., lec’_ij.l}, associating an exclusive label to each elemental constraint in c’_ij. If there is only one disjunct in c’_ij, the label in the unique elemental constraint is {R₀}. Otherwise, each pair of labels in lc’_ij is added to the set of I-L-Sets, since elemental constraints in c’_ij are pairwise disjoint (Definition 3). By using the Inverse function on non-labeled constraints, the Inverse_lc function is:

Inverse_lc ({(ec_ij.k{label_ij.k})}) =_def {(Inverse (ec_ij.k) {label_ij.k})}

The described updating process is performed each time that one new input constraint c’_ij is asserted on a previous TCN. Thus, an initial TCN with no nodes, no constraints, and no I-L-Sets is assumed (Figure 9). At each new input constraint (c’_ij), the TCN is incrementally updated and closured. That is, if c’_ij is consistent (Consistency-Test function), the constraint c’_ij is added to the TCN, the closure process (Closure function) propagates its effects to all TCN, and the new TCN is obtained. A new updating process can be performed on this new TCN, and so on successively.

4.1.1. The Consistency-Test Function

The Consistency-Test function (Figure 3) is based on the operation Å_lc. A new input constraint lc'_ij between nodes n_i and n_j is consistent if it temporally intersects with the previously existing constraint lc_ij between these nodes. Moreover, the Consistency-Test function can detect new I-L-Sets:

1. If the new constraint lc'_ij is consistent with the existing constraint lc_ij, and two elemental constraints ec_ij.pÎlc'_ij, ec_ij.kÎlc_ij do not intersect (ec_ij.k Å ec_ij.p=Æ), then the label set {label_ij.k}È{label_ij.p} is an I-L-Set and should be added to the current set of I-L-Sets.
2. If an existing elemental constraint between nodes n_i and n_j (lec_ij.kÎlc_ij) does not intersect with the new constraint lc'_ij, then {label_ij.k} is an I-L-Set and should be added to the current set of I-L-Sets.

Figure 3: Consistency-Test function

For example,

since

{{([0 10]_{R1}), ([20 25]_{R2}), ([100 110]_{Ra})} Å_lc {([0 30]_{R3}), ([40 50]_{R4}), ([-50 -40]_{Rb})} =

{([20 25]_{{R3 R2}}), ([0 10]_{{R3 R1}})} ¹ {Æ}.

Moreover, the label sets {R₄ R₂}, {R₄ R₁} and {Ra} are detected as I-L-Sets and should be added to the current set of I-L-Sets, since:

{[20 25]_{R2}} Å_lc {[40 50]_{R4}}={Æ}, {[0 10]_{R1})} Å_lc {[40 50]_{R4})}={Æ},

{([100 110]_{Ra})} Å_lc {([0 30]_{R3}), ([40 50]_{R4}), ([-50 -40]_{Rb})}={Æ}.

Note that {R_b} does not need to be detected as an I-L-Set, since the label R_b is not included in the final constraint {([20 25]_{{R3 R2}}), ([0 10]_{{R3 R1}})} to be added to the TCN.

Any superset of an I-L-Set is also an I-L-Set (Theorem 1). Moreover, note that {R₄ R₂}, {R₄ R₁} do not need to be added to the set of I-L-Sets, since the label R₄ is not included in the final constraint. Therefore, the following simplifications can also be performed each time a new I-L-Set is added to the current set of I-L-Sets. These simplifications do not modify the results of reasoning processes, but minimize the size of the set of I-L-Sets and improve its management efficiency.

1. No new I-L-Set that is superset of an existing I-L-Set is added to the set of I-L-Sets.
2. If an existing I-L-Set is superset of the new I-L-Set, then the existing I-L-Set is removed.
3. No new I-L-Set that contains a label not appearing in the labeled constraint (lc_ij Å_lc lc'_ij) to be added to the TCN is added to the set of I-L-Sets.

Let’s see an example of the updating and consistency-test processes. Let’s take the labeled-TCN that results from Example 1 once the following constraints have been updated and closured:

(t₁ {[60 ¥)_R1, [30 40]_R2} t₂), (t₃ {[40 50]_R3, [20 30]_R4} t₄), (T₀ {[10 20]_R0} t₁), (T₀ {[60 70]_R0} t₄).

Figure 4: The resulting labeled-TCN of Figure 1 before updating (t₃ {[10 20]} t₂)

The resulting labeled-TCN is shown in Figure 4 and the set of I-L-Set is {{R₁ R₂}, {R₃ R₄}}. Now, we update (t₃ {[10 20]_R0} t₂). The previously existing constraint between t₃ and t₂ is (Figure 4):

{([40 ¥)_{{R1 R3 R0}}) ([20 ¥)_{{R1 R4 R0}}), ([-10 30]_{{R2 R4 R0}}) ([10 50]_{{R2 R3 R0}})}

The Consistency-Test function performs:

Thus, (t2-t3Î{[10 20]_{R0}}) is consistent. Moreover, {R₁ R₃ R₀} is detected as an I-L-Set. The elemental constraints associated to {R₁ R₃ R₀} are an inconsistent set of disjuncts that cannot hold simultaneously. That is:

The set of I-L-Sets obtained in the reasoning process can be considered as special derived constraints, which express the inconsistency of a set of input elemental constraints. For instance, the I-L-Set {R₀ R₁ R₃} represents (Figure 1):

Ø ( (T₀ [10 20] T₁) Ù (T₃ [10 20] T₂) Ù (T₀ [60 70] T₄) Ù (T₃ [40 50] T₄) Ù (T₁ [60 ¥) T₂)).

This expression is a non-binary constraint. This type of constraints could be represented as a disjunctive linear constraint, as Jonsson and Bäckström (1996), Stergiou and Koubarakis (1996) show. However, input elemental constraints should be represented in derived constraints to be able to derive these inconsistent sets of input elemental constraints. In this model, this is done by means of the label sets associated to labeled elemental constraints.

The closure process (Figure 5) is applied each time a new input constraint (lc'_ij) is updated, such that the effects of lc'_ij are propagated to all TCN.

Figure 5: The closure process on labeled constraints

The closure process has three loops (Figure 6). In these loops the process obtains:

1. Derived constraints lc_ik between n_i and any node n_k, if n_k is previously connected with n_j (edge 1 of Figure 6).
2. Derived constraints lc_ljbetween n_j and any node n_l, if n_l is previously connected with n_i (edge 2 of Figure 6).
3. Derived constraints lc_lk between any pair of nodes n_l and n_k, if n_l and n_k are previously connected with n_i and n_j respectively (edge 3 of Figure 6).

Figure 7: The Labeled-Minimal TCN of the Example 1

Let’s see the previous Example 1 represented in Figure 1 and Figure 4, when the consistent constraint (expression e1):

(t₃ {[20 20]_{{R1 R4 R0}}, [10 20]_{{R2 R0}}} t₂)

is closured. In the first loop of the closure process, we have:

lc₃₀ ¬ lc₃₀ Å_lc ({[20 20]_{{R1 R4 R0}}, [10 20]_{{R2 R0}}} Ä_lc lc₂₀ =

However, {{R₁ R₂}, {R₃ R₄} {R₀ R₁ R₃}} are I-L-Sets. No labeled elemental constraints whose associated label set is a superset of these I-L-Sets will be derived (Theorem 3). Thus:

Similarly,

After the second and third loops, the final labeled-TCN is obtained (Figure 7). The final set of I-L-Sets is {{R₁ R₂}, {R₃ R₄} {R₀ R₁ R₃}}. These sets represent all sets of mutually inconsistent input-elemental constraints that exist in the TCN of Figure 1.

In this section, the main properties of the proposed reasoning algorithms are described.

Theorem 5. The proposed updating and closure processes (Sections 4.1 and 4.2) guarantee a consistent TCN if they are applied on a previous minimal (and consistent) TCN.

Proof: The updating constraint lc’_ij is asserted in the TCN if it is consistent with the previous minimal constraint lc_ij (Consistency-Test function).à

Theorem 6. The proposed closure algorithm obtains a path-consistent TCN, if it is applied over a previous minimal TCN.

Proof: This was detailed by Barber (1993) for non-disjunctive TCNs and it is applied here to labeled TCNs. We have:

Therefore, each derived constraint (any combinable path across lc_ij) between any pair of nodes in the TCN is computed, so that the closure process obtains a path-consistent TCN. à

iv)	Figure 8: lclk is also propagated to lclp and lcpq

Theorem 7. The proposed reasoning processes obtain a minimal TCN, if the previous TCN is a minimal TCN.

Proof: Montanari (1974) shows that when composition distributes over intersection (i.e.: Ä distributes over Å), any path-consistent TCN is also a minimal TCN). This is the case in non-disjunctive metric TCNs (Dechter et al., 1991). In our case, Ä_lc distributes over Å_lc (Theorem 4) and the closure process obtains a path consistent TCN (Theorem 6). Therefore, the proposed reasoning processes also obtain a minimal TCN. à

Figure 9: An incremental reasoning process

Theorem 8. At each updating process, reasoning algorithms obtain a complete and a sound new set of I-L-Sets (Definition 4), if they are applied on a previous minimal TCN and a previous sound and complete set of I-L-Sets.

1. No new I-L-Sets can appear in which some label of lc'_ij does not participate. Otherwise, they would have been detected in a previous updating process, since the previous set of I-L-Sets is assumed complete. Thus, some label of lc’_ij should always participate in any new I-L-Set that appears when lc’_ij is updated.
2. All new I-L-Sets (in which some label of lc’_ij participates) are detected in the consistency test of lc’_ij. Let's assume that a new and undetected I-L-Set exists {R_k, R₁, R₂, ....., R_p} in which some new elemental constraint ec_k{Rk}Îlc'_ij takes part. Thus, the elemental constraints associated to {R₁, R₂, ....., R_p} compute a derived elemental constraint ec_x between the nodes n_i and n_j:

In conclusion, the proposed reasoning algorithms obtain a minimal (and consistent) TCN if they are applied to a previous minimal-TCN (Figure 9). Therefore, the reasoning algorithms guarantee TCN consistency and obtain a minimal TCN and a complete and sound set of I-L-Sets at each new input assertion.

In a minimal (binary) disjunctive network, every subnetwork of size two is globally consistent (Dechter, 1992). Therefore, any local consistent instantiation of a subset of two variables can be extended to a full consistent instantiation. However, to assure that a local consistent instantiation of a subset of more that two variables is overall consistent, the partial instantiation should be propagated on the whole TCN (van Beek, 1991). Thus, assembling a TCN solution can become a costly propagation process in disjunctive TCNs, even though a minimal TCN was used. The proposed reasoning processes maintain a complete and sound set of I-L-Sets (Theorem 8). Thus, we can deduce if a locally consistent set of elemental constraints is overall consistent by means of label sets associated to labeled elemental constraints and the set of I-L-Sets. Specifically, we can deduce whether any locally consistent instantiation of k variables (1<k<n) is overall consistent. Let’s see the following example, which is based on a previous one proposed by Dechter, Meiri and Pearl (1991):

Here, we have the following labeled disjunctive constraints where, T₀ represents the initial time (6:50) and granularity is in minutes:

t₁- T₀ Î {[0 60]_R0}, t₂- T₀ Î {[0 60]_R0}, t₃- T₀ Î {[0 60]_R0}, t₄- T₀ Î {[0 70]_R0},

t₄ - t₁ Î {[25 50]_R0}, t₄ – t₂ Î {[10 30]_R1, [45 60]_R2}, t₄ – t₃ Î {[15 20]_R3, [35 40]_R4, [55 60]_R5}.

The minimal TCN of Example 2 is represented in Figure 10. Here, the binary constraints between each time-point and T₀ represent unary constraints and restrict interpretation domains for variables (t₁, t₂, t₃, t₄). Obviously, this minimal TCN is not a globally consistent TCN. For instance, instantiations {(t₁=0), (t₂=0), (t₃=0)} are consistent with the existing constraints involved among (T₀, t₁, t₂, t₃), but this partial solution cannot be extended to the overall TCN.

Figure 10: Minimal TCN of Example 2

Let’s consider the TCN with labeled constraints. For reasons of simplicity, we only denote the labeled constraints among (T₀, t₁, t₂, t₃):

The set of I-L-Sets is {{R₁ R₂} {R₃ R₄} {R₃ R₅} {R₄ R₅}}. From this labeled TCN and the set of I-L-Sets, we can deduce that instantiations {(t₁=0), (t₂=0), (t₃=0)} are not overall consistent. These instantiations are not locally consistent with the labeled constraints in the subTCN (T₀, t₁, t₂, t₃): All label sets associated to possible simultaneous fulfillment of

are I-L-Sets. That is, all label sets in the Cartesian product

{{R₀ R₄} {R₀ R₃}} C {{R₂ R₀} {R₁ R₀ R₃}} C {{R₀ R₅} {R₀ R₁ R₄}}

are I-L-Sets. Thus, the set of I-L-Sets can be used to deduce consistency of a set of labeled elemental constraints and to obtain a globally consistent labeled-TCN.

Theorem 9. Let’s assume a labeled-TCN of n nodes (and the corresponding complete and sound set of I-L-Sets) and a local set of k (1£k£()) labeled elemental constraints in the TCN, each one of which is between any pair of nodes:

{lec₁, lec₂,....., lec_k} º {(ec₁ {label₁}), (ec₂ {label₂}), ..., (ec_k {label_k})}.

The local set of labeled elemental constraints {lec₁, lec₂, ... , lec_k}is overall consistent iff the set-union of their associated label sets (È_i=1,k{label_i}) is not an I-L-Set.

Proof: The label set (È_i=1,k{label_i}) is the support-set of the simultaneous fulfillment of {lec₁, lec₂, --- , lec_k}. Moreover, the set of I-L-Sets is complete and sound with respect to overall TCN (Theorem 8), such that any label set not in the set of I-L-Set is overall consistent. Therefore (Theorem 2), (È_i=1,k{label_i}) and {lec₁, lec₂, ... , lec_k} are overall consistent iff È_i=1,k{label_i} is not an I-L-Set. à

Definition 5 (Labeled-consistency): Let’s assume a labeled-TCN of n nodes (and the corresponding complete set of I-L-Sets) and a set of k (1£k£()) constraints, each one of which is between any pair of nodes in the TCN:

{c_ij} / 1£i£n, 1£j£n, i¹j.

The set of constraints {c_ij} is labeled-consistent with respect to the nodes involved in these constraints, iff:

1. For each constraint c_ij, there exists an elemental labeled constraint elc_ij.x between (n_i, n_j) in the TCN such that elc_ij.x satisfies c_ij. That is: "c_ij, $elc_ij.xÎlc_ij / c_ij Å ec_ij.x ¹ Æ.
2. The resulting set of the union of label sets associated to these elemental labeled constraints (which satisfy {c_ij}) is not an I-L-Set:

is not an I-L-Set. Note that this is the condition of Theorem 9. à

Theorem 10. Let’s assume a labeled-TCN of n nodes (and the corresponding complete set of I-L-Sets) and a set of k (1£k£()) constraints, each one of which is between any pair of nodes in the TCN:

{c_ij} / 1£i£n, 1£j£n, i¹j.

The set of constraints {c_ij} is overall consistent iff {c_ij} is labeled-consistent with respect to the nodes involved in constraints {c_ij}.

Proof: The proof is trivial according to Definition 5 and Theorem 9. We have that the set of constraints {c_ij} is consistent iff there exists a local set of elemental constraints in the TCN {elc_ij.x} that makes {c_ij} labeled-consistent (Definition 5). Thus, the local set {elc_ij.x} is consistent (Theorem 9), such that {c_ij} is also consistent. à

For instance, we can determine whether any pair of constraints c'_ij and c'_kl can hold simultaneously (that is, they are overall consistent) if:

$elc_ij.xÎlc_ij / c'_ij Å ec_ij.x¹Æ Ù $elc_kl.yÎc_kl / c'_kl Å ec_kl.y¹Æ Ù {label_ij.x}È{label_kl.y}

is not an I-L-Set.

Moreover, any local instantiation of any k-1 (1<k£n) variables {t₁=v₁, t₂=v₂, ..., t_(k-1)=v_(k-1)} can be extended to a global solution if:

$elc_10.xÎlc₁₀ / v₁Îec_10.x,...... , $elc_(k-1)0.yÎlc_(k-1)0 / v_(k-1)Îec_10.x,

where lc_i0 is the constraint between n_i and T₀, and {label_10.x}È{label_20.y}È .... È{label_(k-1)0.y}is not and I-L-Set.

For instance, in Example 2 of Figure 10, the partial instantiation {(t₁=0), (t₂=5), (t₃=5)} is consistent. We have:

([0 45]_{{R0 R3}})Îlc₁₀ / 0Î[0 45], ([0 60]_{{R1 R0 R3}})Îlc₂₀ / 5Î[0 60], ([5 55]_{{R0 R1 R3}})Îlc₃₀ / 5Î[5 55],

and {R₀ R₃}È{R₀ R₁ R₃}È{R₀ R₁ R₃}={R₀ R₁ R₃} is not an IL-Set. Thus, this partial solution can be extended to a global solution. For instance, {(t₁=0), (t₂=5), (t₃=5), (t₄=25)}.

Therefore, a labeled-TCN can be considered as a globally labeled-consistent TCN. That is, on the basis of the concepts introduced by Dechter (1992):

Definition 6. (Local Labeled-consistency): A partial instantiation of variables (1£k<n) {t₁=v₁, t₂=v₂, ..., t_k=v_k} is local labeled-consistent if it is labeled-consistent with respect to (T₀, t₁, t₂, ..., t_k) nodes. This also holds for k=n. à

Definition 7. (Global Labeled-consistency): A labeled sub-TCN (with the global set of I-L-Sets) is global labeled-consistent if any partial instantiation of variables in the sub-TCN, which is local labeled-consistent, can be extended to the overall TCN. A globally labeled-consistent TCN is one in which all its sub-TCNs are globally labeled-consistent. à

Theorem 11. At each new assertion, the proposed reasoning processes obtain a globally labeled-consistent TCN, if they are applied on a previous minimal TCN and a previous sound and complete set of I-L-Sets.

Proof: The proof is trivial according to the previous definitions (Definition 6 and Definition 7) and to the properties of the reasoning processes (Theorem 7 and Theorem 8). Any partial instantiation in any subTCN, which is labeled-consistent with respect to the nodes involved in the partial instantiation, is overall consistent (Theorem 10). à

Similar expressions can be made for k-labeled-consistency and strong k-labeled-consistency on the basis of the concepts provided by Freuder (1982). Therefore, the set of I-L-Sets in a labeled-TCN provides a useful way to assure whether a local instantiation of variables can be part of a global solution. Moreover, Freuder (1982) shows that in a strong k-consistent TCN, consistent instantiations of variables of any subnetwork of size k can be found in a backtrack-free manner and in any variable ordering. This is also a consequence of the decomposability (Montanari, 1974; Dechter et al., 1991) or globally consistency (Dechter, 1992) properties. Obviously, this feature also holds for labeled TCNs.

Let’s analyze the computational cost of the proposed reasoning processes. These processes are, basically, an incremental path-consistent algorithm (Barber, 1993). At each updating process of a new input constraint on a TCN with n nodes, the computational cost of updating and closure processes is bounded by 'n² (O(Ä_lc) + O(Å_lc))'. In the proposed reasoning process, the path-consistent algorithm obtains a minimal disjunctive metric TCN. This is possible due to the management of labeled constraints, associated label sets, and I-L-Sets. Thus, the complexity of reasoning processes is mainly due (instead of a complex closure process) to the management of complex data structures (labeled constraints, associated label sets, and I-L-Sets). That is, the complexity of the proposed reasoning processes is mainly due to the complexity of operations Ä_lc and Å_lc.

The computational cost of Ä_lc and Å_lc depends on the number of elemental constraints in labeled constraints, the size of associated label sets, and the size of I-L-Sets in the previous minimal labeled TCN. Let 'n' be the number of nodes, 'l' the maximum number of disjuncts (or labels) in input constraints, and 'e' the number of updated input constraints in the previous TCN. The maximum number of labels in the TCN is l*e, since each disjunct in each updated input labeled constraint has its own, unequivocal label. Moreover, any I-L-Set can have as maximum one label from each input labeled constraint lc_ij, since: (i) elemental constraints in lc_ij are pairwise disjoint, such that each pair of labels in lc_ij is added to the set of I-L-Sets, and (ii) any superset of an existing I-L-Set is also an I-L-Set. Thus, the maximum number of labels in any I-L-Set is e. Furthermore, each label in an I-L-Set should be from a different input labeled constraint. There are e input labeled constraints, and each input labeled constraint has as maximum l labels. Thus, the maximum number of I-L-Sets of q-length (1£q£e) is (() l^q).

Therefore, the number of i-length (1£i£e) I-L-Sets is S_i=1,e (() lⁱ) = O(2^e l^e). However, any superset of an I-L-Set is already known as inconsistent, such that supersets are not stored in the set of I-L-Sets. Thus, the number of I-L-Set is bounded by O(l^e). Additionally, we also have e*() I-L-Sets of 2-length, since the l disjuncts in each updated constraint are mutually exclusive among them. Similarly, the maximum number of associated label sets is also bounded by O(l^e), each one with a maximum of e labels. Thus, the number of elemental constraints (or labeled subintervals) in any labeled constraint is bound by O(l^e), since each elemental constraint in a labeled constraint has its own associated label set.

According to these parameters, the computational cost of each updating process is bounded by O(n² l^3e). The recovery process of constraints has a constant cost, since a minimal-TCN is always maintained. The computational cost of the proposed algorithms agreed with the computational cost inherent to the problem of the management of disjunctive metric constraints (Dechter, 1991). In fact, the closure process could be considered as an integrated management of the l^e alternative non-disjunctive TCNs in which a disjunctive TCN can be split, as it is shown by Dechter, Meiri and Pearl (1991). It should be noted that l can be bounded in some typical problems like scheduling, where usually l£2 (Garrido et al., 1999), or by restricting domain size (range or granularity) in metric algebras. On the other hand, several improvements can be made on the described processes. For example, an efficient management of label sets has a direct influence on the efficiency of the reasoning processes. Thus, each label set (for instance, {R₃ R₅ R₈}) can be considered as a unidimensional array of bits, which is the binary representation of an integer number (for instance (2³+2⁵+2⁸)). Therefore, each associated label set is represented by a number and the set of I-L-Sets becomes a set of numbers. Matching and set-union processes on label sets in operations Ä_lc and Å_lc can be efficiently performed by means of operations on integer numbers with a constant cost. Therefore, the computational cost can be bounded by O(n² l^2e).

Other alternative implementations are under study. Two different approaches exist for temporal constraint management (Brusoni et al., 1997; Yampratoom, Allen, 1993; Barber, 1993). The first approach is to maintain a closured TCN by recomputing the TCN at each new input constraint and making the derived constraints explicit. Here, queries are answered in constant time, although this implies a high spatial cost. The second approach is to explicitly represent only input constraints, such that the spatial requirements are minimum. However, further computation is needed at query time and when consistency of each new input constraint is tested. The proposed reasoning methods hold 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, È_Tlc and Í_Tlc. 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³ l^e).

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 I_i⁺ I_i^-, integration of constraints on intervals and points seems to require some kind of non-binary 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.

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

I₁ {ec₁, ec₂} I₂, ec₁, ec₂ Î{b, m, o, d, s, f, e, bi, mi, oi, di, si, fi},

really means 'I₁ [ (ec₁ Ú ec₂) Ù Ø(ec₁ Ù ec₂) ] I₂', since ec₁ and ec₂ 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:

In this way, we have:

1. The constraints [I₁ (ec₁ Ú Øec₁) I₂] and [I1 (ec₂ Ú Øec₂) I₂] can be expressed as disjunctive metric constraints on the same pairs of time-points,
2. The constraints [I₁ Ø(ec₁ Ù ec₂) I₂] and [I₁ Ø(Øec₁ Ù Øec₂) I₂] can be expressed as a mutual exclusion among the associated labels of the above point-based constraints. That is, as a set of I-L-Sets.

We present a simple example to illustrate these conclusions. For instance, (I₁ {before after} I₂) can be expressed by means of constraints among the time points I₁^-, I₁⁺, I₂^- and I₂⁺, as:

[I₁ {b a} I₂] º (I₁⁺ {(0 ¥)_{Rb1}} I₂^-) Ú (I₁^- {(-¥ 0)_{Ra1}} I₂⁺).

Thus, when intervals are represented by means of their ending points I_i⁺ I_i^-, an interval-based constraint gives rise to disjunctive constraints between different pairs of time points (i.e.: non-binary constraints). These non-binary constraints can be represented as I-L-Sets. Thus, according to the above expression (e2),

[I₁ {b a} I₂] º [I₁ (b Ú Øb) I₂] Ù [I₁ (a Ú Øa) I₂] Ù [I₁ Ø(b Ù a) I₂] Ù [I₁ Ø(Øb Ù Øa) I₂],

we have:

Therefore, [I₁ {b a} I₂] can be expressed as:

which is equivalent to (by using the labels associated to each elemental constraint):

[I₁⁺ {(0 ¥)_{Rb1} (-¥ 0]_{Rb2}} I₂^-] Ù [I₁^- {(-¥ 0)_{Ra1} [0 ¥)_{Ra2}} I₂⁺]

and {R_b1 R_a1},{R_b2 R_a2} are I-L-Sets, such that one and only one disjunctive symbolic constraint holds.

Thus, symbolic constraints between intervals can be represented by means of: (i) a set of disjunctive metric constraints between time-points, and (ii) a set of I-L-Sets. In Table 1, the equivalent metric constraints between interval ending time points for each elemental interval-based constraint are detailed. According to this table, the following steps allow us to represent disjunctive symbolic constraints between intervals by means of disjunctive metric constraints between interval ending points and I-L-Sets:

1. Each interval I_i is represented by means of its ending points I_i⁺, I_i^-. By default, (I_i^- {(0, ¥)_{R0}} I_i⁺) holds.
2. A symbolic constraint between two intervals (I_i c_ij I_j) is composed of a disjunctive set of (from 1 to 13) elemental symbolic constraints c_ij={ec_ij.k}Í{b, m, o, d, s, f, e, bi, mi, oi, di, si, fi}.
3. Each elemental symbolic constraint ecÎ{b, m, o, d, s, f, e, bi, mi, oi, di, si, fi} is represented by a conjunctive set of disjunctive point-based metric constraints (fourth column of Table 1). This conjunctive set of point-based constraints expresses the ‘fulfillment or non-fulfillment’ (ec Ú Øec) of the elemental symbolic constraint ec.
4. A disjunctive set c_ij={ec_ij.k} of elemental symbolic constraints between I_i and I_j is represented by:

• A conjunctive set of disjunctive point-based metric constraints between the time-points I_i⁺, I_i^-, I_j⁺ and I^-_j. This conjunctive set is composed by the constraints in the fourth column of Table 1 for each elemental constraint in {ec_ij.k}.
• A set of I-L-Sets that expresses the logical relation among elemental symbolic constraints in {ec_ij.k}. That is, 'one and only one elemental symbolic constraint in {ec_ij.k} should hold':

For instance, I₁ {b m s di} I₂ can be represented as:

Moreover, one of the symbolic constraints in {b, m, s, di} should hold. Thus (according to Point iv.b of the method), the Cartesian product of the associated labels related to the non-fulfillment of each elemental symbolic constraints in {b, m, s, di}. That is:

{{R_b2}C{R_m2, R_m3}C{R_s3, R_s4, R_s5}C{R_d3, R_d4}

should be explicitly included in the set of I-L-Sets.

By applying this method, qualitative interval-based constraints can be fully integrated in the proposed labeled point-based constraints. In this case, the interpretation domain for time-points {I_i^- I_i⁺} can be restricted to only three values ({D}={(-¥, 0), [0 0], (0 ¥)}), such that, l=3. Therefore, the computational cost of reasoning algorithms is bounded by O(n² 3^2e).

To illustrate the proposed method, let’s show a typical example on symbolic interval-based constraints (Figure 11.a), which was given by Allen (1983). This example shows how interval-based constraints can be represented and managed by means of disjunctive metric point-based constraints and a minimal IA-TCN can be obtained.

Table 1: Interval-based constraints and their equivalent disjunctive metric constraints between interval ending points (Cells in the second and fourth columns are a conjunctive set of constraints)

Figure 11.a represents a path-consistent IA-TCN, which has inconsistent values in constraints (Allen, 1983). In Table 2, we have the interval-based symbolic constraints for this example, the corresponding disjunctive metric constraints between their ending time^-points (I_i⁺, I_i^-) and the corresponding set of I-L-Sets (according to Table 1). Moreover, we also have:

(IA^-{(0 ¥)_{R0}}IA⁺), (IB^-{(0 ¥)_{R0}}IB⁺), (IC^-{(0 ¥)_{R0}}IC⁺) and (ID^-{(0 ¥)_{R0}}ID⁺).

When all these metric constraints among the ending time-points of intervals are updated according the proposed methods in Section 4, the labeled minimal TCN in Table 3 is obtained. The associated labels to each elemental constraint (disjunct) in constraints are not included for reasons of brevity.

Figure 11: Path-Consistent and equivalent Minimal IA-TCN

Table 3: The minimal metric point-based TCN of the IA-TCN in Figure 11.a

Allen (1983) remarks that the symbolic constraint (IA {f fi} IC) cannot hold given the existing constraints between IA, IB, IC and ID. In the labeled point-based TCN, (IA {f fi} IC) is represented by a set of constraints among ending points of IA and IC. Moreover, the labels associated to each labeled elemental constraint allow us to determine whether a set of elemental constraints between different pairs of time-points can be part of a global solution (Theorem 10). Thus, we can deduce whether (IA {f fi} IC) can hold in the point-based TCN.

The existing constraints between the ending time-points of IC and IA, with their associated label-sets are:

Let's ask for each disjunct in (IA {f fi} IC):

1. The constraint (IA {f} IC) implies (IC⁺ {[0 0]} IA⁺) Ù (IC^- {(-¥ 0)} IA^-). According to Theorem 10, these constraints hold iff the set-union of the label sets associated to (IC⁺ [0 0] IA⁺) and to (IC^- (-¥ 0) IA^-) is not an I-L-Set. We have two possibilities:

In conclusion, the symbolic constraint (IA {f fi} IC) cannot hold on the globally labeled-consistent point-based TCN. This conclusion could be also obtained from a minimal IA-TCN (Figure 11.b). Additionally, we have that (IA {f fi} IC) implies (IA⁺ [0 0] IC⁺). That is, if the constraint (IA⁺ [0 0] IC⁺) holds, we have that the associated constraints to the label sets {R₂₅ R₃₀ R₂₉ R₁₇ R₂₂ R₂₁ R₀} or {R₂₇ R₂₈ R₂₉ R₁₉ R₂₀ R₂₁ R₀} should also hold. Each one of these label sets implies (IC^- {[0 0]} IA^-). That is: (IA⁺ [0 0] IC⁺) ® (IC^- {[0 0]} IA^-). Thus, the only way that (IA⁺ [0 0] IC⁺) can hold is if (IA {e} IC) holds. These relations will be detailed in Section 6.

Metric constraints between intervals can also be managed in the described temporal model. From a general point of view, metric information can be added to each elemental interval-based constraint in a standard way (Table 4). These metric constraints on interval boundaries (Table 4) are similar to the ones proposed by Staab and Hahn (1998).

Table 4: Metric interval constraints on interval boundaries

Obviously, the metric constraints of Table 4 can be managed in the proposed model, by means of metric constraints on interval ending points. Thus, symbolic constraints of Interval Algebra can be extended in this way to metric domain. However, since each interval is represented by means of its ending time-points, more flexible metric constraints on intervals can be represented by means of metric constraints on their ending time-points. In this way, the described model also subsumes the Interval Distance Sub Algebra model proposed by Badaloni and Berati (1996). Moreover, ending points of intervals can also be related to the initial time-point T₀, and unary metric constraints on interval durations can be expressed by means of metric constraints between the two ending points of each interval:

Thus, following constraints (Figure 12):

(I1 {b, o} I2) Ù (I1^- is [[20 30], [50 60]} before I2^-) Ù (I2^- is {[140 150], [200 210]} after T₀)

can be represented as (Table 1):

and {R_b2 R_o4}, {R_b2 R_o5}, {R_b2 R_o6}, {R₁ R₂} and {R₃ R₄} are I-L-Sets.

In the described model, each disjunct in an input constraint is univocally associated to a label. Moreover, the label set associated to each derived elemental constraint represents the support-set of input elemental constraints from which the elemental constraint is derived. I-L-Sets represent inconsistent sets of input elemental constraints. By reasoning on labeled disjunctive constraints, associated label lists and I-L-Sets, the temporal model offers the capability of reasoning on logical expressions of elemental constraints belonging to disjunctive constraints between different pairs of time points. Let's assume the following labeled input constraints:

(n_i lc_ij n_j) º (n_i {(lec_ij.1)_{Rij.1} (lec_ij.2) _{Rij.2} .....(lec_ij.p) _{Rij.p}} n_j),

(n_k lc_kl n_l) º (n_k {(lec_kl.1) _{Rkl.1} (lec_kl.2) _{Rkl.2} .....(lec_kll.q) _{Rkl.q}} n_l)

1. To represent that two elemental constraints (elc_ij.xÎlc_ij, elc_kl.yÎlc_kl) cannot hold simultaneously (that is Ø(elc_ij.x Ù elc_kl.y)) the label set {R_ij.x R_kl.y} should be added to the set of I-L-Sets.
1. To represent a logical dependency between two elemental constraints, such as 'If lec_ij.x then lec_kl.y' (where lec_ij.xÎc_ij, lec_kl.yÎc_kl), the Cartesian product {R_ij.x} C {{R_kl.1, R_kl.2, ....., R_kl.q}-{R_kl.y}} should be added to the set of I-L-Sets.
2. To represent that two elemental constraints (elc_ij.xÎlc_ij, elc_kl.yÎlc_kl) should hold simultaneously (bi-directional logical dependency), the Cartesian products {R_ij.x} C {{R_kl.1, R_kl.2, ....., R_kl.q}-{R_kl.y}} and {R_kl.y} C {{R_ij.1, R_ij.2, ....., R_ij.p}-{R_ij.x}} should be added to the set of I-L-Sets.

For instance, let’s see the Example 2 of Section 4.4 (Figure 10):

• To represent that ‘John goes to work by car and Fred goes to work walking’ is not possible, {R₁ R₅} should be asserted as an I-L-Set.
• To represent that ‘if John goes to work by car then Fred goes to work walking’, {R₁ R₃} and {R₁ R₄} should be asserted as I-L-Sets.
• To represent that ‘if John goes to work by car then Fred goes to work walking, and vice versa’, {R₁ R₃}, {R₁ R₄} and {R₅ R₂} should be asserted as I-L-Sets.

In a similar way, logical relations among point-based and interval-based elemental constraints can also be represented. For instance, the logical dependence "the duration of I₁ is [5 8] if I₂ is before I₃ and the duration of I₁ is [12 15] if I₂ is after I₃" can be represented as:

and {R₁ R_b11}, {R₂ R_b9} are I-L-Sets, since R_b11 is associated to ‘I₂ is after I₃’ and R_b9 is associated to ‘I₂ is before I₃’. Likewise, "I₁ starts at the same time as I₂ if t₁ occurs after t₂" can be represented as (see Table 1):

and {R₃ R_s3}, {R₃ R_s4}, and {R₃ R_s5} are I-L-Sets, since R₃ is associated to 't₁ occurs after t₂' and R_s3, R_s4 and R_s5 are associated to 'I₁ does not start at the same time as I₂'.

Disjunctions of constraints between different pairs of points and intervals can be represented in the proposed model by means of labeled constraints between points and a set of I-L-Sets. This subsumes the related expressiveness in the subset of disjunctive linear constraints proposed by Stergiou and Koubarakis (1998), where only disjunctions of constraints between different pairs of points are managed.

To represent a disjunctive set of disjunctive constraints between points, we have:

(n_i lc_ij n_j) Ú (n_k lc_kl n_l) can be represented as: (n_i {lc_ij ÚØlc_ij} n_j) Ù (n_k {lc_kl ÚØlc_kl} n_l),

and some logical relation among lc_ij, Ølc_ij, lc_kl and Ølc_kl. Thus, the disjunctive set of constraints:

can be represented as:

(n_i {(lec_ij.1)_{Rij.1}, (lec_ij.2)_{Rij.2}, ...., (lec_ij.p)_{Rij.p}, Ø{(lec_ij.1)_{Rij.1}, (lec_ij.2)_{Rij.2}, ...., (lec_ij.p)_{Rij.p}}} n_j) Ù

(n_k {(lec_kl.1)_{Rkl.1}, (lec_kl.2)_{Rkl.2}, ..., (lec_kj.q)_{Rkl.q}, Ø{(lec_kl.1)_{Rkl.1}, (lec_kl.2)_{Rkl.2}, ..., (lec_kj.q)_{Rkl.q}}} n_l)

º{(n_i {(lec_ij.1)_{Rij.1}, (lec_ij.2)_{Rij.2}, ..., (lec_ij.p)_{Rij.p}, (Ølec_ij.1)_{R'ij.1}, (Ølec_ij.2)_{R'ij.2}, ..., (Ølec_ij.p)_{R'ij.p}} n_j) Ù

(n_k {(lec_kl.1)_{Rkl.1}, (lec_kl.2)_{Rkl.2}, .., (lec_kj.q)_{Rkl.q}, (Ølec_kl.1)_{R'kl.1}, (Ølec_kl.2)_{R'kl.2}, ..., ( Ølec_kl.q)_{R'kl.q} } n_l)}

Thus, disjunctive and conjunctive sets of disjunctive constraints between points can be represented and managed by means of a conjunctive set of disjunctive constraints and a set of I-L-Sets. For example:

and

Table 5: Point-based constraints for (I₁ before I₂) and (I₃ before I₄)

Similarly, disjunctions of interval-based constraints between different pairs of intervals can also be represented. For instance, from Table 1 and Table 5, {(I₁ before I₂) Ú (I₃ before I₄)} can be represented as:

(I₁⁺ {(0 ¥)_{Rb1} (-¥ 0]_{Rb2}} I₂^-), (I₃⁺ {(0 ¥)_{Rb3} (-¥ 0]_{Rb4}} I₄^-),

and

Thus:

Table 6: Point-based constraints for (I₁ during I₂) and (I₃ starts I₄)

In a similar way (Table 6), (I₁ during I₂) Ú (I₃ starts I₄) º

(I₁^- {(-¥ 0)_{Rd1} [0 ¥)_{Rd3}} I₂^-), (I₁⁺ {(0 ¥)_{Rd2} (-¥ 0]_{Rd4}} I₂⁺),

(I₃^- {[0 0]_{Rs1} (0 ¥)_{Rs3} (-¥ 0)_{Rs4}} I₄^-), (I₃⁺ {(0 ¥)_{Rs2} (-¥ 0]_{Rs5}} I₄⁺),

and {R_d1 R_d2 R_s1 R_s2} and the Cartesian product {R_d3 R_d4} X {R_s3 R_s4 R_s5} are I-L-Sets.

Therefore, logical relations on elemental constraints can be represented by a set of I-L-Sets. Thus, a labeled TCN (and the set of I-L-Sets) can represent a special type of and/or TCN. These types of non-binary constraints enrich the expressiveness of language and allow for the modeling of more complex problems (Meiri, 1996). Stergiou and Koubarakis (1996) and Jonsson and Bäckström (1998) show that Disjunctions of Linear Constraints (DLR) are also able to represent these non-binary constraints. However, Pujari and Sattar (1999) remark that general methods from linear programming should then be applied for DLR management, such that specific temporal concepts (like the ones detailed in Section 2) are not considered in these general methods. In the proposed model, management of these non-binary constraints are performed by the proposed reasoning methods without increasing their computational complexity. The added functionality is of interest in several temporal reasoning problems, including planning, scheduling and temporal constraint databases (Barber et al., 1994; Gerevini & Schubert, 1995; Brusoni et al., 1997; Stergiou & Koubarakis, 1998; etc.) where no general solutions are provided in the specific temporal reasoning area.

In addition, the proposed reasoning algorithms obtain a globally labeled-consistent TCN (Theorem 11). This feature allows us to manage hypothetical queries, which is an important requirement in query processes on temporal constraint databases (Brusoni et al., 1997). Thus, queries such as Does c'_ij hold, if c'_kl? can be answered without any TCN propagation. The label set associated to each derived elemental constraint represents the set of input elemental constraints that should hold for the fulfillment of this elemental constraint. Therefore,

(x_k c'_kl x_l)®(x_i c'_ij x_j)

holds, if "elc_kl.yÎlc_kl / ec_kl.yÍc'_kl then $elc_ij.xÎlc_ij / ec_ij.xÍc'_ij and labels(elc_ij.x)Ílabels(elc_kl.y) hold.

For example, from the labeled minimal TCN in Figure 7, we have:

(T₁ {[40 40]} T₃) ® (T₂ { [0 0] } T₄), (T₃ { [20 20] } T₂) ® (T₃ { [20 20] } T₄).

However, (T₃ {[10 20]} T₂) does not imply (T₁ {[70 70]} T₄). Similarly, questions such as ‘Can c'_ij hold, if c'_kl?’ can also be easily answered by applying Theorem 9 and Theorem 10.

When we reason on temporal facts, we can simultaneously work on different alternative temporal contexts, situations, trends, plans, intentions or possible worlds (Dousson et al., 1993; Garcia & Laborie, 1996). This is usual in a branching (backward or forward) model of time. Here, we can have alternative past contexts (i.e.: different lines about how facts may have occurred) or alternative future contexts (i.e.: different lines about how facts may occur). Thus, temporal context management is also required in hypothetical or causal reasoning. Also, having different contexts permits a partition of the whole TCN in a set of independent chains in order to decrease the complexity problem size (Gerevini & Schubert, 1995). In this section, we do not deal with hypothetical reasoning issues. Our goal is temporal management of context-dependent constraints. Thus, in general, a hierarchy of alternative temporal contexts can be established, such that constraints can be associated to different temporal contexts. For instance, Figure 13 represents a hierarchy of alternative contexts, where W₀ represents the root context and there are different disjunctive constraints between (n₁, n₂) in each context. Temporal reasoning algorithms detailed in this paper are able to manage these context-dependent constraints:

• Input disjunctive constraints are asserted in different temporal contexts. To do this, the labels associated to input elemental constraints can also be used to represent the context in which the disjunctive is asserted. For instance (Figure 13), if the constraint:

• Label sets associated to context-dependent derived elemental constraints will represent the temporal contexts in which derived elemental constraints hold.

Definition 8. A context-dependent disjunctive constraint is a disjunctive constraint where each elemental constraint (i.e.: disjunct) is associated to an alternative temporal context. The universal labeled constraint is {(-¥ ¥)_{{W0 R0}}}, where W₀ is the root context. à

The proposed reasoning processes can manage context-dependent disjunctive constraints in a way similar to previously defined labeled disjunctive constraints (Section 3). For instance, according to the constraints and contexts in Figure 13, the following input labeled constraints between nodes n₁ n₂ should be updated:

(n1 {[0 100]{R1 W0}, [200 300]{R2 W0}} n2),	(n1 {[0 50]{R3 W1}, [200 210]{R4 W1}} n2),
(n1 {[60 100]{R5 W2}, [290 300]{R6 W2}} n2),	(n1 {[0 25]{R7 W3}, [260 280]{R8 W3}} n2),
(n1 { [0 25]{R0 W11}} n2),	(n1 { [30 50]{R9 W12}, [200 205]{R10 W12}} n2),
(n1 {[0 20]{R0 W31}, [210 215]{R0 W32}} n2),	(n1 {[260 280]{R0 W33}} n2).

The updating process of each new constraint c_ij in a given context W_p should assure the consistency of c_ij in the context W_p, as well as in its predecessor contexts (Figure 13). The consistency of c_ij with the successor contexts of W_p will be detailed in Section 7.2, since several options can be identified. However, it is not necessary to assure consistency among constraints belonging to contexts of different hierarchies. Successor contexts of a given context represent different alternatives, which are mutually exclusive. Thus, constraints belonging to contexts of different hierarchies can be mutually inconsistent. However, this does not imply that constraints in these contexts should necessarily be mutually disjoint. For instance (Figure 13), the constraints (n₁ {[0 50]_{{R3 W1}}, [200 210]_{{R4 W1}}} n₂) in context W₁ and (n₁ {[0 25]_{{R7 W3}}, [260 280]_{{R8 W3}}} n₂) in context W₃ are not mutually disjoint. However, W₁, W₂ and W₃ are assumed as three mutually exclusive alternatives of W₀.

The closure process of each new constraint c_ij in context W_p should downward propagate the new constraint c_ij to all its successor contexts (Figure 13). Moreover, no propagation should be performed to the predecessor contexts of context_k, nor among contexts of different hierarchies. Elemental constraints belonging to contexts of different hierarchies cannot be simultaneously considered, that is, combined or intersected.

The update and closure processes defined in Section 4 should be adapted in order to manage context-dependent disjunctive constraints. The Context-Update process (Figure 14) asserts the constraint c’_ijº{ec’₁, ec’₂, ..., ec’_n} in the context context_k. In a way similar to the updated process described in Section 4, Context-Update should be performed each time a new context-dependent constraint is asserted.

Figure 14: Context-Update process for context-dependent labeled constraints

Where:

• Put-label-context (c’_ij, context_k) associates an exclusive label set to each elemental constraint ec’_ij.pÎc’_ij. This label set has two labels {R_ij.p context_k}. In this label set, the first label is the label associated to each temporal disjunct. In a way similar to Put-labels function, these labels are mutually exclusive (Definition 3). The second label represents the context in which c’_ij is updated. Moreover, each pair of labels associated to successor contexts of the parent context of context_k is added to the I-L-Sets, since all the successor contexts of a given context are mutually exclusive:

• get (n_i, n_j, context_k) returns the set of labeled elemental constraints between n_i and n_j in the context_k (and in all its successor contexts). That is:

get (n_i, n_j, context_k)::= {(ec_ij.p{label_ij.p})Îlc_ij / context_kÎ{label_ij.p}}.

• get-upward (n_i, n_j, context_k), similarly to the previous get function, it returns the existing constraints between n_i and n_j in the context_k (and in all its successor contexts). However, if there is no constraint between n_i and n_j in the context_k, then the function returns the constraints between n_i and n_j that exist in the predecesor context of context_k:

The context-dependent closure (Figure 15) process is similar to the closure process described in Section 4 and it is also performed at each updating process. The closure process of each updated constraint in context_k is downwards performed in context_k and in all its successor contexts.

Figure 15: Context-Closure process for context-dependent labeled constraints

The resulting label set associated to each context-dependent derived elemental constraint represents the contexts where the elemental constraint holds, as well as the hierarchy of predecessor contexts of the elemental constraint. For instance, Figure 16 shows the contextual labeling for the example in Figure 13. Moreover, after successively performing the updating and closure processes for all constraints in this example, we have the following constraint between nodes n₁ and n₂:

(n₁ lc₁₂ n₂): (n₁ {[0 100]_{{R1 W0}}, [200 300]_{{R2 W0}}, [0 50]_{{R3 R1 W1 W0}}, [200 210]_{{R4 R2 W1 W0}}, (e3)

Figure 16: Labels in contexts

No closure process is performed among constraints belonging to contexts of different hierarchies. According to Put-label-context function, each pair of labels related to the successor contexts of each context is an I-L-Set. Thus, these I-L-Sets prevent deriving elemental constraints from contexts of different hierarchies. That is, each derived elemental constraint obtained (combining or intersecting) from two elemental constraints in contexts of different hierarchy will have an inconsistent associated label set. Therefore, these derived elemental constraints will be rejected in the operation È_lc. For instance, in the example of Figure 13, {{W₁, W₂}, {W₁, W₃}, {W₂, W₃}, {W₁₁, W₁₂}, {W₃₁, W₃₂}, {W₃₁, W₃₃}, {W₃₂, W₃₃}} are I-L-Sets. Thus, if a constraint is asserted in context W₁:

1. No propagation is performed using constraints in contexts W₁₁ and W₁₂ simultaneously, since {W₁₁, W₁₂} is an I-L-Set.
2. No propagation is performed in context W₂, nor in W₃, nor in their successors, since {W₁, W₂} and {W₁ W₃} are I-L-Sets.

Let's see an example of the Context-Update and Context-Closure processes. Let’s assume that the context-dependent constraints in Figure 13 are already updated and closured, such that the previous constraint lc₁₂ (expression e3) exists between n₁ and n₂. Now, we update (n₁ {[20 40]} n₂) in context W₁. The call to Consistency-Test function in the Context-Update function is:

Consistency-Test (get-upward (n₁, n₂, W₁), {[20 40]_{{R0 W1}}}).

Given the previous constraint lc₁₂ between n₁ and n₂ (expression e3), the function performs:

Thus, the new constraint (n₁ {[20 40]} n₂) is consistent in context W₁. Therefore, the constraint between n₁ n₂ results:

lc₁₂ ¬ (lc₁₂ - get (n₁, n₂, W₁)) È_lc (lc₁₂ Å_lc {[20 40]_{{R0 W1}}}) =