Journal of Artificial Intelligence Research 12 (2000) 35-86 Submitted 5/99; published 2/00 © 2000 AI Access Foundation and Morgan Kaufmann Publishers. All rights reserved. Reasoning on Interval and Point-based Disjunctive Metric Constraints in Temporal Contexts Federico Barber FBARBER@DSIC.UPV.ES Dpto. de Sistemas Informáticos y Computación Universidad Politécnica de Valencia Camino de Vera s/n, 46022 Valencia, Spain Abstract We introduce a temporal model for reasoning on disjunctive metric constraints on intervals and time points in temporal contexts. This temporal model is composed of a labeled temporal algebra and its reasoning algorithms. The labeled temporal algebra defines labeled disjunctive metric point- based constraints, where each disjunct in each input disjunctive constraint is univocally associated to a label. Reasoning algorithms manage labeled constraints, associated label lists, and sets of mutually inconsistent disjuncts. These algorithms guarantee consistency and obtain a minimal network. Additionally, constraints can be organized in a hierarchy of alternative temporal contexts. Therefore, we can reason on context-dependent disjunctive metric constraints on intervals and points. Moreover, the model is able to represent non-binary constraints, such that logical dependencies on disjuncts in constraints can be handled. The computational cost of reasoning algorithms is exponential in accordance with the underlying problem complexity, although some improvements are proposed. 1. Introduction 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, {A1, A2, ..., An}]?? Sj?". 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 'interval1 starts 2 seconds before interval2', 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 'interval1 {bef, aft} interval2' 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 'interval1 lasts 2 seconds more than interval2' 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 ‘(interval1 {bef, meets} interval2) ? (time- point3 is [10 20] from time-point4)’, or temporal-causal relations like ‘If (interval1 {bef, meets} interval2) then (time-point3 is [10 20] from time-point4)’ 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 ‘(interval1 {bef, meets} interval2) ? (time-point3 is [10 20] from time-point4) 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 (x1- y1?c1 ??x2-y2?c2 ? ....? xn-yn?cn), where xi and yi are time points, ci 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. 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. Time points are instantiated on D (ti?D), and temporal intervals can be modelled as pairs of ending time points that can be instantiated on D: Ii = (Ii-, Ii+), Ii?DxD, Ii-?Ii+. ? Temporal constraints between primitives, where each constraint relates n primitives: c1,2..n(x1, x2, ..., xn). 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 (xi cij xj), 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 (cij is a set of disjunctive basic constraints, ?cij??1) or non-disjunctive constraints. ? Operations between constraints. Mainly, Temporal Composition (?), Temporal Intersection (?), Temporal Union (??), and Temporal Inclusion (??). A temporal problem is specified by a set of n variables X= {xi}, an interpretation domain D and a finite set of temporal constraints between variables {(xi cij xj)}. A temporal problem gives rise to a Temporal Constraint Network (TCN) which can be represented as a directed graph where nodes represent temporal primitives (xi) and labeled-directed edges represent the binary constraints between them (cij). The Universal Constraint U is not usually represented in the graph, and each direct edge (representing cij) between xi and xj implies an inverse one (representing cji) between xj and xi. 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 (v1, v2, v3, ...,vn) / vi?D which represents the assignments of values {vi} to variables {xi}: (x1=v1, x2=v2, ...,xn=vn). 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 xi if there exists a TCN solution in which xi=v. The set of all feasible values of a variable xi is the minimal domain for the variable. A constraint (xi cij xj) is consistent if there exists a solution in which (xi cij xj) holds. A constraint cij 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 kth 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 (x1, x2, ..., xk, xj) is path-consistent iff for any value v1?d1 and vj?dj such that (x1=v1 c1j xj=vj) holds, there exists a sequence of values v2?d?, v3?d?, ..., vk?dk such that (v1 cl2 v2), (v2 c23 v3),...., and (vk ck,j vj) 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 (xi, x1, x2, ...,xk, xj) is path-consistent iff cij??? (ci1 ? c12? ... ? ckj). 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 ?cij,cik,ckj?TCN, cij ?? (cik ? ckj). 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. ?cij,cik,ckj?TCN: cij?cij ???cik ??ckj) 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 (x1=v1, x2=v2, ...,xk=vk) / 1?k0). Thus, ? The label R0 is associated to "John left home between 7:10 and 7:20", "Fred arrived at work between 8:00 and 8:10", and "John arrived at work about 10'-20' after Fred left home". This is the common context. ? The label R1 is associated to "John goes by bus", and R2 to "John goes by car". ? The label R3 is associated to "Fred goes in a carpool", and R4 to "Fred goes by car". Definition 2 (Inconsistent-Label-Sets). An Inconsistent-Label-Set (I-L-Set) is a set of labels {labeli} 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 {lecij.k} of an input disjunctive constraint lcij are pairwise disjoint. Thus, each 2-length set of labels from each pair of {lecij.k} is added to the set of I-L-Sets. That is, for each input constraint lcij ??{lecij.1, lecij.2, ..., lecij.l}, where lecij.k?(ecij.k{labelij.k}) and |{labelij.k}|=1: ?k,p?(1,..,l) / k?p, I-L-Sets ??I-L-Sets ? ({labelij.k}?{labelij.p}) ? In the example of Figure 1, {R1 R2} and {R3 R4} 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. 3.2 Operations on Labeled Constraints 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: lecij.k ?lc lecij.p = (ecij.k {labelij.k}) ?lc (ecij.p {labelij.p}) =def ecij.k ?T ecij.p ????labelij.k}???labelij.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. lcij ?lc lc’ij =def ?lecij.k?lcij, ?lc [{lecij.k} lc’ij] , where ?lc [{lecij.k} lc’ij] = (ecij.k{labelij.k}) ?lc lc’ij =def Inconsistent({labelij.k}) : lc’ij ?lecij.p?lc’ij / lecij.p?lc lecij.k : lc’ij (s1) Other : ({lc’ij} ? {lecij.k}) - ({lecij.p}, ?lecij.p?lc’ij ? lecij.k?lclecij.p) (s2). The function Inconsistent({labelij.k}) returns true if the set {labelij.k} is an I-L-Set or a superset of any existing I-L-Set (Theorem 1). Otherwise, it returns false: Inconsistent({labelij.k}) =def If ?{labels}?Inconsistent-Label-Sets / {labels}?{labelij.k} Then True Else 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 s1 and s2, 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 {labelij.k}, the elemental constraint (ecij.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. lcij ?lc lcjk =def ?lecij.p?lcij, ?lecjk.q?lcjk ?lc [ (ecij.p ? ecjk.q {labelij.p}?{labeljk.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 {R4 R2} 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 {R4 R1} 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 ?. lcij ?lc lc’ij =def ?lecij.k?lcij, ?lecij.p?lc’ij , ?lc [lecij.k ?lc lecij.p] where, lecij.k ?lc lecij.p =def If ecij.k ??ecij.p= ? Then {?} ;The Inconsistent-Constraint is returned. Else [(ecij.k ? ecij.p) ({labelij.k}?{labelij.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 {labelij.r} associated to each derived labeled-elemental constraint (ecij.r) is obtained from the set-union of labels associated to combined (?lc) or intersected (?lc) labeled-elemental constraints. Therefore, {labelij.r} represents the support set (composed of input elemental constraints) that implies the derived elemental constraint (ecij.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: (a ? (b ? c) = {[25 31], [35 70]} (a ? b) ? (a ? c) = {[25 70]}. 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 lci, lcj and lck. Thus, (lci ?lc lcj) ?lc (lci ?lc lck) can be expressed, according to the definition of operation ?lc, as: ??lecp?lci,??lecq?lcj, ?lc[(lecp??lc lecq)]) ?lc (?lecr?lci,??lecs?lck, ?lc[(lecr??lc lecs)]) = ?lecp?lci,??lecq?lcj,??lecr?lci, ?lecs?lck ??lc[(lecp??lc lecq)] ?lc ?lc[(lecr??lc lecs)]) which, according to the definition of ?lc, can be expressed as: ?lecp?lci,??lecq?lcj,??lecr?lci, ?lecs?lck ??lc[(lecp??lc lecq) ?lc (lecr??lc lecs)]) (e1) In this expression, lecp and lecr are elemental constraints of the same-labeled constraint lci. 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 lecp?lecr, then {labelp}?{labelr} is an I-L-Set. Thus, if lecp?lecr, the label set associated to (lecp??lc lecq) ?lc (lecr??lc lecs) is an I-L- Set. In consequence, (lecp??lc lecq) ?lc (lecr??lc lecs) is rejected in operation ?lc. That is, ?lecp?lci,??lecq?lcj,??lecr?lci, ?lecs?lck / lecp?lecr ??lc[(lecp??lc lecq) ?lc (lecr??lc lecs)]) = ?. Thus, the above expression (e1) results: ?lecp?lci,??lecq?lcj, ?lecs?lck ?(?lc [(lecp??lc lecq) ?lc (lecp??lc lecs)]). In this expression, ?lc clearly distributes over ?lc for elemental constraints (i.e.: non-disjunctive constraints). Therefore: ?lecp?lci,??lecq?lcj, ?lecs?lck ?(?lc [(lecp??lc (lecq ?lc lecs))]) = ?lecp?lci, ?lc [lecp??lc (?lecq?lcj, ?lecs?lck, ?lc [lecq ?lc lecs])] = lci ?lc (lcj ?lc lck). 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 {R1 R2}, {R3 R4} 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 ({[0 1]{R1}, [10 20]{R2}} ?lc {[0 30]{R3}, [40 50]{R4}}) = {[25 51]{R1 R0}, [35 70]{R2 R0}} ?lc {[0 31]{R1 R3}, [40 51]{R1 R4} [10 50]{R2 R3}, [50 70]{R2 R4}} = ?lc ([25 31]{R1 R3 R0}, [40 51]{R1 R4 R0}, [25 50]{R1 R2 R3 R0}, [50 51]{R1 R2 R4 R0}, [40 51]{R1 R2 R4 R0}, [35 50]{R3 R2 R0}, [50 70]{R4 R2 R0}). However, {R1 R2}, {R3 R4} 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). 4. Reasoning Algorithms on Labeled Constraints 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. 4.1 The Updating Process Given a previous labeled-TCN, composed by a set of nodes {ni}, a set of labeled constraints {lcij} among them, and a set of I-L-Sets, the updating process of each new c’ij between nodes ni and nj constraint is detailed in Figure 2. Updating (ni c’ij nj) ;c’ij?{ec’ij., ec’ij.2, ..., ec’ij.l}, a disjunctive metric constraint. lc'ij ??Put-Labels (c’ij), ;An exclusive label is associated to each elemental constraint ec’ij.k in c’ij If Consistency-Test (lcij ? lc'ij) ;Consistency test of lc'ij. The previously existing constraint between ni and nj is lcij. Moreover, new I-L-Sets are detected. Then (*Inconsistent Constraint*) Return (false) Else (*Consistent Constraint*) lcij? lcij ?lc lc'ij, lcji ??Inverselc (lcij), Closure (ni lcij nj), ;Closure algorithm for the updated constraint. Return (true) End-If End-Updating 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 {R0}. 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 Inverselc function is: Inverselc ({(ecij.k{labelij.k})}) =def {(Inverse (ecij.k) {labelij.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 ni and nj is consistent if it temporally intersects with the previously existing constraint lcij between these nodes. Moreover, the Consistency-Test function can detect new I-L-Sets: i) If the new constraint lc'ij is consistent with the existing constraint lcij, and two elemental constraints ecij.p?lc'ij, ecij.k?lcij do not intersect (ecij.k ??ecij.p=?), then the label set {labelij.k}?{labelij.p} is an I-L-Set and should be added to the current set of I-L-Sets. ii) If an existing elemental constraint between nodes ni and nj (lecij.k?lcij) does not intersect with the new constraint lc'ij, then {labelij.k} is an I-L-Set and should be added to the current set of I-L-Sets. Consistency-Test (lcij, lc’ij) = If (lcij ?lc lc’ij) = {?} Then Return (False) Else If ?lecij.k?lcij, ?lecij.p?lc'ij / lecij.k ?lc lecij.p={?} Then I-L-Sets ??I-L-Sets ? ({labelij.k}?{labelij.p}), If ?lecij.k?lcij / lecij.k??lc lc’ij = {?} Then I-L-Sets ??I-L-Sets ? {labelij.k}, End-If Return (True) End- Consistency-Test Figure 3: Consistency-Test function For example, Consistency-Test ({([0 10]{R1}), ([20 25]{R2}), ([100 110]{Ra})}?? {([0 30]{R3}), ([40 50]{R4}), ([-50 -40]{Rb})}) = True 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})} ? {?}. In this function, the label sets {R4 R2}, {R4 R1} 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 {Rb} does not need to be detected as an I-L-Set, since the label Rb 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 {R4 R2}, {R4 R1} do not need to be added to the set of I-L-Sets, since the label R4 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. i) No new I-L-Set that is superset of an existing I-L-Set is added to the set of I-L-Sets. ii) If an existing I-L-Set is superset of the new I-L-Set, then the existing I-L-Set is removed. iii) No new I-L-Set that contains a label of lc'ij, which does not appear in the labeled constraint (lcij ?lc lc'ij) to be added to the TCN, should be 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: Figure 4: The resulting labeled-TCN of Figure 1 before updating (t3 {[10 20]} t2) (t1 {[60 ??R1, [30 40]R2} t2), (t3 {[40 50]R3, [20 30]R4} t4), (T0 {[10 20]R0} t1), (T0 {[60 70]R0} t4). The resulting labeled-TCN is shown in Figure 4 and the set of I-L-Set is {{R1 R2}, {R3 R4}}. Now, we update (t3 {[10 20]R0} t2). The previously existing constraint between t3 and t2 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: {[10 20]{R0}} ?lc {([40 ?){R1 R3 R0}) ([20 ?){R1 R4 R0}), ([-10 30]{R2 R4 R0}) ([10 50]{R2 R3 R0})} = {[20 20]{R1 R4 R0}, [10 20]{R2 R0} [?]{R1 R3 R0}} ? {?} (e1) Thus, (t2-t3?{[10 20]{R0}}) is consistent. Moreover, {R1 R3 R0} is detected as an I-L-Set. The elemental constraints associated to {R1 R3 R0} are an inconsistent set of disjuncts that cannot hold simultaneously. That is: "If today John left home between 7:10 and 7:20 (R0), Fred arrived at work between 8:00 and 8:10 (R0) and John arrived at work about 10'-20' after Fred left home (R0), then it is impossible for John to have gone by bus (R1) and Fred to have gone in a carpool (R3)." 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 {R0 R1 R3} represents (Figure 1): ? ( (T0 [10 20] T1) ??(T3 [10 20] T2) ??(T0 [60 70] T4) ??(T3 [40 50] T4) ??(T1 [60 ?) T2)). 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. 4.2 The Closure Process 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. Closure (ni lcij nj) (* First loop: Closure ni ? nj ? nk *) ?nk?TCN / lcjk ? {U{R0}}: lcik ??lcik??lc (lcij ?lc lcjk), lcki ? Inverse(lcik) (* Second loop: Closure nj ? ni ? nl *) ?nl?TCN / lcil?? {U{R0}}: lcjl ??lcjl??lc (Inverse(lcij) ?lc?lcil), lclj ? Inverse(lcjl) (* Third loop: Closure nl ? ni ? nj ? nk*) ?nl, nk??TCN / lcli?? {U{R0}}, lcjk?? {U{R0}}: lclk ??lclk??lc (lcli ?lc lcij ?lc lcjk), lckl ??Inverse(lclk) End-Closure Figure 5: The closure process on labeled constraints Figure 6: Loops in the Closure Process The closure process has three loops (Figure 6). In these loops the process obtains: i) Derived constraints lcik between ni and any node nk, if nk is previously connected with nj (edge 1 of Figure 6). ii) Derived constraints lcljbetween nj and any node nl, if nl is previously connected with ni (edge 2 of Figure 6). Figure 7: The Labeled-Minimal TCN of the Example 1 iii) Derived constraints lclk between any pair of nodes nl and nk, if nl and nk are previously connected with ni and nj respectively (edge 3 of Figure 6). Let’s see the previous Example 1 represented in Figure 1 and Figure 4, when the consistent constraint (expression e1): (t3 {[20 20]{R1 R4 R0}, [10 20]{R2 R0}} t2) is closured. In the first loop of the closure process, we have: lc30 ? lc30 ?lc ({[20 20]{R1 R4 R0}, [10 20]{R2 R0}} ?lc lc20 = {[-30 -10]{R3 R0} [-50 -30]{R4 R0}} ?lc ({[20 20]{R1 R4 R0}, [10 20]{R2 R0}} ?lc {[-60 –40]{R2 R0} (-? -70]{R1 R0}}) = {[-30 -10]{R3 R0}} [-50 -30]{R4 R0}} ?lc {[-40 -20]{R1 R2 R4 R0}, (-? -50]{R1 R4 R0} [-50 –20]{R2 R0} (-? -50]{R1 R2 R0}}. However, {{R1 R2}, {R3 R4} {R0 R1 R3}} 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: lc30 ?{[-30 -10]{R3 R0}} [-50 -30]{R4 R0}} ?lc {(-? -50]{R1 R4 R0} [-50 –20]{R2 R0} }= {(-30 -20]{R2 R3 R0} [-50 –50]{R4 R1 R0} [-50 -30]{R4 R2 R0}}. Similarly, lc31 ? lc31 ?lc ({[20 20]{R1 R4 R0} [10 20]{R2 R0}} ?lc lc21 = {[-20 -10]{R3 R2 R0} [-40 -40]{R4 R1 R0} [-30 -10]{R4 R2 R0}} lc34 ? lc34 ?lc ({[20 20]{R1 R4 R0}, [10 20]{R2 R0}} ?lc lc24 = {[40 50]{R3 R2 R0} [20 30]{R4 R2 R0} [20 20]{R4 R1 R0}}. After the second and third loops, the final labeled-TCN is obtained (Figure 7). The final set of I-L- Sets is {{R1 R2}, {R3 R4} {R0 R1 R3}}. These sets represent all sets of mutually inconsistent input- elemental constraints that exist in the TCN of Figure 1. 4.3 Properties of Reasoning Algorithms 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 lcij (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: i) No derived constraint can exist between a pair of nodes if no path between them combines the asserted constraint lcij. ii) The closure process computes a derived constraint between any pair of nodes (nl, nk) that become connected by a path across the closured constraint lcij. Let’s assume an existing path between the nodes nx1, ny1 that includes lcij: nx1, nx2, nx3, ........, nx, (nj lcij nj), ny......, ny2, ny1 such that a derived constraint between nx1 ny1 should be computed. However, a minimal constraint between (nx1, ni) and between (nj, ny1) should already exist in the previous minimal TCN. In consequence, a derived constraint between (nx1, ny1) is computed in the third loop of the process. iii) If the previous TCN is minimal, all possible derived constraints that can exist between any pair of nodes (nl, nk) are already computed in the constraint lc’lk derived between these nodes in the proposed closure process. In the third loop, this process obtains: lc’lk=?lclk??lc (lcli ?lc lcij ?lc lcjk). Let’s suppose there exists another path between (nl, nk) across the updated lcij constraint: (nl, np, ni, nj, nq, nk). This path computes another derived constraint between (nl, nk): lc''lk=?lclk??lc (lclp ?lc lcpi ?lc lcij ?lc lcjq ?lc lcqk). However, since the previous TCN is minimal, the previously existing minimal constraints lcli and lcjk imply (lclp??lc lcpi) and (lcjq??lc lcqk), respectively. That is, lcli??lc(lclp ?lc lcpi) and lcjk??lc(lcjq ?lc lcqk) Thus, lc''lk is also implicitly implied by lc’lk (lc’lk?lclc''lk). Here, we have assumed the associative property for ?lc, which is obvious from its definition.? iv) Derived constraints obtained in the closure process do not need to be closured again if the previous TCN is minimal. That is, no constraint in the TCN would become more restricted if derived constraints were also closured. Let suppose lclk is modified in the third loop of closure process: lc’lk=?lclk??lc (lcli ?lc lcij ?lc lcjk) such that it should be propagated to the (nl, nk, np) subTCN (Figure 8). Thus, the following derived constraints should be obtained: lc’lp=?lclp??lc (lc’lk ?lc lckp) lc’pq=?lcpq??lc (lcpl ?lc lc’lk). For constraint lc’lp, we have, lc’lp = lclp??lc (lc’lk ?lc lckp) = lclp??lc ((lclk??lc (lcli ?lc lcij ?lc lcjk)) ?lc lckp). However, since ?lc distributes over ?lc, lc’lp = lclp??lc ((lclk ?lc lckp???lc (lcli ?lc lcij ?lc lcjk ?lc lckp)). Since the previous TCN is minimal, the minimal constraints lcpi and lcpj should previously exist, such that lclp?lc(lclk ?lc lckp? and lcjp?lc(lcjk ?lc lckp). Thus, lc’lp ?lc lclp??lc (lcli ?lc lcij ?lc lcjp). However, in the third loop of the closure process, the following derived constraint is computed: lc''lp = lclp ?lc (lcli ?lc lcij ?lc lcjp). Thus, lc’lp is already represented in the obtained constraint lc''lp (that is, lc''lp ?lc lc'lp?. In a similar way, lc''pq = lcpq ?lc (lcpi ?lc lcij ?lc lcjq) is also obtained in the proposed closure process, such that lc''pq ?lc lc'pq. Therefore, each derived constraint (any combinable path across lcij) between any pair of nodes in the TCN is computed, so that the closure process obtains a path-consistent TCN. ? i v ) 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. Proof: i) The new set of I-L-Sets is complete. The consistency test of the updated constraint lc'ij obtains all possible new I-L-Sets that can appear when lc'ij is added to the TCN, except those I-L-Sets which are related to the mutual exclusion of the disjuncts in lc'ij (which are determined in the Put-Label function): a) 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. b) 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 {Rk, R1, R2, ....., Rp} in which some new elemental constraint eck{Rk}?lc'ij takes part. Thus, the elemental constraints associated to {R1, R2, ....., Rp} compute a derived elemental constraint ecx between the nodes ni and nj: (ecx {R1, R2, ....., Rp}) / (ecx {R1, R2, ....., Rp}) ?lc (eck{Rk}) =? This elemental constraint ecx is already represented in the previously existing constraint lcij between ni and nj since the previous TCN is minimal . Thus, eck?ecx=?, such that the I-L- Set {Rk, R1, R2, ....., Rp} is detected in the consistency test of lc’ij. In conclusion, all new inconsistent sets of elemental constraints in which lc'ij participates are detected and no other new I-L-Sets can exist. Therefore, the new set of I-L-Sets is complete if the previous set of I-L-Sets is complete. ii) The new set of I-L-Sets is sound. All new I-L-Sets obtained represent inconsistent sets of elemental constraints. This is trivial, given the consistency test function. ? 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. 4.4 Global Labeled-Consistency 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