Journal of Artificial Intelligence Research 12 (2000) 3586 Submitted 5/99; published 2/00
© 2000 AI Access Foundation and Morgan Kaufmann Publishers. All rights reserved.
Reasoning on Interval and Pointbased
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 pointbased 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 contextdependent disjunctive metric constraints on intervals and points. Moreover, the model is able to represent nonbinary 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 timedependent entities. The goal is to determine what consequences (T) follow from a set of temporal constraints, "{TemporalConstraints}=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_{1}, A_{2}, ..., 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, knowledgebased 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 timepoints in temporal contexts. Moreover, special cases of nonbinary 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 tradeoff between representation expressiveness and complexity of reasoning algorithms. Qualitative Point Algebra (PA) (Vilain, Kautz & Van Beek, 1986) is a limited subset of intervalbased models. Interval Algebra (IA) introduced by Allen (1983) represents symbolic (qualitative) constraints between intervals but metric information, such as 'interval_{1} starts 2 seconds before interval_{2}', cannot be included. Metric (quantitative) pointbased 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_{1} {bef, aft} interval_{2}' 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 4tuplemetric 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_{1} lasts 2 seconds more than interval_{2}' require a highorder 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 nondisjunctive metric networks (Dechter et al., 1991). However, Vilain, Kautz and Van Beek (1986) also showed that determining the consistency of a generalcase temporal network (i.e.: disjunctive qualitative and metric constraints between points, intervals or durations) is NPhard. 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 pointinterval 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 NPcomplete.
On the other hand, these qualitative and metric temporal models do not manage certain types of nonbinary constraints, which are important for modeling some problems (scheduling, causal reasoning, etc.). For instance, disjunctive assertions like ‘(interval_{1} {bef, meets} interval_{2}) Ú (timepoint_{3} is [10 20] from timepoint_{4})’, or temporalcausal relations like ‘If (interval_{1} {bef, meets} interval_{2}) then (timepoint_{3} is [10 20] from timepoint_{4})’ 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 backtrackfree search (Dechter, 1992; Freuder, 1982). In particular, a global consistent network would allow us to handle conjunctive queries like ‘does ‘(interval_{1} {bef, meets} interval_{2}) Ù (timepoint_{3} is [10 20] from timepoint_{4}) 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 nondisjunctive metric constraints (x_{1}y_{1}£c_{1} Ú x_{2}y_{2}£c_{2} Ú ....Ú_{ }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 NPcomplete. 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 OrdHorn 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, kconsistency (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 contextdependent 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, adhoc 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 timepoints and intervals. The temporal model is based on timepoints as primitive, such that intervals are represented by means of their end timepoints. 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 pointbased metric constraint is associated to one unique label. In this way, pointbased constraints can be related among them without using hyperarcs. Therefore, metric and symbolic constraints among intervals and timepoints can be fully integrated, represented and managed by means of a labeled metric pointbased 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:
With these features, the proposed temporal model is suitable for modeling problems where these requirements appear. The computational cost of reasoning methods is nonpolynomial, 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 pointbased 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 pointbased constraints and management of nonbinary constraints are respectively described in Sections 5 and 6. Association of constraints to temporal contexts and management of contextdependent 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:
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 labeleddirected 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 IATCNs based on the Interval Algebra (Allen, 1983), PATCNs based on the Point Algebra (Vilain et al., 1986), or MetricTCNs based on the Metric Point Algebra (Dechter et al., 1991; Dean & McDermott, 1987). In this later case, disjunctive metric pointbased 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 ntuple (v_{1}, v_{2}, v_{3}, ...,v_{n}) / v_{i}ÎD which represents the assignments of values {v_{i}} to variables {x_{i}}: (x_{1}=v_{1}, x_{2}=v_{2}, ...,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 kconsistent iff (given any instantiation of any k1 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 (k1)length paths in the network are consistent, (ii) for each pair or nodes, there exists an interpretation that satisfies each (k1)length path between them, and (iii) each subTCN of knodes is consistent. As particular cases, 1consistency, 2consistency and 3consistency are called nodeconsistency, arcconsistency and pathconsistency, respectively (Mackworth, 1977; Montanari, 1974).
Pathconsistency is a common concept in constraint networks. From Montanari (1974) and Mackworth (1977), ‘a path of klength through nodes (x_{1}, x_{2}, ..., x_{k}, x_{j}) is pathconsistent iff for any value v_{1}Îd_{1} and v_{j}Îd_{j} such that (x_{1}=v_{1} c_{1j} x_{j}=v_{j}) holds, there exists a sequence of values v_{2}Îd_{2}, v_{3}Îd_{3}, ..., v_{k}Îd_{k} such that (v_{1} c_{l2} v_{2}), (v_{2} c_{23} v_{3}),...., and (v_{k} c_{k,j} v_{j}) hold’. A TCN is pathconsistent iff all its paths are consistent. Moreover, Montanari (1974) proves that to ensure pathconsistency it suffices to check every 2length path. Thus, pathconsistency and 3consistency are equivalent concepts. Alternatively, Meiri (1996) outlines a path of klength (x_{i}, x_{1}, x_{2}, ...,x_{k}, x_{j}) is pathconsistent iff c_{ij} Í_{T} (c_{i1} Ä c_{12}Ä ... Ä 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 arcconsistent, as the usual case in symbolic algebras. In metric algebras, pathconsistency usually assumes node and arcconsistency. Therefore, taking into account that it is only necessary to test 2length paths to assure pathconsistency, a TCN is pathconsistent iff "c_{ij},c_{ik},c_{kj}ÍTCN, c_{ij} Í_{T} (c_{ik} Ä c_{kj}). This condition gives rise to the more usual pathconsistent algorithm: the Transitive Closure Algorithm (TCA) which imposes local 3consistency in each subTCN of 3 nodes, such that all 2length paths become consistent paths (Mackworth, 1977; Montanari , 1974). The TCA algorithm will obtain an equivalent pathconsistent 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 kconsistent iff the network is jconsistent for all j£k (Freuder, 1982). An nconsistent TCN is a consistent TCN, and a strong nconsistent TCN is a minimal TCN. Alternatively, Dechter (1992) introduces the concepts of local and global consistency: A partial instantiation of variables (x_{1}=v_{1}, x_{2}=v_{2}, ...,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 nconsistent 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 minimalTCN, 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, CSPbased 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 generalcase TCN is NPhard, 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^{3} 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 kconsistency can guarantee consistency and obtain a minimal TCN, depending on the TCN topology or the underlying temporal algebra. For example, pathconsistency guarantees consistency and obtains a minimal nondisjunctive metric TCN (Dechter et al., 1991). The pathconsistency TCA Algorithm has an O(n^{3}) cost (Allen, 1983; Vilain, Kautz & Van Beek, 1986). However, assuring pathconsistency can become a complex task in disjunctive metricTCNs 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}xc_{jk}. Thus, the total number of disjuncts (subintervals) in a pathconsistent 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 nondisjunctive metric TCNs. Thus, the TCA algorithm is O(n^{3 }R^{3}) in disjunctive metricTCNs 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.
3. A Labeled Temporal Algebra
The main elements of the pointbased disjunctive metric temporal algebra are (Dechter et al., 1991):
c_{ij}º{[d^{}_{1} d^{+}_{1}], [d^{}_{2} d^{+}_{2}], ...., [d^{}_{k} d^{+}_{k}], ....., [d^{}_{l} d^{+}_{l}]} , where d^{}_{k}£d^{+}_{k} and d^{}_{k},d^{+}_{k}ÎD,
and disjunctively restricts the temporal distance between two timepoints, t_{i} and t_{j}:
t_{j}  t_{i} Î {[d^{}_{1} d^{+}_{1}], [d^{}_{2} d^{+}_{2}], ....., [d^{}_{l} d^{+}_{l}]},
meaning that (d^{}_{1}£t_{j}t_{i}£ d^{+}_{1}) Ú .... Ú (d^{}_{l}£ t_{j}t_{i}£ d^{+}_{l}). Similar conditions can be applied to open (d^{}_{k} d^{+}_{k}) and semiopen intervals (d^{}_{k} d^{+}_{k}], [d^{}_{k} d^{+}_{k}). The UniversalConstraint U is {(¥ +¥)}. Unary constraints restrict the associated subdomain of a timepoint t_{i}Î{[d^{}_{1} d^{+}_{1}], [d^{}_{2} d^{+}_{2}], ....., [d^{}_{l} d^{+}_{l}]}. A special timepoint T_{0} is usually included, which represents 'the beginning of the world' (usually, T_{0}=0). Thus, each unary constraint on t_{i} can be represented as a binary one between t_{i} and T_{0}:
t_{i}  T_{0} Î {[d^{}_{1} d^{+}_{1}], [d^{}_{2} d^{+}_{2}], ..... ,[d^{}_{l} d^{+}_{l}]} º t_{i}Î[d^{}_{1}, d^{+}_{1}] Ú t_{i}Î[d^{}_{2}, d^{+}_{2}] Ú, ..., Ú t_{i}Î[d^{}_{l}, d^{+}_{l}]
and, by default: "t_{i}, (T_{0} {[0 ¥)} t_{i}).
S Ä T = {d_{k} / $d_{i}ÎS Ù $d_{j}ÎT / d_{k}= d_{i}+d_{j}}.
That is, "[d_{S}^{}_{i}, d_{S}^{+}_{i}]ÎS, "[d_{T}^{}_{j}, d_{T}^{+}_{j}]ÎT, È_{T}{[d_{S}^{}_{i}+d_{T}^{}_{j}, d_{S}^{+}_{i}+d_{T}^{+}_{j}]}. Here, resulting subdomains in S Ä T may not be pairwise disjoint. Therefore, some additional processing may be required to compute a disjoint subdomain set.
S Å T = {d_{k} / d_{k}ÎS Ù d_{k}ÎT}. That is, the setintersection of their subdomains.
S È_{T} T = {d_{k} / d_{k}ÎS Ú d_{k}ÎT}, as the setunion of their subdomains.
SÍ_{T}T = iff "d_{k}ÎS, $d_{k}ÎT.
On the basis of the pointbased disjunctive metric temporal algebra and its operations, we introduce a labeled pointbased disjunctive metric temporal algebra, which gives rise to a labeledTCN.
3.1 Labeled Constraints and Inconsistent Label Sets
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}}.
ec_{ij.k }= [d^{}_{ij.k} d^{+}_{ij.k}] / "i,j,k d^{}_{ij.k}£d^{+}_{ij.k}
c_{ij} º{ec_{ij.1}, ec_{ ij.2}, ..., ec_{ ij.l}} Í U / "k,pÎ(1,..,l), k¹p, (ec_{ij.k} Å ec_{ ij.p})=Æ
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,
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}}º{label_{1}, label_{2}, ..., label_{s}} is a set of symbols.à
Each label_{ }in a labeledTCN can be considered as a unique symbol. The following cases can occur:
Let's see a simple example on labeled constraints, which was introduced by Dechter, Meiri and Pearl (1991).
Figure 1: The labeled pointbased disjunctive metric TCN of the Example 1
Example 1: "John goes to work either by car [30'40'], or by bus (at least 60'). Fred goes to work either by car [20'30'], or in a carpool [40'50']. Today John left home (t1) between 7:10 and 7:20, and Fred arrived (t4) at work between 8:00 and 8:10. We also know that John arrived (t2) at work about 10'20' after Fred left home (t3)."
In this example, we have the disjunctive labeled constraints in Figure 1, where T_{0} represents the initial time (7:00) and where the granularity is in minutes. A label 'R_{0}' is associated to elemental constraints belonging to constraints with only one disjunct. In constraints with more than one, mutually exclusive disjuncts, each disjunct is labeled with an exclusive label R_{n} (n>0). Thus,
Definition 2 (InconsistentLabelSets). An InconsistentLabelSet (ILSet) 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 ILSet is also an ILSet. 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 2length set of labels from each pair of {lec_{ij.k}} is added to the set of ILSets. 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, ILSets ¬ ILSets È ({label_{ij.k}}È{label_{ij.p}}) à
In the example of Figure 1, {R_{1} R_{2}} and {R_{3} R_{4}} are ILSets. Other ILSets 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:
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 setunion of their elemental constraints. However, all labeled elemental constraints whose associated labels are ILSets should be rejected.
lc_{ij} È_{lc} lc’_{ij} =_{def} "lec_{ij.k}Îlc_{ij}, È_{lc} [{lec_{ij.k}} lc’_{ij}] , where
È_{lc} [{lec_{ij.k}} lc’_{ij}]_{ }= (ec_{ij.k}{label_{ij.k}}) È_{lc} lc’_{ij }=_{def}
Inconsistent({label_{ij.k}}) : lc’_{ij}
$lec_{ij.p}Îlc’_{ij} / lec_{ij.p}Í_{lc }lec_{ij.k} : lc’_{ij }(s_{1})
Other : ({lc’_{ij}} È {lec_{ij.k}})  ({lec_{ij.p}}, "lec_{ij.p}Îlc’_{ij} Ù lec_{ij.k}Í_{lc}lec_{ij.p})_{ }(s_{2}).
The function Inconsistent({label_{ij.k}}) returns true if the set {label_{ij.k}} is an ILSet or a superset of any existing ILSet (Theorem 1). Otherwise, it returns false:
Inconsistent({label_{ij.k}}) =_{def}
If ${label_{s}}ÎInconsistentLabelSets / {label_{s}}Í{label_{ij.k}} Then True Else False.
The operation È_{lc} simplifies the resulting constraint. Equal or lessrestricted 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_{1} and s_{2}, 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 counterintuitive. However, note that the label set associated to each derivedlabeled elemental constraint represents the support set (composed of input elemental constraints) from which the derivedlabeled 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 pointbased 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 derivedlabeled 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 supportset of elemental constraints). If the label set {R_{4} R_{2}} becomes an ILSet, 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_{4} R_{1}} should be asserted as an ILSet.
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}]
where, lec_{ij.k} Å_{lc} lec_{ij.p} =_{def}
If ec_{ij.k} Å ec_{ij.p}= Æ Then {Æ} ;The InconsistentConstraint is returned.
Else [(ec_{ij.k} Å ec_{ij.p}) ({label_{ij.k}}È{label_{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 labeledelemental constraint (ec_{ij.r}) is obtained from the setunion of labels associated to combined (Ä_{lc}) or intersected (Å_{lc}) labeledelemental 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 ILSets is complete if it represents all inconsistent sets of TCN elemental constraints. A set of ILSets is sound if each ILSet represents an inconsistent set of elemental constraints. à
Theorem 2. Assuming a complete and sound set of ILSets, a labeled elemental constraint is consistent iff it has an associated label set which is not an ILSet. The proof is trivial, since the label set associated to each labeled elemental constraint represents its supportset. à
Theorem 3. Assuming a complete and sound set of ILSets, 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 ILSets. 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 nondisjunctive 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 ILSets, Ä_{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:
"lec_{p}Îlc_{i}, "lec_{q}Îlc_{j}, "lec_{r}Îlc_{i}, "lec_{s}Îlc_{k} (È_{lc}[(lec_{p} Ä_{lc} lec_{q}) Å_{lc} (lec_{r} Ä_{lc} lec_{s})]) (e1)
In this expression, lec_{p} and lec_{r} are elemental constraints of the samelabeled constraint lc_{i}. However, the setunion of label sets associated to each pair of elemental constraints in any (input or derived) labeled constraint is an ILSet (Definition 3). That is, if lec_{p}¹lec_{r}, then {label_{p}}È{label_{r}} is an ILSet. Thus, if lec_{p}¹lec_{r}, the label set associated to (lec_{p} Ä_{lc} lec_{q}) Å_{lc} (lec_{r} Ä_{lc} lec_{s}) is an ILSet. 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.: nondisjunctive 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_{1} R_{2}}, {R_{3} R_{4}} are ILSets. 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, {R_{1} R_{2}}, {R_{3} R_{4}} are ILSets. 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 wellknown Transitive Closure Algorithm, general closure algorithms as in (Dechter, 1992; Dechter et al., 1991; van Beek & Dechter, 1997), CSPbased approaches, etc. However, Montanari (1974) shows that when composition operation distributes over intersection, any pathconsistent TCN is also a minimal TCN. From Theorem 4, we have that Ä_{lc} distributes over Å_{lc}. Thus, application of a pathconsistent algorithm on the proposedlabeled 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 pathconsistent algorithm for nondisjunctive 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 ILSets.
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 labeledTCN, composed by a set of nodes {n_{i}}, a set of labeled constraints {lc_{ij}} among them, and a set of ILSets, the updating process of each new c’_{ij} between nodes n_{i} and n_{j} constraint is detailed in Figure 2.
Updating (n_{i} c’_{ij} n_{j}) ;c’_{ij}º{ec’_{ij.}, ec’_{ij.2}, ..., ec’_{ij.l}}, a disjunctive metric constraint.
lc'_{ij} ¬ PutLabels (c’_{ij}), ;An exclusive label is associated to each elemental constraint ec’_{ij.k} in c’_{ij}
If ConsistencyTest (lc_{ij} , lc'_{ij}) ;Consistency test of lc'_{ij}. The previously existing constraint between n_{i} and n_{j} is lc_{ij}. Moreover, new ILSets are detected.
Then (*Inconsistent Constraint*)
Return (false)
Else (*Consistent Constraint*)
lc_{ij}¬ lc_{ij }Å_{lc} lc'_{ij}, lc_{ji} ¬ Inverse_{lc} (lc_{ij}),
Closure (n_{i} lc_{ij} n_{j}), ;Closure algorithm for the updated constraint.
Return (true)
EndIf
EndUpdating
Figure 2: Updating process on labeled constraints
The function PutLabels(c’_{ij}) returns a labeledconstraint 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_{0}}. Otherwise, each pair of labels in lc’_{ij} is added to the set of ILSets, since elemental constraints in c’_{ij} are pairwise disjoint (Definition 3). By using the Inverse function on nonlabeled 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 ILSets 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 (ConsistencyTest 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 ConsistencyTest Function
The ConsistencyTest 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 ConsistencyTest function can detect new ILSets:
ConsistencyTest (lc_{ij}, lc’_{ij}) =
If (lc_{ij} Å_{lc} lc’_{ij}) = {Æ}
Then Return (False)
Else
If $lec_{ij.k}Îlc_{ij}, $lec_{ij.p}Îlc'_{ij} / lec_{ij.k} Å_{lc} lec_{ij.p}={Æ}
Then ILSets ¬ ILSets È ({label_{ij.k}}È{label_{ij.p}}),
If $lec_{ij.k}Îlc_{ij} / lec_{ij.k} Å_{lc} lc’_{ij} = {Æ}
Then ILSets ¬ ILSets È {label_{ij.k}},
EndIf
Return (True)
End ConsistencyTest
Figure 3: ConsistencyTest function
For example,
ConsistencyTest ({([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}})} ¹ {Æ}.
Moreover, the label sets {R_{4} R_{2}}, {R_{4} R_{1}} and {Ra} are detected as ILSets and should be added to the current set of ILSets, 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 ILSet, 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 ILSet is also an ILSet (Theorem 1). Moreover, note that {R_{4} R_{2}}, {R_{4} R_{1}} do not need to be added to the set of ILSets, since the label R_{4} is not included in the final constraint. Therefore, the following simplifications can also be performed each time a new ILSet is added to the current set of ILSets. These simplifications do not modify the results of reasoning processes, but minimize the size of the set of ILSets and improve its management efficiency.
Let’s see an example of the updating and consistencytest processes. Let’s take the labeledTCN that results from Example 1 once the following constraints have been updated and closured:
(t_{1} {[60 ¥)_{R1}, [30 40]_{R2}} t_{2}), (t_{3} {[40 50]_{R3}, [20 30]_{R4}} t_{4}), (T_{0} {[10 20]_{R0}} t_{1}), (T_{0} {[60 70]_{R0}} t_{4}).
Figure 4: The resulting labeledTCN of Figure 1 before updating (t_{3} {[10 20]} t_{2})
The resulting labeledTCN is shown in Figure 4 and the set of ILSet is {{R_{1} R_{2}}, {R_{3} R_{4}}}. Now, we update (t_{3} {[10 20]_{R0}} t_{2}). The previously existing constraint between t_{3} and t_{2} is (Figure 4):
{([40 ¥)_{{R1 R3 R0}}) ([20 ¥)_{{R1 R4 R0}}), ([10 30]_{{R2 R4 R0}}) ([10 50]_{{R2 R3 R0}})}
The ConsistencyTest 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, (t2t3Î{[10 20]_{{R0}}}) is consistent. Moreover, {R_{1} R_{3} R_{0}} is detected as an ILSet. The elemental constraints associated to {R_{1} R_{3} R_{0}} are an inconsistent set of disjuncts that cannot hold simultaneously. That is:
"If today John left home between 7:10 and 7:20 (R_{0}), Fred arrived at work between 8:00 and 8:10 (R_{0}) and John arrived at work about 10'20' after Fred left home (R_{0}), then it is impossible for John to have gone by bus (R_{1}) and Fred to have gone in a carpool (R_{3})."
The set of ILSets 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 ILSet {R_{0} R_{1} R_{3}} represents (Figure 1):
Ø ( (T_{0} [10 20] T_{1}) Ù (T_{3} [10 20] T_{2}) Ù (T_{0} [60 70] T_{4}) Ù (T_{3} [40 50] T_{4}) Ù (T_{1} [60 ¥) T_{2})).
This expression is a nonbinary 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 (n_{i} lc_{ij} n_{j})
(* First loop: Closure n_{i} ® n_{j} ® n_{k }*)
"n_{k}ÎTCN / lc_{jk} ¹_{ }{U_{{R0}}}:
lc_{ik} ¬ lc_{ik} Å_{lc} (lc_{ij} Ä_{lc} lc_{jk}), lc_{ki} ¬ Inverse(lc_{ik})
(* Second loop: Closure n_{j} ® n_{i} ® n_{l} *)
"n_{l}ÎTCN / lc_{il} ¹_{ }{U_{{R0}}}:
lc_{jl} ¬ lc_{jl} Å_{lc} (Inverse(lc_{ij}) Ä_{lc} lc_{il}), lc_{lj} ¬ Inverse(lc_{jl})
(* Third loop: Closure n_{l} ® n_{i} ® n_{j} ® n_{k}*)
"n_{l}, n_{k} ÎTCN / lc_{li} ¹_{ }{U_{{R0}}}, lc_{jk} ¹_{ }{U_{{R0}}}:
lc_{lk} ¬ lc_{lk} Å_{lc} (lc_{li} Ä_{lc} lc_{ij} Ä_{lc} lc_{jk}), lc_{kl} ¬ Inverse(lc_{lk})
EndClosure
Figure 5: The closure process on labeled constraints
The closure process has three loops (Figure 6). In these loops the process obtains:
Figure 7: The LabeledMinimal 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_{3} {[20 20]_{{R1 R4 R0}}, [10 20]_{{R2 R0}}} t_{2})
is closured. In the first loop of the closure process, we have:
lc_{30} ¬ lc_{30} Å_{lc} ({[20 20]_{{R1 R4 R0}}, [10 20]_{{R2 R0}}} Ä_{lc} lc_{20} =
{[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, {{R_{1} R_{2}}, {R_{3} R_{4}} {R_{0} R_{1} R_{3}}} are ILSets. No labeled elemental constraints whose associated label set is a superset of these ILSets will be derived (Theorem 3). Thus:
lc_{30} ¬{[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,
lc_{31} ¬ lc_{31} Å_{lc} ({[20 20]_{{R1 R4 R0}} [10 20]_{{R2 R0}}} Ä_{lc} lc_{21} =
{[20 10]_{{R3 R2 R0}}_{ }[40 40]_{{R4 R1 R0} }[30 10]_{{R4 R2 R0}}}
lc_{34} ¬ lc_{34} Å_{lc} ({[20 20]_{{R1 R4 R0}}, [10 20]_{{R2 R0}}} Ä_{lc} lc_{24} =
{[40 50]_{{R3 R2 R0}} [20 30]_{{R4 R2 R0} }[20 20]_{{R4 R1 R0}}}.
After the second and third loops, the final labeledTCN is obtained (Figure 7). The final set of ILSets is {{R_{1} R_{2}}, {R_{3} R_{4}} {R_{0} R_{1} R_{3}}}. These sets represent all sets of mutually inconsistent inputelemental 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 lc_{ij} (ConsistencyTest function).à
Theorem 6. The proposed closure algorithm obtains a pathconsistent TCN, if it is applied over a previous minimal TCN.
Proof: This was detailed by Barber (1993) for nondisjunctive 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 lc_{ij}.
ii) The closure process computes a derived constraint between any pair of nodes (n_{l}, n_{k}) that become connected by a path across the closured constraint lc_{ij}. Let’s assume an existing path between the nodes n_{x1}, n_{y1} that includes lc_{ij}:
n_{x1}, n_{x2}, n_{x3}, ........, n_{x}, (n_{j} lc_{ij} n_{j}), n_{y}......, n_{y2}, n_{y1}
such that a derived constraint between n_{x1} n_{y1} should be computed. However, a minimal constraint between (n_{x1}, n_{i}) and between (n_{j}, n_{y1}) should already exist in the previous minimal TCN. In consequence, a derived constraint between (n_{x1}, n_{y1}) 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 (n_{l}, n_{k}) 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}= lc_{lk} Å_{lc} (lc_{li} Ä_{lc} lc_{ij} Ä_{lc} lc_{jk}).
Let’s suppose there exists another path between (n_{l}, n_{k}) across the updated lc_{ij} constraint: (n_{l}, n_{p}, n_{i}, n_{j}, n_{q}, n_{k}). This path computes another derived constraint between (n_{l}, n_{k}):
lc''_{lk}= lc_{lk} Å_{lc} (lc_{lp} Ä_{lc} lc_{pi} Ä_{lc} lc_{ij} Ä_{lc} lc_{jq} Ä_{lc} lc_{qk}).
However, since the previous TCN is minimal, the previously existing minimal constraints lc_{li} and lc_{jk} imply (lc_{lp} Ä_{lc} lc_{pi}) and (lc_{jq} Ä_{lc} lc_{qk}), respectively. That is, lc_{li} Í_{lc}(lc_{lp} Ä_{lc} lc_{pi}) and lc_{jk} Í_{lc}(lc_{jq} Ä_{lc} lc_{qk}) Thus, lc''_{lk} is also implicitly implied by lc’_{lk} (lc’_{lk}Í_{lc}lc''_{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 lc_{lk} is modified in the third loop of closure process:
lc’_{lk}= lc_{lk} Å_{lc} (lc_{li} Ä_{lc} lc_{ij} Ä_{lc} lc_{jk})
such that it should be propagated to the (n_{l}, n_{k}, n_{p}) subTCN (Figure 8). Thus, the following derived constraints should be obtained:
lc’_{lp}= lc_{lp} Å_{lc} (lc’_{lk} Ä_{lc} lc_{kp}) lc’_{pq}= lc_{pq} Å_{lc} (lc_{pl} Ä_{lc} lc’_{lk}).
For constraint lc’_{lp}, we have,
lc’_{lp }= lc_{lp} Å_{lc} (lc’_{lk} Ä_{lc} lc_{kp}) = lc_{lp} Å_{lc} ((lc_{lk} Å_{lc} (lc_{li} Ä_{lc} lc_{ij} Ä_{lc} lc_{jk})) Ä_{lc} lc_{kp}).
However, since Ä_{lc} distributes over Å_{lc},
lc’_{lp} = lc_{lp} Å_{lc} ((lc_{lk} Ä_{lc} lc_{kp}) Å_{lc} (lc_{li} Ä_{lc} lc_{ij} Ä_{lc} lc_{jk} Ä_{lc} lc_{kp})).
Since the previous TCN is minimal, the minimal constraints lc_{pi} and lc_{pj} should previously exist, such that lc_{lp}Í_{lc}(lc_{lk} Ä_{lc} lc_{kp}) and lc_{jp}Í_{lc}(lc_{jk} Ä_{lc} lc_{kp}). Thus,
lc’_{lp} Í_{lc} lc_{lp} Å_{lc} (lc_{li} Ä_{lc} lc_{ij} Ä_{lc} lc_{jp}).
However, in the third loop of the closure process, the following derived constraint is computed:
lc''_{lp} = lc_{lp} Å_{lc} (lc_{li} Ä_{lc} lc_{ij} Ä_{lc} lc_{jp}).
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} = lc_{pq} Å_{lc} (lc_{pi} Ä_{lc} lc_{ij} Ä_{lc} lc_{jq})
is also obtained in the proposed closure process, such that lc''_{pq} Í_{lc} lc'_{pq}.
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 pathconsistent TCN. à
iv) 
Figure 8: lc_{lk} is also propagated to lc_{lp} and lc_{pq} 
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 pathconsistent TCN is also a minimal TCN). This is the case in nondisjunctive 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 ILSets (Definition 4), if they are applied on a previous minimal TCN and a previous sound and complete set of ILSets.
Proof:
i) The new set of ILSets is complete. The consistency test of the updated constraint lc'_{ij} obtains all possible new ILSets that can appear when lc'_{ij} is added to the TCN, except those ILSets which are related to the mutual exclusion of the disjuncts in lc'_{ij} (which are determined in the PutLabel function):
(ec_{x} _{{R1, R2, ....., Rp}}) / (ec_{x} _{{R1, R2, ....., Rp}}) Å_{lc} (ec_{k{Rk}}) =Æ
This elemental constraint ec_{x} is already represented in the previously existing constraint lc_{ij} between n_{i} and n_{j} since the previous TCN is minimal. Thus, ec_{k}Åec_{x}=Æ, such that the ILSet {R_{k}, R_{1}, R_{2}, ....., R_{p}} 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 ILSets can exist. Therefore, the new set of ILSets is complete if the previous set of ILSets is complete.
ii) The new set of ILSets is sound. All new ILSets 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 minimalTCN (Figure 9). Therefore, the reasoning algorithms guarantee TCN consistency and obtain a minimal TCN and a complete and sound set of ILSets at each new input assertion.
4.4 Global LabeledConsistency
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 ILSets (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 ILSets. 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):
Example 2: "Dave goes walking to work in [25’ 50’]. John goes to work either by car [10’ 30'], or by bus [45’ 60’]. Fred goes to work either by car [15' 20'], or in a carpool [35' 40'], or walking [55’ 60’]. Today, they all left their home between 6:50 and 7:50 (at t_{1}, t_{2} and t_{3} timepoints), and arrived at work at just the same time (t_{4}) before 8:00."
Here, we have the following labeled disjunctive constraints where, T_{0} represents the initial time (6:50) and granularity is in minutes:
t_{1} T_{0} Î {[0 60]_{R0}}, t_{2} T_{0} Î {[0 60]_{R0}}, t_{3} T_{0} Î {[0 60]_{R0}}, t_{4} T_{0} Î {[0 70]_{R0}},
t_{4}  t_{1} Î {[25 50]_{R0}}, t_{4} – t_{2} Î {[10 30]_{R1}, [45 60]_{R2}}, t_{4} – t_{3} Î {[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 timepoint and T_{0} represent unary constraints and restrict interpretation domains for variables (t_{1}, t_{2}, t_{3}, t_{4}). Obviously, this minimal TCN is not a globally consistent TCN. For instance, instantiations {(t_{1}=0), (t_{2}=0), (t_{3}=0)} are consistent with the existing constraints involved among (T_{0}, t_{1}, t_{2}, t_{3}), 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_{0}, t_{1}, t_{2}, t_{3}):
(T_{0} {[5 45]_{{R0 R5}}, [0 45]_{{R0 R4}}, [0 45]_{{R0 R3}}} t_{1}),
(T_{0} {[0 25]_{{R2 R0}}, [5 60]_{{R1 R0 R4}}, [25 60]_{{R1 R0 R5}}, [0 60]_{{R1 R0 R3}}} t_{2}),
(T_{0} {[25 55]_{{R0 R2 R3}}, [0 15]_{{R0 R5}}, [0 35]_{{R0 R1 R4}}, [5 55]_{{R0 R1 R3}}, [5 35]_{{R0 R2 R4}}} t_{3}),
(t_{1} {([5 35]_{{R0 R2}}, [40 5]_{{R0 R1}}} t_{2}),
(t_{1} {[15 15]_{{R0 R4}}, [35 5]_{{R0 R3}}, [5 35]_{{R0 R5}}} t_{3}),
(t_{2} {[5 30]_{{R1 R0 R4}}, [45 25]_{{R2 R0 R3}}, [25 50]_{{R1 R0 R5}}, [15 10]_{{R1 R0 R3}}, [25 5]_{{R2 R0 R4}}, [5 15]_{{R2 R0 R5}}} t_{3}).
The set of ILSets is {{R_{1} R_{2}} {R_{3} R_{4}} {R_{3} R_{5}} {R_{4} R_{5}}}. From this labeled TCN and the set of ILSets, we can deduce that instantiations {(t_{1}=0), (t_{2}=0), (t_{3}=0)} are not overall consistent. These instantiations are not locally consistent with the labeled constraints in the subTCN (T_{0}, t_{1}, t_{2}, t_{3}): All label sets associated to possible simultaneous fulfillment of
(T_{0} {[0 0]} t_{1}), (T_{0} {[0 0]} t_{2}) and (T_{0} {[0 0]} t_{3})
are ILSets. That is, all label sets in the Cartesian product
{{R_{0 }R_{4}}_{ }{R_{0 }R_{3}}} C {{R_{2 }R_{0}}_{ }{R_{1 }R_{0 }R_{3}}} C {{R_{0 }R_{5}}_{ }{R_{0 }R_{1 }R_{4}}}
are ILSets. Thus, the set of ILSets can be used to deduce consistency of a set of labeled elemental constraints and to obtain a globally consistent labeledTCN.
Theorem 9. Let’s assume a labeledTCN of n nodes (and the corresponding complete and sound set of ILSets) 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_{1}, lec_{2},....., lec_{k}} º {(ec_{1} {label_{1}}), (ec_{2} {label_{2}}), ..., (ec_{k} {label_{k}})}.
The local set of labeled elemental constraints {lec_{1}, lec_{2}, ... , lec_{k}}is overall consistent iff the setunion of their associated label sets (È_{i=1,k}{label_{i}}) is not an ILSet.
Proof: The label set (È_{i=1,k}{label_{i}}) is the supportset of the simultaneous fulfillment of {lec_{1}, lec_{2},  , lec_{k}}. Moreover, the set of ILSets is complete and sound with respect to overall TCN (Theorem 8), such that any label set not in the set of ILSet is overall consistent. Therefore (Theorem 2), (È_{i=1,k}{label_{i}}) and {lec_{1}, lec_{2}, ... , lec_{k}} are overall consistent iff È_{i=1,k}{label_{i}} is not an ILSet. à
Definition 5 (Labeledconsistency): Let’s assume a labeledTCN of n nodes (and the corresponding complete set of ILSets) 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 labeledconsistent with respect to the nodes involved in these constraints, iff:
is not an ILSet. Note that this is the condition of Theorem 9. à
Theorem 10. Let’s assume a labeledTCN of n nodes (and the corresponding complete set of ILSets) 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 labeledconsistent 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}} labeledconsistent (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 ILSet.
Moreover, any local instantiation of any k1 (1<k£n) variables {t_{1}=v_{1}, t_{2}=v_{2}, ..., t_{(k1)}=v_{(k1)}} can be extended to a global solution if:
$elc_{10.x}Îlc_{10} / v_{1}Îec_{10.x},...... , $elc_{(k1)0.y}Îlc_{(k1)0} / v_{(k1)}Îec_{10.x},
where lc_{i0} is the constraint between n_{i} and T_{0}, and {label_{10.x}}È{label_{20.y}}È .... È{label_{(k1)0.y}}is not and ILSet.
For instance, in Example 2 of Figure 10, the partial instantiation {(t_{1}=0), (t_{2}=5), (t_{3}=5)} is consistent. We have:
([0 45]_{{R0 R3}})Îlc_{10} / 0Î[0 45], ([0 60]_{{R1 R0 R3}})Îlc_{20} / 5Î[0 60], ([5 55]_{{R0 R1 R3}})Îlc_{30} / 5Î[5 55],
and {R_{0} R_{3}}È{R_{0} R_{1} R_{3}}È{R_{0} R_{1} R_{3}}={R_{0} R_{1} R_{3}} is not an ILSet. Thus, this partial solution can be extended to a global solution. For instance, {(t_{1}=0), (t_{2}=5), (t_{3}=5), (t_{4}=25)}.
Therefore, a labeledTCN can be considered as a globally labeledconsistent TCN. That is, on the basis of the concepts introduced by Dechter (1992):
Definition 6. (Local Labeledconsistency): A partial instantiation of variables (1£k<n) {t_{1}=v_{1}, t_{2}=v_{2}, ..., t_{k}=v_{k}} is local labeledconsistent if it is labeledconsistent with respect to (T_{0}, t_{1}, t_{2}, ..., t_{k}) nodes. This also holds for k=n. à
Definition 7. (Global Labeledconsistency): A labeled subTCN (with the global set of ILSets) is global labeledconsistent if any partial instantiation of variables in the subTCN, which is local labeledconsistent, can be extended to the overall TCN. A globally labeledconsistent TCN is one in which all its subTCNs are globally labeledconsistent. à
Theorem 11. At each new assertion, the proposed reasoning processes obtain a globally labeledconsistent TCN, if they are applied on a previous minimal TCN and a previous sound and complete set of ILSets.
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 labeledconsistent with respect to the nodes involved in the partial instantiation, is overall consistent (Theorem 10). à
Similar expressions can be made for klabeledconsistency and strong klabeledconsistency on the basis of the concepts provided by Freuder (1982). Therefore, the set of ILSets in a labeledTCN 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 kconsistent TCN, consistent instantiations of variables of any subnetwork of size k can be found in a backtrackfree 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.
4.5 Analysis of Temporal Complexity
Let’s analyze the computational cost of the proposed reasoning processes. These processes are, basically, an incremental pathconsistent 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^{2} (O(Ä_{lc}) + O(Å_{lc}))'. In the proposed reasoning process, the pathconsistent algorithm obtains a minimal disjunctive metric TCN. This is possible due to the management of labeled constraints, associated label sets, and ILSets. 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 ILSets). 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 ILSets 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 ILSet 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 ILSets, and (ii) any superset of an existing ILSet is also an ILSet. Thus, the maximum number of labels in any ILSet is e. Furthermore, each label in an ILSet 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 ILSets of qlength (1£q£e) is (() l^{q}).
Therefore, the number of ilength (1£i£e) ILSets is S_{i=1,e} (() l^{i}) = O(2^{e} l^{e}). However, any superset of an ILSet is already known as inconsistent, such that supersets are not stored in the set of ILSets. Thus, the number of ILSet is bounded by O(l^{e}). Additionally, we also have e*() ILSets of 2length, 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^{2} l^{3e}). The recovery process of constraints has a constant cost, since a minimalTCN 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 nondisjunctive 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_{3} R_{5} R_{8}}) can be considered as a unidimensional array of bits, which is the binary representation of an integer number (for instance (2^{3}+2^{5}+2^{8})). Therefore, each associated label set is represented by a number and the set of ILSets becomes a set of numbers. Matching and setunion 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^{2} 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 ILSets and a globally labeledconsistent TCN. Regrettably, assembling a solution in a labeled TCN, although backtrack free, is also costly due to the exponential number of ILSets. However, these features offer the capability of representing and managing special types of nonbinary disjunctive constraints (later detailed in Section 6).
Other reasoning algorithms for query processes on a nonclosured 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}, È_{T}lc and Í_{T}lc. For instance, the TCA algorithm as is applied by Allen (1983), and the kconsistency algorithms like those described in (Cooper, 1990; Freuder, 1978). Moreover, a minimal TCN of labeled constraints can be obtained without enforcing global consistency; for example, by applying the naive backtracking algorithm described by Dechter, Meiri and Pearl (1991), which is O(n^{3 }l^{e}).
5. IntervalBased Constraints Through Labeled PointBased Constraints
The integration of quantitative and qualitative information has been the goal of several temporal models, as was described in Section 1. When intervals are represented by means of their ending points I_{i}^{+} I_{i}^{}, integration of constraints on intervals and points seems to require some kind of nonbinary constraints between timepoints (Gerevini & Schubert, 1995; Schwalb & Dechter, 1997; Drakengren & Jonsson, 1997). In this section, the proposed temporal model is applied in order to integrate interval and pointbased constraints. Constraints on intervals are managed by means of constraints on ending points of intervals and ILSets. Likewise, metric information can also be added to interval constraints such that an expressive way of integrating qualitative and quantitative constraints is obtained.
5.1 Symbolic IntervalBased Constraints
Symbolic constraints on intervals express the qualitative temporal relation between two intervals. Each symbolic constraint is a disjunctive subset of 13 elemental constraints, which are mutually exclusive among them (Allen, 1983). For example, the following constraint
I_{1} {ec_{1}, ec_{2}} I_{2}, ec_{1}, ec_{2} Î{b, m, o, d, s, f, e, bi, mi, oi, di, si, fi},
really means 'I_{1} [ (ec_{1} Ú ec_{2}) Ù Ø(ec_{1} Ù ec_{2}) ] I_{2}',_{ }since ec_{1} and ec_{2} 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:
I_{1} [ (ec_{1} Ù Øec_{2}) Ú (Øec_{1} Ù ec_{2}) ] I_{2} º
I_{1} [ (ec_{1} Ú Øec_{1}) Ù (ec_{2} Ú Øec_{2}) Ù Ø(ec_{1} Ù ec_{2}) Ù Ø (Øec_{1} Ù Øec_{2}) ] I_{2} (e2).
In this way, we have:
We present a simple example to illustrate these conclusions. For instance, (I_{1} {before after} I_{2}) can be expressed by means of constraints among the time points I_{1}^{}, I_{1}^{+}, I_{2}^{} and I_{2}^{+}, as:
[I_{1} {b a} I_{2}] º (I_{1}^{+} {(0 ¥)_{{Rb1}}} I_{2}^{})^{ }Ú (I_{1}^{} {(¥ 0)_{{Ra1}}} I_{2}^{+}).
Thus, when intervals are represented by means of their ending points I_{i}^{+} I_{i}^{}, an intervalbased constraint gives rise to disjunctive constraints between different pairs of time points (i.e.: nonbinary constraints). These nonbinary constraints can be represented as ILSets. Thus, according to the above expression (e2),
[I_{1} {b a} I_{2}] º [I_{1} (b Ú Øb) I_{2}] Ù [I_{1} (a Ú Øa) I_{2}] Ù [I_{1} Ø(b Ù a) I_{2}] Ù [I_{1} Ø(Øb Ù Øa) I_{2}],
we have:
I_{1} before I_{2} Û I_{1}^{+} {(0 ¥)_{{Rb1}}} I_{2}^{}, I_{1} Øbefore I_{2} Û I_{1}^{+} {(¥ 0]_{{Rb2}}} I_{2}^{}, 
I_{1} after I_{2} Û I_{1}^{} {(¥ 0)_{{Ra1}}} I_{2}^{+}, I_{1} Øafter I_{2} Û I_{1}^{} {[0 ¥)_{{Ra2}}} I_{2}^{+}. 
Therefore, [I_{1} {b a} I_{2}] can be expressed as:
[I_{1}^{+} {(0 ¥)_{{Rb1}} (¥ 0]_{{Rb2}}} I_{2}^{}]^{ }Ù [I_{1}^{} {(¥ 0)_{{Ra1}} [0 ¥)_{{Ra2}}} I_{2}^{+}] Ù
Ø [ (I_{1}^{+} {(0 ¥)_{{Rb1}}} I_{2}^{}) Ù (I_{1}^{} {(¥ 0)_{{Ra1}}} I_{2}^{+}) ] Ù
Ø[ (I_{1}^{+} {(¥ 0]_{{Rb2}}} I_{2}^{})^{ }Ù (I_{1}^{} {[0 ¥)_{{Ra2}}} I_{2}^{+}) ],
which is equivalent to (by using the labels associated to each elemental constraint):
[I_{1}^{+} {(0 ¥)_{{Rb1}} (¥ 0]_{{Rb2}}} I_{2}^{}] Ù [I_{1}^{} {(¥ 0)_{{Ra1}} [0 ¥)_{{Ra2}}} I_{2}^{+}]
and {R_{b1} R_{a1}},{R_{b2} R_{a2}} are ILSets, 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 timepoints, and (ii) a set of ILSets. In Table 1, the equivalent metric constraints between interval ending time points for each elemental intervalbased 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 ILSets:
iv.a) Only one elemental constraint in {ec_{ij.k}} should hold. This condition does not need to be represented since the different sets of pointbased constraints that correspond to fulfillment of different elemental symbolic constraints (second column of Table 1) are already mutually exclusive.
iv.b) One of the elemental symbolic constraints in {ec_{ij.k}} should hold. Let S be the label sets, where each label set corresponds to the pointbased constraints which are related to the nonfulfillment of each elemental symbolic constraint in {ec_{ij.k}} (third column of Table 1). Thus, the Cartesian product among the label sets in S is a set of ILSets.
For instance, I_{1} {b m s di} I_{2} can be represented as:
(I_{1}^{} { (0 ¥)_{{R0}}} I_{1}^{+}), (I_{2}^{} { (0 ¥)_{{R0}}} I_{2}^{+}),
I_{1} {b Øb} I_{2} 
Þ 
(I_{1}^{+} {(0 ¥)_{{Rb1}} (¥ 0]_{{Rb2}}} I_{2}^{}), 

I_{1} {m Øm} I_{2} 
Þ 
(I_{1}^{+} {[0 0]_{{Rm1}} (0 ¥)_{{Rm2}} (¥ 0)_{{Rm3}}} I_{2}^{}), 

I_{1} {s Øs} I_{2} 
Þ 
(I_{1}^{} {[0 0]_{{Rs1}} (0 ¥)_{{Rs3}} (¥ 0)_{{Rs4}}} I_{2}^{}) Ù (I_{1}^{+} {(0 ¥)_{{Rs2}} (¥ 0]_{{Rs5}}} I_{2}^{+}), 

I_{1} {di Ødi} I_{2} º I_{2} {d Ød} I_{1} 
Þ 
(I_{2}^{} {(¥ 0)_{{Rd1}} [0 ¥)_{{Rd3}}} I_{1}^{}) Ù (I_{2}^{+} {(0 ¥)_{{Rd2}} (¥ 0]_{{Rd4}}} I_{1}^{+}). 
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 nonfulfillment 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 ILSets.
By applying this method, qualitative intervalbased constraints can be fully integrated in the proposed labeled pointbased constraints. In this case, the interpretation domain for timepoints {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^{2} 3^{2e}).
To illustrate the proposed method, let’s show a typical example on symbolic intervalbased constraints (Figure 11.a), which was given by Allen (1983). This example shows how intervalbased constraints can be represented and managed by means of disjunctive metric pointbased constraints and a minimal IATCN can be obtained.
I_{i} ec_{ij.k} I_{j} 
I_{i} ec_{ij.k} I_{j} 
I_{i} Øec_{ij.k} I_{j} 
I_{i} (ec_{ij.k} Ú Øec_{ij.k}) I_{j} 
I_{i} before I_{j} 
I_{i}^{+} {(0 ¥)_{{Rb1}}} I_{j}^{} 
I_{i}^{+} {(¥ 0]_{{Rb2}}} I_{j}^{} 
I_{i}^{+} {(0 ¥)_{{Rb1}} (¥ 0]_{{Rb2}}} I_{j}^{} 
I_{i} meets I_{j} 
I_{i}^{+} {[0 0]_{{Rm1}}} I_{j}^{} 
I_{i}^{+} {(0 ¥)_{{Rm2}} (¥ 0)_{{Rm3}}} I_{j}^{} 
I_{i}^{+} {[0 0]_{{Rm1}} (0 ¥)_{{Rm2}} (¥ 0)_{{Rm3}}} I_{j}^{} 
I_{i} during I_{j} 
I_{i}^{} {(¥ 0)_{{Rd1}}} I_{j}^{} I_{i}^{+} {(0 ¥)_{{Rd2}}} I_{j}^{+} 
(I_{i}^{} {[0 ¥)_{{Rd3}}} I_{j}^{}) Ú (I_{i}^{+} {(¥ 0]_{{Rd4}}} I_{j}^{+}) 
I_{i}^{} {(¥ 0)_{{Rd1}} [0 ¥)_{{Rd3}}} I_{j}^{} I_{i}^{+} {(0 ¥)_{{Rd2}} (¥ 0]_{{Rd4}}} I_{j}^{+} 
I_{i} starts I_{j} 
I_{i}^{} {[0 0]_{{Rs1}}} I_{j}^{} I_{i}^{+} {(0 ¥)_{{Rs2}}} I_{j}^{+} 
(I_{i}^{} {(0 ¥)_{{Rs3}} (¥ 0)_{{Rs4}}} I_{j}^{}) Ú (I_{i}^{+} {(¥ 0]_{{Rs5}}} I_{j}^{+}) 
I_{i}^{} {[0 0]_{{Rs1}} (0 ¥)_{{Rs3}} (¥ 0)_{{Rs4}}} I_{j}^{} I_{i}^{+} {(0 ¥)_{{Rs2}} (¥ 0]_{{Rs5}}} I_{j}^{+} 
I_{i} finishes I_{j} 
I_{i}^{+} {[0 0]_{{Rf1}}} I_{j}^{+} I_{i}^{} {(¥ 0)_{{Rf2}}} I_{j}^{} 
(I_{i}^{+} {(0 ¥)_{{Rf3}} (¥ 0)_{{Rf4}}} I_{j}^{+}) Ú (I_{i}^{} {[0 ¥)_{{Rf5}}} I_{j}^{}) 
I_{i}^{+} {[0 0]_{{Rf1}} (0 ¥)_{{Rf3}} (¥ 0)_{{Rf4}}} I_{j}^{+} I_{i}^{} {(¥ 0)_{{Rf2}} [0 ¥)_{{Rf5}}} I_{j}^{} 
I_{i} overlaps I_{j} 
I_{i}^{+} {(¥ 0)_{{Ro1}}} I_{j}^{} I_{i}^{+ }{(0 ¥)_{{Ro2}}} I_{j}^{+} I_{i}^{ }{(0 ¥)_{{Ro3}}} I_{j}^{} 
(I_{i}^{+} {[0 ¥)_{{Ro4}}} I_{j}^{}) Ú (I_{i}^{+ }{(¥ 0]_{{Ro5}}} I_{j}^{+}) Ú (I_{i}^{ }{(¥ 0]_{{Ro6}}} I_{j}^{}) 
I_{i}^{+} {(¥ 0)_{{Ro1}} [0 ¥)_{{Ro4}}} I_{j}^{} I_{i}^{+ }{(0 ¥)_{{Ro2}} (¥ 0]_{{Ro5}}} I_{j}^{+} I_{i}^{ }{(0 ¥)_{{Ro3}} (¥ 0]_{{Ro6}}} I_{j}^{} 
I_{i} equal I_{j} 
I_{i}^{+} {[0 0]_{{Re1}}} I_{j}^{+} I_{i}^{} {[0 0]_{{Re2}}} I_{j}^{} 
(I_{i}^{+} {(0 ¥)_{{Re3}} (¥ 0)_{{Re4}}} I_{j}^{+}) Ú (I_{i}^{} {(0 ¥)_{{Re5}} (¥ 0)_{{Re6}}} I_{j}^{}) 
I_{i}^{+} {(0 ¥)_{{Re3}} [0 0]_{{Re1}} (¥ 0)_{{Re4}}} I_{j}^{+} I_{i}^{} {(0 ¥)_{{Re5}} [0 0]_{{Re2}} (¥ 0)_{{Re6}}} I_{j}^{} 
Table 1: Intervalbased constraints and their equivalent disjunctive metric constraints between interval ending points_{ }(Cells in the second and fourth columns are a conjunctive set of constraints)
Symbolic Constraint 

Disjunctive Metric Constraint between I^{+} I^{} 
InconsistentLabelSets 
(IA {d di} IB) 
Þ 
IA^{} {(¥ 0)_{{R1}} [0 ¥)_{{R3}}} IB^{} IA^{+} {(0 ¥)_{{R2}} (¥ 0]_{{R4}}} IB^{+} IB^{} {(¥ 0)_{{R5}} [0 ¥)_{{R7}}} IA^{} IB^{+} {(0 ¥)_{{R6}} (¥ 0]_{{R8}}} IA^{+} 
{R_{4} R_{8}} {R_{3} R_{8}} {R_{4} R_{7}} {R_{3} R_{7}} 
(IB {d di} IC) 
Þ 
IB^{} {(¥ 0)_{{R9}} [0 ¥)_{{R11}}} IC^{} IB^{+} {(0 ¥)_{{R10}} (¥ 0]_{{R12}}} IC^{+} IC^{} {(¥ 0)_{{R13}} [0 ¥)_{{R15}}} IB^{} IC^{+} {(0 ¥)_{{R14}} (¥ 0]_{{R16}}} IB^{+} 
{R_{12} R_{16}} {R_{11} R_{16}} {R_{12} R_{15}} {R_{11} R_{15}} 
(ID {m s} IA) 
Þ 
ID^{+} {[0 0]_{{R17}} (0 ¥)_{{R18}} (¥ 0)_{{R19}}} IA^{} ID^{} {[0 0]_{{R20}} (0 ¥)_{{R22}} (¥ 0)_{{R23}}} IA^{} ID^{+} {(0 ¥)_{{R21}} (¥ 0]_{{R24}}} IA^{+} 
{R_{19} R_{24}} {R_{18} R_{24}} {R_{19} R_{23}} {R_{18} R_{23}} {R_{19} R_{22}} {R_{18} R_{22}} 
(ID {o} IB) 
Þ 
ID^{+} {(¥ 0)_{{R0}}} IB^{} ID^{+} {(0 ¥)_{{R0}}} IB^{+} ID^{} {(0 ¥)_{{R0}}} IB^{} 

(ID {m s} IC) 
Þ 
ID^{+} {[0 0]_{{R25}} (0 ¥)_{{R26} (¥ 0)_{{R27}}} IC^{} ID^{} {[0 0]_{{R28}} (0 ¥)_{{R30}} (¥ 0)_{{R31}}} IC^{} ID^{+} {(0 ¥)_{{R29}} (¥ 0]_{{R32}}} IC^{+} 
{R_{27} R_{32}} {R_{26} R_{32}} {R_{27} R_{31}} {R_{26} R_{31}} {R_{27} R_{30}} {R_{26} R_{30}} 
Table 2: Symbolic constraints in Figure 11.a by means of disjunctive metric constraints between I^{+}, I^{}
Figure 11.a represents a pathconsistent IATCN, which has inconsistent values in constraints (Allen, 1983). In Table 2, we have the intervalbased symbolic constraints for this example, the corresponding disjunctive metric constraints between their ending time^{}points (I_{i}^{+}, I_{i}^{}) and the corresponding set of ILSets (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 timepoints 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.
a) PathConsistent IATCN 
b) Minimal IATCN 
Figure 11: PathConsistent and equivalent Minimal IATCN

IA^{+} 
IA^{} 
IB^{+} 
IB^{} 
IC^{+} 
IC^{} 
ID^{+} 
ID^{} 
IA^{+} 

{(¥ 0)} 
{(0 ¥), (¥ 0)} 
{(¥ 0)} 
{(¥ ¥)} 
{(¥ 0)} 
{(¥ 0)} 
{(¥ 0)} 
IA^{} 
{(0 ¥)} 

{(0 ¥)} 
{(¥ 0), (0 ¥)} 
{(0 ¥)} 
{(¥ 0), [0 0], (0 ¥)} 
{[0 0], (0 ¥)} 
{(¥ 0), [0 0]} 
IB^{+} 
{(¥ 0), (0 ¥)} 
{(¥ 0)} 

{(¥ 0)} 
{(¥ 0), (0 ¥)} 
{(¥ 0)} 
{(¥ 0)} 
{(¥ 0)} 
IB^{} 
{(0 ¥)} 
{(0 ¥), (¥ 0)} 
{(0 ¥)} 

{(0 ¥)} 
{(¥ 0), (0 ¥)} 
{(0 ¥)} 
{(¥ 0)} 
IC^{+} 
{(¥ ¥)} 
{(¥ 0)} 
{(¥ 0), (0 ¥)} 
{(¥ 0)} 

{(¥ 0)} 
{(¥ 0)} 
{(¥ 0)} 
IC^{} 
{(0 ¥)} 
{(¥ 0), [0 0], (0 ¥)} 
{(0 ¥)} 
{(¥ 0), (0 ¥)} 
{(0 ¥)} 

{(0 ¥), [0 0]} 
{(¥ 0), [0 0]} 
ID^{+} 
{(0 ¥)} 
{(¥ 0), [0 0]} 
{(0 ¥)} 
{(¥ 0)} 
{(0 ¥)} 
{(¥ 0), [0 0]} 

{(¥ 0)} 
ID^{} 
{(0 ¥)} 
{[0 0], (0 ¥)} 
{(0 ¥)} 
{(0 ¥)} 
{(0 ¥)} 
{[0 0], (0 ¥)} 
{(0 ¥)} 

Table 3: The minimal metric pointbased TCN of the IATCN 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 pointbased 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 timepoints can be part of a global solution (Theorem 10). Thus, we can deduce whether (IA {f fi} IC) can hold in the pointbased TCN.
The existing constraints between the ending timepoints of IC and IA, with their associated labelsets are:
IC^{+} {(¥ ¥)_{{R25 R30 R29 R17 R22 R21 R0)Ú{R27 R28 R29 R19 R20 R21 R0}},
(¥ 0)_{{R27 R28 R29 R17 R22 R21 R9 R10 R15 R16 R1 R2 R7 R0 R8}},
(0 ¥)_{{R25 R30 R29 R19 R20 R21 R11 R12 R13 R14 R3 R4 R5 R0 R6}}} IA^{+}
IC^{} {(0 ¥)_{{R27 R28 R29 R17 R22 R21 R9 R10 R15 R16 R1 R2 R7 R8 R0}},
[0 0]_{{R25 R30 R29 R17 R22 R21 R0}Ú{R27 R28 R29 R19 R20 R21 R0}},
(¥ 0)_{{R25 R30 R29 R19 R20 R21 R11 R12 R13 R14 R3 R4 R5 R6 R0}}} IA^{}
Let's ask for each disjunct in (IA {f fi} IC):
i.1) {R_{25} R_{30} R_{29} R_{17} R_{22} R_{21} R_{0}} È {R_{25} R_{30} R_{29} R_{19} R_{20} R_{21} R_{11} R_{12} R_{13} R_{14} R_{3} R_{4} R_{5} R_{6} R_{0}} =
{R_{6} R_{5} R_{4} R_{3} R_{20} R_{19} R_{25} R_{30} R_{29} R_{17} R_{22} R_{21} R_{11} R_{12} R_{13} R_{14} R_{0} }, or
i.2) {R_{27} R_{28} R_{29} R_{19} R_{20} R_{21} R_{0}} È {R_{25} R_{30} R_{29} R_{19} R_{20} R_{21} R_{11 }R_{12} R_{13} R_{14} R_{3} R_{4} R_{5} R_{6} R_{0}} =
{R_{14} R_{13} R_{12} R_{11} R_{30} R_{25} R_{27} R_{28} R_{29} R_{19} R_{20} R_{21} R_{3} R_{4} R_{5} R_{0} R_{6}}.
However, both label sets (i.1, i.2) are ILSets: For instance, {R_{19} R_{22}} and {R_{27} R_{30}} are ILSets (Table 2) and they are subsets of i.1 and i.2, respectively. Thus, (IA {f} IC) does not hold.
ii) The constraint (IA {fi} IC) implies (IC^{+} {[0 0]} IA^{+}) Ù (IC^{} { (0 ¥)} IA^{}). Similarly:
ii.1) {R_{25} R_{30} R_{29} R_{17} R_{22} R_{21} R_{0}} È {R_{27} R_{28} R_{29} R_{17} R_{22} R_{21} R_{9} R_{10} R_{15} R_{16} R_{1 }R_{2 }R_{7 }R_{8 }R_{0}} =
{R_{16 }R_{15 }R_{10 }R_{9 }R_{28 }R_{27 }R_{25 }R_{30 }R_{29 }R_{17 }R_{22 }R_{21 }R_{1 }R_{2 }R_{7 }R_{0 }R_{8}}.
This label set is an ILSet. For instance, {R_{30 }R_{27}} is an ILSet. Also,
ii.2) {R_{27 }R_{28 }R_{29 }R_{19 }R_{20 }R_{21 }R_{0}} È {R_{27 }R_{28 }R_{29 }R_{17 }R_{22 }R_{21 }R_{9 }R_{10 }R_{15 }R_{16 }R_{1 }R_{2 }R_{7 }R_{8 }R_{0}} =
{R_{8 }R_{7 }R_{2 }R_{1 }R_{22 }R_{17 }R_{27 }R_{28 }R_{29 }R_{19 }R_{20 }R_{21 }R_{9 }R_{10 }R_{15 }R_{16 }R_{0}}.
Both these label sets (ii.1, ii.2) are also ILSets. For instance, {R_{30 }R_{27}} and {R_{19} R_{22}} are ILSets. Thus, (IA {fi} IC) does not hold either.
In conclusion, the symbolic constraint (IA {f fi} IC) cannot hold on the globally labeledconsistent pointbased TCN. This conclusion could be also obtained from a minimal IATCN (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_{25} R_{30} R_{29} R_{17} R_{22} R_{21} R_{0}} or {R_{27} R_{28} R_{29} R_{19} R_{20} R_{21} R_{0}} 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.
5.2 Metric Constraints on Intervals
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 intervalbased 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).
IA Symbolic Elemental Constraints 
IA Metric Elemental Constraints c_{ij}º {[dm_{1} dM_{1}], [dm_{2} dM_{2}], ..... [dm_{n} dM_{n}]} c'_{ij}º {[dm’_{1} dM’_{1}], [dm’_{2} dM’_{2}], ..... [dm’_{n} dM’_{n}]} 


I_{i} before I_{j} 
I_{i} (before c_{ij}) I_{j} 

I_{i} meets I_{j} 
I_{i} (meets c_{ij}) I_{j} 

I_{i} during I_{j} 
I_{i} (c_{ij} during c'_{ij}) I_{j} 

I_{i} starts I_{j} 
I_{i} (starts c_{ij}) I_{j} 

I_{i} finishes I_{j} 
I_{i} (finishes c_{ij}) I_{j} 

I_{i} overlaps I_{j} 
I_{i} (overlaps c_{ij}) I_{j} 

I_{i} equal I_{j} 
I_{i} (c_{ij} equal c'_{ij}) I_{j} 
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 timepoints, more flexible metric constraints on intervals can be represented by means of metric constraints on their ending timepoints. 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 timepoint T_{0}, and unary metric constraints on interval durations can be expressed by means of metric constraints between the two ending points of each interval:
dur (I_{i}) = {[dm_{1} dM_{1}], [dm_{2} dM_{2}], ..... [dm_{n} dM_{n}]} Þ
(I_{i}^{} {[dm_{1} dM_{1}], [dm_{2} dM_{2}], ..... [dm_{n} dM_{n}]} I_{i}^{+}).
Figure 12: Metric constraints between intervals 

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_{0})
can be represented as (Table 1):
By default: (I_{1}^{} { (0 ¥)_{{R0}}} I1^{+}), (I2^{} { (0 ¥)_{{R0}}} I2^{+}), and
(I1 {b, o} I2) Þ (I1^{+} {(0 ¥)_{{Rb1}} (¥ 0]_{{Rb2}}} I2^{}), (I1^{+} {(¥ 0)_{{Ro1}} [0 ¥)_{{Ro4}}} I2^{}),
(I1^{+} {(0 ¥)_{{Ro2}} (¥ 0]_{{Ro5}}} I2^{+}), (I1^{} {(0 ¥)_{{Ro3}} (¥ 0]_{{Ro6}}} I2^{}),
(I1^{} is [[20 30], [50 60]} at the left of I2^{}) Þ (I1^{} {[50 60]_{{R1}} [20 30]_{{R2}}} I2^{}),
(I2^{} is {[140 150], [200 210]} after T_{0}) Þ (T_{0} {[140 150]_{{R3}} [200 210]_{{R4}}} I2^{}),
and {R_{b2} R_{o4}}, {R_{b2} R_{o5}}, {R_{b2} R_{o6}}, {R_{1} R_{2}} and {R_{3} R_{4}} are ILSets.
6. Reasoning on Logical Expressions of Constraints
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 supportset of input elemental constraints from which the elemental constraint is derived. ILSets represent inconsistent sets of input elemental constraints. By reasoning on labeled disjunctive constraints, associated label lists and ILSets, 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})
For instance, let’s see the Example 2 of Section 4.4 (Figure 10):
In a similar way, logical relations among pointbased and intervalbased elemental constraints can also be represented. For instance, the logical dependence "the duration of I_{1} is [5 8] if I_{2} is before I_{3} and the duration of I_{1} is [12 15] if I_{2} is after I_{3}" can be represented as:
(I_{2} {b, bi} I_{3}) Þ (I_{2}^{+} {(0 ¥)_{{Rb9}} (¥ 0]_{{Rb10}}} I_{3}^{}), (I_{3}^{+} {(0 ¥)_{{Rb11}} (¥ 0]_{{Rb12}}} I_{2}^{}),
{R_{b10} R_{b12}} is an ILSet,
(I_{1}^{} {[5 8]_{{R1}} [12 15]_{{R2}}} I_{1}^{+}),
and {R_{1} R_{b11}}, {R_{2} R_{b9}} are ILSets, since R_{b11} is associated to ‘I_{2} is after I_{3}’ and R_{b9} is associated to ‘I_{2} is before I_{3}’. Likewise, "I_{1} starts at the same time as I_{2} if t_{1} occurs after t_{2}" can be represented as (see Table 1):
I_{1} {s, Øs} I_{2} Þ (I_{1}^{} {[0 0]_{{Rs1}} (0 ¥)_{{Rs3} }(¥ 0)_{{Rs4}}} I_{2}^{}) , (I_{1}^{+} {(0 ¥)_{{Rs2}} (¥ 0]_{{Rs5}}} I_{2}^{+}) ,
(t_{1} {(¥ 1]_{{R1}}, [0 0]_{{R2}}, [1 ¥)_{{R3}}} t_{2}),
and {R_{3} R_{s3}}, {R_{3} R_{s4}}, and {R_{3} R_{s5}} are ILSets, since R_{3} is associated to 't_{1} occurs after t_{2}' and R_{s3}, R_{s4} and R_{s5} are associated to 'I_{1} does not start at the same time as I_{2}'.
6.1 Disjunctions of Point and IntervalBased Constraints
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 ILSets. 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:
{(n_{i} lc_{ij} n_{j}) Ú (n_{k} lc_{kl} n_{l})} º
{(n_{i }{(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}}} n_{l})}
can be represented as:
i) A conjunctive set of constraints between (n_{i}, n_{j}) and between (n_{k}, n_{l}), where, Ø(lec_{x}) can be represented by means of the complementary domain of (lec_{x}):
(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})}
ii) A set of ILSets to represent the mutually exclusive disjunction of lc_{ij} and lc_{kl} (they cannot simultaneously hold):
ii.a) One of the constraints lc_{ij} or lc_{kl} should hold: The Cartesian product of label sets from complementary domains of lc_{ij} and lc_{kl}, {R'_{ij.1},_{ }R'_{ij.2},_{ }....,_{ }R'_{ij.p}}C{R'_{kl.1}, R'_{kl.2}, ...., R'_{kl.q}}, are ILSets.
ii.b) Only one of the constraints lc_{ij} or lc_{kl} should hold: The Cartesian product of label sets from lc_{ij} and lc_{kl}, {R_{ij.1},_{ }R_{ij.2},_{ }....,_{ }R_{ij.p}}C{R_{kl.1}, R_{kl.2}, ...., R_{kl.q}} are ILSets.
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 ILSets. For example:
(t_{i} {[5 5]_{{R1}} [10 10]_{{R2}}} t_{j}) Ú (t_{k} {[0 0]_{{R3}} [20 20]_{{R4}}} t_{l}) º
(t_{i} {[5 5]_{{R1}} [10 10]_{{R2} }(¥ 5)_{{R5}} (5 10)_{{R6}} (10 ¥)_{{R7}}} t_{j}) Ù
(t_{k} {[0 0]_{{R3}} [20 20]_{{R4}} (¥ 0)_{{R8}} (0 20)_{{R9}} (20 ¥)_{{R10}}} t_{l}),
and
(ii.a) since (t_{i} {[5 5]_{{R1}}, [10 10]_{{R2}}} t_{j}] or [t_{k} {[0 0]_{{R3}}, [20 20]_{{R4}}} t_{l}] should hold:
{R_{5} R_{6} R_{7}}C{R_{8} R_{9} R_{10}} are ILSets,
(ii.b) since only one constraint (t_{i} {[5 5]_{{R1}} [10 10]_{{R2}}} t_{j}) or (t_{k} {[0 0]_{{R3}} [20 20]_{{R4}}} t_{l}) should hold:
{R_{1} R_{2}}C{R_{3} R_{4}} = {R_{1} R_{3}}, {R_{1} R_{4}}, {R_{2} R_{3}}, {R_{2} R_{4}} are ILSets.
I_{i} ec_{ij} I_{j} 
I_{i} ec_{ij} I_{j} 
I_{i} Øec_{ij} I_{j} 
I_{i} (ec_{ij} Ú Øec_{ij}) I_{j} 
I_{1} before I_{2} 
I_{1}^{+} {(0 ¥)_{{Rb1}}} I_{2}^{} 
I_{1}^{+} {(¥ 0]_{{Rb2}}} I_{2}^{} 
I_{1}^{+} {(0 ¥)_{{Rb1}} (¥ 0]_{{Rb2}}} I_{2}^{} 
I_{3} before I_{4} 
I_{3}^{+} {(0 ¥)_{{Rb3}}} I_{4}^{} 
I_{3}^{+} {(¥ 0]_{{Rb4}}} I_{4}^{} 
I_{3}^{+} {(0 ¥)_{{Rb3}} (¥ 0]_{{Rb4}}} I_{4}^{} 
Table 5: Pointbased constraints for (I_{1} before I_{2}) and (I_{3} before I_{4})
Similarly, disjunctions of intervalbased constraints between different pairs of intervals can also be represented. For instance, from Table 1 and Table 5, {(I_{1} before I_{2}) Ú (I_{3} before I_{4})} can be represented as:
(I_{1}^{+} {(0 ¥)_{{Rb1}} (¥ 0]_{{Rb2}}} I_{2}^{}), (I_{3}^{+} {(0 ¥)_{{Rb3}} (¥ 0]_{{Rb4}}} I_{4}^{}),
and
a) one of the constraints (I_{1} before I_{2}) or (I_{3} before I_{4}) should hold. Thus, the Cartesian product of label sets associated to the disjunctive constraints in (I_{i} Øec_{ij} I_{j}) is a set of ILSets: {R_{b2}, R_{b4}} is an ILSet,
b) only one of the constraints (I_{1} before I_{2}) or (I_{3} before I_{4}) should hold. Thus, the label set associated to the mutual fulfillment of constraints in (I_{i} ec_{ij} I_{j}) is an ILSet: {R_{b1}, R_{b3}} is an ILSet.
Thus:
{(I_{1} before I_{2}) Ú (I_{3} before I_{4})} º
(I_{1}^{+} {(0 ¥)_{{Rb1}} (¥ 0]_{{Rb2}}} I_{2}^{}), (I_{3}^{+} {(0 ¥)_{{Rb3}} (¥ 0]_{{Rb4}}} I_{4}^{}),
and {R_{b2}, R_{b4}}, {R_{b1}, R_{b3}} are ILSets.
I_{i} ec_{ij} I_{j} 
I_{i} ec_{ij} I_{j} 
I_{i} Øec_{ij} I_{j} 
I_{i} (ec_{ij} Ú Øec_{ij}) I_{j} 
(I_{1} during I_{2}) 
I_{1}^{} {(¥ 0)_{{Rd1}}} I_{2}^{} I_{1}^{+} {(0 ¥)_{{Rd2}}} I_{2}^{+} 
(I_{1}^{} {[0 ¥)_{{Rd3}}} I_{2}^{}) Ú (I_{1}^{+} {(¥ 0]_{{Rd4}}} I_{2}^{+}) 
I_{1}^{} {(¥ 0)_{{Rd1}} [0 ¥)_{{Rd3}}} I_{2}^{} I_{1}^{+} {(0 ¥)_{{Rd2}} (¥ 0]_{{Rd4}}} I_{2}^{+} 
(I_{3} starts I_{4}) 
I_{3}^{} {[0 0]_{{Rs1}}} I_{4}^{} I_{3}^{+} {(0 ¥)_{{Rs2}}} I_{4}^{+} 
(I_{3}^{} {(0 ¥)_{{Rs3}} (¥ 0)_{{Rs4}}} I_{4}^{}) Ú (I_{3}^{+} {(¥ 0]_{{Rs5}}} I_{4}^{+}) 
I_{3}^{} {[0 0]_{{Rs1}} (0 ¥)_{{Rs3}} (¥ 0)_{{Rs4}}} I_{4}^{} I_{3}^{+} {(0 ¥)_{{Rs2}} (¥ 0]_{{Rs5}}} I_{4}^{+} 
Table 6: Pointbased constraints for (I_{1} during I_{2}) and (I_{3} starts I_{4})
In a similar way (Table 6), (I_{1} during I_{2}) Ú (I_{3} starts I_{4}) º
(I_{1}^{} {(¥ 0)_{{Rd1}} [0 ¥)_{{Rd3}}} I_{2}^{}), (I_{1}^{+} {(0 ¥)_{{Rd2}} (¥ 0]_{{Rd4}}} I_{2}^{+}),
(I_{3}^{} {[0 0]_{{Rs1}} (0 ¥)_{{Rs3}} (¥ 0)_{{Rs4}}} I_{4}^{}), (I_{3}^{+} {(0 ¥)_{{Rs2}} (¥ 0]_{{Rs5}}} I_{4}^{+}),
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 ILSets.
Therefore, logical relations on elemental constraints can be represented by a set of ILSets. Thus, a labeled TCN (and the set of ILSets) can represent a special type of and/or TCN. These types of nonbinary 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 nonbinary 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 nonbinary 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 labeledconsistent 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_{1} {[40 40]} T_{3}) ® (T_{2} { [0 0] } T_{4}), (T_{3} { [20 20] } T_{2}) ® (T_{3} { [20 20] } T_{4}).
However, (T_{3} {[10 20]} T_{2}) does not imply (T_{1} {[70 70]} T_{4}). Similarly, questions such as ‘Can c'_{ij} hold, if c'_{kl}?’ can also be easily answered by applying Theorem 9 and Theorem 10.
7. Alternative Temporal Contexts
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 contextdependent 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_{0} represents the root context and there are different disjunctive constraints between (n_{1}, n_{2}) in each context. Temporal reasoning algorithms detailed in this paper are able to manage these contextdependent constraints:
(n_{1} {[0 50]_{{R1}}, [200 210]_{{R2}}} n_{2})
is asserted in context W_{1}, we have the following input contextdependent labeled constraint:
(n_{1} {[0 25]_{{R1, W1}}, [260 280]_{{R2, W1}}} n_{2}).
Here, each contextdependent label set associated to each elemental constraint represents both the alternative temporal disjunct (i.e.: R_{1} or R_{2}) and the context in which the elemental constraint is asserted (W_{1}).
Definition 8. A contextdependent 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_{0} is the root context. à
The proposed reasoning processes can manage contextdependent 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_{1} n_{2} should be updated:
(n_{1} {[0 100]_{{R1 W0}}, [200 300]_{{R2 W0}}} n_{2}), 
(n_{1} {[0 50]_{{R3 W1}}, [200 210]_{{R4 W1}}} n_{2}), 
(n_{1} {[60 100]_{{R5 W2}}, [290 300]_{{R6 W2}}} n_{2}), 
(n_{1} {[0 25]_{{R7 W3}}, [260 280]_{{R8 W3}}} n_{2}), 
(n_{1} { [0 25]_{{R0 W11}}} n_{2}), 
(n_{1} { [30 50]_{{R9 W12}}, [200 205]_{{R10 W12}}} n_{2}), 
(n_{1} {[0 20]_{{R0 W31}}, [210 215]_{{R0 W32}}} n_{2}), 
(n_{1} {[260 280]_{{R0 W33}}} n_{2}). 
Figure 13: A hierarchy of alternative contexts
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_{1} {[0 50]_{{R3 W1}}, [200 210]_{{R4 W1}}} n_{2}) in context W_{1} and (n_{1} {[0 25]_{{R7 W3}}, [260 280]_{{R8 W3}}} n_{2}) in context W_{3} are not mutually disjoint. However, W_{1}, W_{2} and W_{3} are assumed as three mutually exclusive alternatives of W_{0}.
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.
7.1 ContextDependent Updating and Closure Processes
The update and closure processes defined in Section 4 should be adapted in order to manage contextdependent disjunctive constraints. The ContextUpdate process (Figure 14) asserts the constraint c’_{ij}º{ec’_{1}, ec’_{2}, ..., ec’_{n}} in the context context_{k}. In a way similar to the updated process described in Section 4, ContextUpdate should be performed each time a new contextdependent constraint is asserted.
ContextUpdate (n_{i} c’_{ij} n_{j} context_{k})
lc'_{ij} ¬ Putlabelcontext (c’_{ij}, context_{k}) ;Labelling and mutual inconsistency.
If ConsistencyTest (getupward (n_{i}, n_{j}, context_{k}), lc'_{ij}) ;Upwards Consistency test
Then (*Inconsistent Constraint*)
Return (false)
Else (*Consistent Constraint*) ;lc'_{ij} is asserted in the context_{k} and in all its
lc_{ij} ¬ (lc_{ij}  get (n_{i}, n_{j}, context_{k})) È_{lc} (lc_{ij} Å_{lc} lc'_{ij}), ;successor contexts.
lc_{ji} ¬ Inverse_{lc} (lc_{ij}),
ContextClosure (n_{i} lc_{ij} n_{j} context_{k}) ;Downwards Closure algorithm in context_{k}.
. Return (true)
EndIf
EndContextUpdate
Figure 14: ContextUpdate process for contextdependent labeled constraints
Where:
"context_{p} / context_{p}ÎSuccesorContexts(ParentContext(Context_{k})),
ILSets ¬ ILSets È ({context_{k}}È{context_{p}}).
Where ParentContext(context_{k}) and SuccessorContexts(context_{k}) return the parentcontext and the set of successorcontexts of context_{k}, respectively. Thus, in Figure 13, {{W_{1}, W_{2}}, {W_{1}, W_{3}}, {W_{2}, W_{3}}, {W_{11}, W_{12}}, {W_{31}, W_{32}}, {W_{31}, W_{33}}, {W_{32}, W_{33}}} are ILSets.
get (n_{i}, n_{j}, context_{k})::= {(ec_{ij.p}{label_{ij.p}})Îlc_{ij} / context_{k}Î{label_{ij.p}}}.
Note that get(n_{i}, n_{j}, context_{k}) is a subset of lc_{ij}. Thus, (lc_{ij}  get (n_{i}, n_{j}, context_{k})) means the setdifference between lc_{ij} and get (n_{i}, n_{j}, context_{k}). That is, the set of elemental constraints in the contextdependent constraint lc_{ij}, which are not in context_{k}, nor in any of its successor contexts.
getupward (n_{i}, n_{j}, context_{k}) ::=
If get (n_{i}, n_{j}, context_{k}) ¹ Æ Then return (get (n_{i}, n_{j}, context_{k}))
Else
Context_{k} ¬ ParentContext (Context_{k})
Until get (n_{i}, n_{j}, context_{k}) ¹ Æ Ú Context_{k}=W_{0} do
If get (n_{i}, n_{j}, context_{k}) ¹ Æ Then return (get (n_{i}, n_{j}, context_{k}))
Else return({(¥ +¥)}_{{W0 R0}}})
Endgetupward
The contextdependent 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.
ContextClosure (n_{i} lc_{ij} n_{j} context_{k})
(* First loop: Closure n_{i} ® n_{j} ® n_{k }*)
"n_{k}ÎTCN / lc_{jk} ¹_{ }{U_{{R0 W0}}}:
lc'_{ik} ¬ lc_{ik} Å_{lc} (lc_{ij} Ä_{lc} lc_{jk}),
lc_{ik} ¬ (lc_{ik}  get (n_{i}, n_{k}, context_{k})) È_{lc} lc’_{ij},
lc_{ki} ¬ Inverse(lc_{ik})
(* Second loop: Closure n_{j} ® n_{i} ® n_{l} *)
"n_{l}ÎTCN / lc_{il} ¹_{ }{U_{{R0 W0}}}:
lc'_{jl} ¬ lc_{jl} Å_{lc} (Inverse(lc_{ij}) Ä_{lc} lc_{il}),
lc_{jl} ¬ (lc_{jl}  get (n_{j}, n_{l}, context_{k})) È_{lc} lc'_{jl},
lc_{lj}¬ Inverse(lc_{jl})
(* Third loop: Closure n_{l} ® n_{i} ® n_{j} ® n_{k} *)
"n_{l}, n_{k} ÎTCN / lc_{lj} ¹_{ }{U_{{R0 W0}}}, lc_{jk} ¹_{ }{U_{{R0 W0}}}:
lc'_{lk} ¬ lc_{lk} Å_{lc} (lc_{li} Ä_{lc} lc_{ij} Ä_{lc} lc_{jk})
lc_{lk} ¬ (lc_{lk}  get (n_{l}, n_{k}, context_{k})) È_{lc} lc'_{lk},
lc_{kl} ¬ Inverse(lc_{lk})
EndContextClosure
Figure 15: ContextClosure process for contextdependent labeled constraints
The resulting label set associated to each contextdependent 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_{1} and n_{2}:
(n_{1} lc_{12} n_{2}): (n_{1} {[0 100]_{{R1 W0}}, [200 300]_{{R2 W0}}, [0 50]_{{R3 R1 W1 W0}}, [200 210]_{{R4 R2 W1 W0}}, (e3)
[60 100]_{{R5 R1 W2 W0}}, [290 300]_{{R6 R2 W2 W0}}, [0 25]_{{R7 R1 W3 W0}}, [260 280]_{{R8 R2 W3 W0}},
[0 25]_{{R0 R3 R1 W11 W1 W0}}, [30 50]_{{R9 R3 R1 W12 W1 W0}}, [200 205]_{{R10 R2 R4 W12 W1 W0}},
[0 20]_{{R0 R7 R1 W31 W3 W0}}, [210 215]_{{R0 R2 R8 W32 W3 W0}}, [260 280]_{{R0 R2 R8 W33 W3 W0}}} n_{2})
Figure 16: Labels in contexts
No closure process is performed among constraints belonging to contexts of different hierarchies. According to Putlabelcontext function, each pair of labels related to the successor contexts of each context is an ILSet. Thus, these ILSets 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_{1}, W_{2}}, {W_{1}, W_{3}}, {W_{2}, W_{3}}, {W_{11}, W_{12}}, {W_{31}, W_{32}}, {W_{31}, W_{33}}, {W_{32}, W_{33}}} are ILSets. Thus, if a constraint is asserted in context W_{1}:
Let's see an example of the ContextUpdate and ContextClosure processes. Let’s assume that the contextdependent constraints in Figure 13 are already updated and closured, such that the previous constraint lc_{12} (expression e3) exists between n_{1} and n_{2}. Now, we update (n_{1} {[20 40]} n_{2}) in context W_{1}. The call to ConsistencyTest function in the ContextUpdate function is:
ConsistencyTest (getupward (n_{1}, n_{2}, W_{1}), {[20 40]_{{R0 W1}}}).
Given the previous constraint lc_{12} between n_{1} and n_{2} (expression e3), the function performs:
{[0 50]_{{R3 R1 W1 W0}}, [200 210]_{{R4 R2 W1 W0}}, [0 25]_{{R0 R3 R1 W11 W1 W0}},
[30 50]_{{R9 R3 R1 W12 W1 W0}}, [200 205]_{{R10 R2 R4 W12 W1 W0}}} Å_{lc} {[20 40]_{{R0 W1}}}=
{[20 40]_{{R3 R1 R0 W1 W0}}, [20 25]_{{R0 R3 R1 W11 W1 W0}}, [30 40]_{{R9 R3 R1 R0 W12 W1 W0}}} ¹ Æ
Thus, the new constraint (n_{1} {[20 40]} n_{2}) is consistent in context W_{1}. Therefore, the constraint between n_{1} n_{2} results:
lc_{12} ¬ (lc_{12}  get (n_{1}, n_{2}, W_{1})) È_{lc} (lc_{12} Å_{lc} {[20 40]_{{R0 W1}}}) =
{[0 100]_{{R1 W0}}, [200 300]_{{R2 W0}}, [60 100]_{{R5 R1 W2 W0}}, [290 300]_{{R6 R2 W2 W0}},
[0 25]_{{R7 R1 W3 W0}}, [260 280]_{{R8 R2 W3 W0}}, [0 20]_{{R0 R7 R1 W31 W3 W0}},
[210 215]_{{R0 R2 R8 W32 W3 W0}}, [260 280]_{{R0 R2 R8 W33 W3 W0}}} È_{lc}
{[20 40]_{{R1 R0 W1 W0}}, [20 40]_{{R3 R1 R0 W1 W0}}, [20 25]_{{R0 R3 R1 W11 W1 W0}}, [30 40]_{{R9 R3 R1 R0 W12 W1 W0}}}=
{[0 100]_{{R1 W0}}, [200 300]_{{R2 W0}}, [60 100]_{{R5 R1 W2 W0}}, [290 300]_{{R6 R2 W2 W0}}, [0 25]_{{R7 R1 W3 W0}}, (e4)
[260 280]_{{R8 R2 W3 W0}}, [0 20]_{{R0 R7 R1 W31 W3 W0}}, [210 215]_{{R0 R2 R8 W32 W3 W0}}, [260 280]_{{R0 R2 R8 W33 W3 W0}},
[20 40]_{{R1 R0 W1 W0}}, [20 25]_{{R0 R3 R1 W11 W1 W0}}, [30 40]_{{R9 R3 R1 R0 W12 W1 W0}}}.
Note that the new updated constraint is asserted in context W_{1} and propagated to all its successor contexts (W_{11} and W_{12}). However, the new constraint in context W_{1} does not affect the existing constraints in predecessor contexts of W_{1} (W_{0}) nor the constraints belonging to contexts of different hierarchies (W_{2}, W_{3} and their successors).
In this update process, no closure process is performed, since no node is related with n_{1} or n_{2}. Now, let’s update (n_{3} {[10 20]} n_{1}) in context W_{1}. We have:
ConsistencyTest (getupward (n_{3}, n_{1}, W_{1}), {[10 20]_{{R0 W1}}}),
that performs:
{(¥ +¥)}_{{W0 R0}} Å_{lc} {[20 40]_{{R0 W1}}} = {[20 40]_{{R0 W0 W1}}} ¹ Æ,
since no previous constraint exists between (n_{3} n_{1}) in context W_{1}. The constraint (n_{3} {[10 20]} n_{1}) is consistent, and asserted in the TCN:
lc_{31} ¬ {(¥ +¥)}_{{W0 R0}, }[20 40]_{{R0 W0 W1}}}. (e5)
Afterwards, this constraint is closured. The call to ContextClosure process is:
ContextClosure (n_{3}, {(¥ +¥)}_{{W0 R0}, }[20 40]_{{R0 W0 W1}}}, n_{1}, W_{1}).
In this closure process, only the first loop is performed since no node is related to n_{3}. Moreover, only the previous constraint lc_{12} (expression e4) exists in the current TCN between n_{1} and n_{2}. Thus, the first loop performs:
lc'_{32} ¬ lc_{32} Å_{lc} ({(¥ +¥)}_{{W0 R0}, }[20 40]_{{R0 W0 W1}}} Ä_{lc} lc_{12}) =
{(¥ ¥)_{{W0 R0}}} Å_{lc} ({(¥ +¥)}_{{W0 R0}, }[20 40]_{{R0 W0 W1}}} Ä_{lc} lc_{12}) =
{(¥ +¥)}_{{W0 R0}, }[220 340]_{{R2 R0 W0 W1}}, [40 80]_{{R1 R0 W1 W0}},
[40 65]_{{R0 R3 R1 W11 W1 W0}}, [50 80]_{{R9 R3 R1 R0 W12 W1 W0}}},
such that,
lc_{32} ¬ (lc_{32}  get (n_{3}, n_{2}, W_{1})) È_{lc} lc'_{32} = ({(¥ ¥)_{{W0 R0}}}  {}) È_{lc} lc'_{32} =
{(¥ ¥)_{{W0 R0}}, [220 340]_{{R2 R0 W0 W1}}, [40 80]_{{R1 R0 W1 W0}},
[40 65]_{{R0 R3 R1 W11 W1 W0}}, [50 80]_{{R9 R3 R1 R0 W12 W1 W0}}}. (e6)
Thus, the asserted constraint between (n_{3}, n_{2}) in context W_{1} is closured in the context W_{1} and in all its successor contexts (W_{11} and W_{12}). Likewise, the closure process does not perform any propagation simultaneously using constraints of the contexts W_{11} and W_{22}, nor any of the context W_{2}, W_{3}, nor any of their successors.
7.2 Complete Versus Incomplete Partition of Contexts
In each updating process, the consistency of each new constraint lc’_{ij} in a given context is assured in this context and in all its parent contexts. Let’s deal with consistency issues between a context and its successor contexts. Here, we have that constraints in a given context W_{i} can be either completely covered or only partially covered by the existing constraints in the successor contexts of W_{i}. That is, the successor contexts of W_{i} can be either a complete partition or only a partial partition of W_{i}.
For instance, let's assert the constraint (n_{1} {[210 210]_{{R0 W1}}} n_{2}) in the context W_{1} of the example in Figure 13. In the Consistencytest function, we have (where the constraint lc_{12} is the previous expression e2):
getupward (n_{1}, n_{2}, W_{1}) Å_{lc} {[210 210]_{{R0 W1}}} =
{[0 50]_{{R3 R1 W1 W0}}, [200 210]_{{R4 R2 W1 W0}}, [0 25]_{{R0 R3 R1 W11 W1 W0}}, [30 50]_{{R9 R3 R1 W12 W1 W0}},
[200 205]_{{R10 R2 R4 W12 W1 W0}}} Å_{lc} {[210 210]_{{R0 W1}}} = {[210 210]_{{R0 W1 R4 R2 W0}}}.
That is, the asserted constraint is consistent with the existing constraints in context W_{1}. However, no resulting elemental constraint is associated to context W_{11} nor W_{12}. This means that the asserted constraint (n_{1} {[210 210]_{{R0 W1}}} n_{2}) is consistent in W_{1}, but is inconsistent in W_{11} and in W_{12}. Here, two alternatives appear:
In both cases, each context will always be consistent with all its successor contexts. The option to be adopted can depend on the problem type to solve (Garrido et al., 1999). Any of the these options can be easily introduced in the described reasoning processes, since the function Consistency Test can determine which successor contexts (W_{s}) become inconsistent at each new constraint (lc’_{ij }) in a context (W_{k}):
W_{s}ÎSuccessorContexts(W_{k}) / $elc_{ij.p}Îgetupward (n_{i}, n_{j}, W_{k}), W_{s}Î{label_{ij.p}} Ù
Ø$elc_{ij.r}Î(getupward (n_{i}, n_{j}, W_{k}) Å_{lc} lc’_{ij}), W_{s}Î{label_{ij.r}}.
On the other hand, when: (i) the successor contexts (W_{k1}, W_{k2}, ..., W_{kp}) of a context W_{k} are a complete partition of it, and (ii) all constraints in (W_{k1}, W_{k2}, ..., W_{kp}) have been asserted, then constraints in W_{k} can be restricted according to the final existing constraints in (W_{k1}, W_{k2}, ..., W_{kp}). To do this, the context W_{k} should be constrained by the temporal union of the constraints in all its successor contexts.
7.3 A Minimal and Consistent ContextDependent TCN
Definition 9. A contextdependent TCN is minimal (and consistent) if the constraints in each context are consistent (with respect to constraints in this context, in all its predecessor contexts, and all its successor contexts) and minimal (with respect to constraints in this context and in all its predecessor contexts). à
Theorem 12. At each updating process, the contextdependent reasoning processes obtain a minimal (and consistent) contextdependent TCN if the previous contextdependent TCN is minimal.
Proof: If the previous contextdependent TCN is minimal, the ConsistencyTest function guarantees the consistency of each new contextdependent input constraint:
i) in its context and in all its parent contexts (getupward function and Theorem 5),
ii) in all its successor contexts (depending of the two identified cases in Section 7.2).
The closure process of a new constraint in a given context (W_{k}) propagates its effects to this context and to all its successor contexts. Therefore (Theorem 7), the process obtains the new minimal constraints in this context (W_{k}) and in all its successor contexts. à
Moreover, the obtained contextdependent TCN is globally labeledconsistent. Thus, we can deduce whether a set of elemental constraints (between different pairs of time points) is consistent (Theorem 10). That is, this set of elemental constraints holds in some context. For instance, given the previous constraints lc_{12}, lc_{31} and lc_{32} (previous expressions e4, e5 and e6), we can deduce that:
(n_{1} {[40 40]} n_{2}) Ù (n_{3} {[40 40]} n_{1}) Ù (n_{3} {[40 40]} n_{2})
is full consistent since:
$elc_{12.x}Îlc_{12}, $elc_{31.y}Îlc_{31}, $elc_{32.z}Îlc_{32} / ({label_{12.x}} È {label_{12.x}} È {label_{12.x}}) is not an ILSet.
Specifically, these instantiations hold in {R_{1} R_{0} W_{1} W_{0}} and {R_{1} R_{0} W_{0}}. Thus, this set of elemental constraints holds in context W1 (and, obviously, in all its predecessor contexts).
Likewise, from a minimal contextdependent TCN, the user can retrieve the constraints that hold in each context or the constraints that simultaneously hold in a set of given contexts. To do this, the ContextConstraints function retrieves the constraints that hold between a pair of nodes (n_{i}, n_{j}) in a given context (context_{k}). That is, the result of Getupwards(n_{i}, n_{j}, context_{k}) except those elemental constraints belonging to successor contexts of context_{k}:
ContextConstraints (n_{i}, n_{j}, context_{k})::= Getupwards (n_{i}, n_{j}, context_{k}) –
{lec_{ij.p}Îlc_{ij} / $context_{q}ÎSuccesorContexts(context_{k}), {context_{q}}Ç{label_{ij.p}}¹Æ}.
For instance, given the contextdependent constraint lc_{12} in Figure 13 (expression e3), the following constraint would hold between (n_{1}, n_{2}) in both contexts W_{1} and W_{3}:
ContextConstraints(n_{1}, n_{2}, W_{1}) Å_{lc} ContextConstraint(n_{1}, n_{2}, W_{3}) =
{[0 50]_{{R3 R1 W1 W0}}, [200 210]_{{R4 R2 W1 W0}}} Å_{lc} {[0 25]_{{R7 R1 W3 W0}}, [260 280]_{{R8 R2 W3 W0}}}=
{[0 25]_{{R7 R3 R1 W3 W1 W0}}}.
In addition, we can obtain the constraints, which simultaneously hold in a context and in any of its successor ones. For instance, in context W_{1} and in any of its successor contexts (W_{11}, W_{12}), the following constraint holds:
ContextConstrains(n_{1}, n_{2}, W_{1}) Å_{lc} [ContextConstraints(n_{1}, n_{2}, W_{11}) È_{lc} ContextConstraints(n_{1}, n_{2}, W_{12})]=
{[0 50]_{{R3 R1 W1 W0}}, [200 210]_{{R4 R2 W1 W0}}} Å_{lc}
{[0 25]_{{R0 R3 R1 W11 W1 W0}}}È_{lc }{[30 50]_{{R9 R3 R1 W12 W1 W0}}, [200 205]_{{R10 R2 R4 W12 W1 W0}}}=
{[200 205]_{{W12 R10 R4 R2 W1 W0}}, [0 25]_{{W11 R0 R3 R1 W1 W0}}, [30 50]_{{W12 R9 R3 R1 W1 W0}}}.
On the other hand, each alternative context (W_{i}) can be associated to an alternative hypothesis (H_{i}). Each hypothesis H_{i} gives rise to a set of constraints, which will be asserted in the associated context W_{i}. Thus, the proposed reasoning processes assure minimal constraints in the hierarchy of hypotheses. Moreover, if a hypothesis (H_{i}) becomes unavailable, then the label set {W_{i}} should be added to the set of ILSets. Thus, all constraints in context W_{i} (and in all its successor contexts) will be removed. That is, all constraints that depend on the unavailable hypothesis H_{i} will be removed.
7.4 Computational Complexity of Temporal Context Management
The management of temporal context does not increase the complexity of the reasoning processes detailed in Section 4. In fact, we can consider that each label associated to a disjunct (R_{i}) in labeled disjunctive constraints is also associated to a context (W_{i}). Thus, the computational cost of each updating process is also bounded by O(n^{2} l^{2e}), where 'l' is the maximum number of input disjuncts between any pair of nodes in all contexts.
The temporal labeled algebra proposed in this paper (Section 3) has been applied on the pointbased disjunctive metric constraints (Dechter, Meiri & Pearl, 1991). However, this labeled algebra can also be applied on other temporal constraints. In this case, the operations Å_{ lc}, Ä_{ lc}, È_{lc} and Í_{ lc} should be specified (Section 3) on the basis of the operations Å, Ä, È_{T} and Í_{T} of the underlying algebra. In this way, the management of temporal contexts can also be applied to other types of constraints.
Theorem 13. The computational complexity of the proposed reasoning process applied to contextdependent nondisjunctive metric constraints is polynomial (O(n^{2} W^{2})) in the number W of managed contexts.
Proof: Disjunctions in constraints are only related to the contexts in which input constraints are asserted, if nondisjunctive constraints are managed. That is, constraints between each pair of nodes are in the form:
(n_{i} {(ec_{ij.0}{W_{0} R_{0}}), (ec_{ij.1}{W_{1} R_{0}}), ...... , (ec_{ij.k}{W_{k} R_{0}})} n_{j}) , 0£k£W / W={W_{i}}
Thus, the maximum number of disjuncts in constraints is bounded by the maximum number of managed contexts W. Moreover, the maximum length of associated label sets is the maximum depth in the hierarchy of contexts, and the set of ILSets has only 2length sets (i.e.: pairs of labels associated to each pair of successor contexts of each context). Therefore, the computational cost of operations Ä_{lc} and Å_{ lc} is bounded by O(W^{2}). à
The methods proposed in Section 7.1 for management of temporal contexts can also be applied to other temporal reasoning algorithms, instead of the reasoning methods detailed in Section 4. This requires that these other reasoning algorithms be based on the operations of composition and intersection of temporal constraints. Thus,
For instance, when intervalbased constraints are managed, the TCA algorithm can be used to obtain a pathconsistent contextdependent IATCN, with a O(n^{3} W^{2}) cost. Similarly, when a contextdependent reasoning is applied to PIDN networks (Pujari & Sattar, 1999), the computational cost of specific reasoning algorithms on PIDN constraints is increased by a factor W^{2}. When the proposed temporal algebra in Section 3 is applied to tractable classes of constraints, the specific reasoning algorithms for management of these classes of constraints can also be applied. The computational cost of these reasoning algorithms (which should be based on combination and intersection operations on constraints) is increased by a polynomial factor W^{2}. For instance, when nondisjunctive metric constraints are managed, the TCA algorithm can be used as the closure algorithm in Section 7.1. This algorithm will obtain a minimal contextdependent TCN with a computational cost O(n^{3} W^{2}).
Several problems remain pending in representation and reasoning problems on temporal constraints. In relation to this, we have dealt with reasoning on complex qualitative and quantitative constraints between timepoints and intervals, which can be organized in a hierarchy of alternative temporal contexts. We have described a newlabeled temporal algebra, whose main elements are labeled disjunctive metric constraints, label sets associated to elemental constraints, and sets of inconsistent elemental constraints (ILSets). The temporal model presented is able to integrate qualitative and metric constraints on timepoints and intervals. In fact, symbolic and metric constraint between intervals can be represented by means of disjunctive metric constraints between time points and a set of ILSets. The model is also able to manage (nonbinary) logical relations among elemental constraints. The reasoning algorithms on the described model are based on the distributive property for composition over intersection in labeled constraints, and guarantee consistency and obtain a minimal TCN of disjunctive metric pointbased constraints. In addition, a special type of global labeledconsistent TCN is also obtained.
Labeled constraints can be organized in a hierarchy of alternative temporal contexts, such that temporal reasoning processes can be performed on these contexts. Reasoning algorithms guarantee consistency in each hierarchy of contexts, maintain a minimal contextdependent TCN, and allow us to determine what constraints hold in each context or in a set of alternative contexts. Thus, we can reason on a hierarchy of contextdependent constraints on intervals, points and unary durations (Figure 17).
These described features are useful functionalities for modeling important problems in the temporal reasoning area. However, they have not been identified in previous models. Therefore, the temporal model presented here represents a flexible framework for reasoning on complex, contextdependent, metric and qualitative constraints on timepoints, intervals and unary durations.
Figure 17: Contextdependent constraints on intervals, time points and unary durations
A pathconsistent algorithm can be used as the closure process on labeled TCNs, like the typical TCA algorithm as applied by Allen (1983). This pathconsistent algorithm would obtain a minimal contextdependent TCN of disjunctive metric constraints. We have proposed an incremental reasoning process. Thus, a minimal (and consistent) contextdependent TCN is assured at each new assertion. This incremental reasoning allows us to detect whether each new input constraint is inconsistent with the previously existing ones. This can be useful when problem constraints are not initially known but are successively deduced from an incremental independent process (Garrido et al., 1999).
A prototype of proposed reasoning algorithms has been implemented in CommonLisp and is available from the author. These reasoning algorithms are being applied to an integrated architecture of planning and scheduling processes (Garrido et al., 1999). Here, the scheduling process should guarantee the consistency of each alternative partial plan (i.e.: temporal constraints and availability of resources for operations) simultaneously as the planner is generating each partial plan (Srivastava & Kambhampati, 1999). Thus, the following main features are needed:
A globally labeledconsistent (and minimal) TCN allows us to determine consistent alternative choices and to obtain optimal solutions in each plan. Additionally, the proposed model can be a useful framework to apply on problems where these features also appear (Dousson et al., 1993; Garcia & Laborie, 1996; Srivastava & Kambhampati, 1999; etc.).
The computational cost of reasoning algorithms is exponential, due to the inherent complexity of the management of disjunctive constraints. However, the management of temporal contexts does not increase the complexity of the reasoning processes on disjunctive constraints.
Some improvements to decrease the empirical cost of reasoning algorithms have been proposed in this paper. The application of algorithms to handle only an explicit TCN (without making the derived constraints explicit) and empirical evaluations on several test cases are under study. Moreover, other reasoning algorithms can be applied to the temporal algebra presented, as proposed in Section 4. On the other hand, it is interesting to identify subclasses of the labeled temporal algebra where the size of label sets can be bounded, and to identify tractable subclasses of IA on the proposed model. It could also be interesting to identify the expressive power of ILSets (and labeled constraints) on the basis of method described by Jeavons, Cohen and Cooper (1999). Here, each ILSet represents a special derived constraint, which expresses the inconsistency of a set of input elemental constraints; that is, a special type of disjunctive linear constraint (Jonsson & Bäckström, 1996; Stergiou & Koubarakis, 1996).
The proposedlabeled algebra (labeled constraints and the operations on them) can be applied to other temporal models (i.e.: to other classes of temporal constraints, operations, and reasoning algorithms). To do this, the operations of the labeled algebra (Å_{lc}, Ä_{lc}, È_{lc} and Í_{lc}) should be defined on the basis of the respective operations (Å, Ä, È_{T} and Í_{T}) of these models, and the reasoning algorithms should use the operations defined on labeled constraints (Å_{lc}, Ä_{lc}, È_{lc} and Í_{lc}). This requires that these reasoning algorithms be based on the composition and intersection operations. Specifically, the application of the proposed model to tractable temporal constraints as those identified in Section 1 (Jonsson et al., 1999; Drakengren & Jonsson, 1997; Vilain, Kautz and Van Beek, 1986; etc.) allows for a tractable reasoning process on a hierarchy of temporal constraint contexts.
Acknowledgements
This work was partially supported by the Generalitat Valenciana (Research Project #GV1112/93) and by the Spanish Government (Research Project #CYCITTAP980345). The author would sincerely like to thank the JAIR reviewers for their helpful comments and suggestions on previous versions of this paper.
References
Allen, J. (1983). Maintaining knowledge about temporal intervals. Comm of the ACM, 26, 11, 832843.
Badaloni, S., & Berati, M. (1996). Hybrid Temporal Reasoning for Planning and Scheduling. In Proceedings of the 3º Int. Workshop on Temporal Representation and Reasoning (TIME’96).
Barber, F. (1993). A metric timepoint and durationbased temporal model. ACM Sigart Bulletin, 4 (3), 3040.
Barber, F., Botti, V., Onaindia, E., & Crespo, A. (1994). Temporal reasoning in Reakt: An environment for realtime knowledgebased systems. AICommunications, 7 (3), 175202.
Brusoni, V., Console, L., & Terenziani, P. (1997). Later: Managing temporal information efficiently, IEEE Expert, 12 (4), 5664.
Cohen, D., Jeavons, P., & Koubarakis, M. (1996). Tractable disjunctive constraints. In Proceedings. of the 3rd Int. Conf. on Principles and Practice of Constraint Programming (CP’96). Freuder, E.C. (Ed.). Lecture Notes in Computer Science, 1118, 297307.
Cooper, M.C. (1990). An optimal kconsistency algorithm. Artificial Intelligence, 41, 8995.
Dean, T.L., & McDermott, D.V. (1987). Temporal data base management. Artificial Intelligence, 38, 155.
Dechter. R., Meiri, I., & Pearl, J. (1991). Temporal constraint networks. Artificial Intelligence, 49, 6195.
Dechter, R. (1992). From local to global consistency. Artificial Intelligence, 55, 87107.
Dousson, C., Gaborit, P., & Ghallab M. (1993). Situation Recognition: Representation and Algorithms. In Proceedings of 13th International Joint Conference on Artificial Intelligence (IJCAI’93).
Drakengren, T., & Jonsson, P. (1997). Eight maximal tractable subclasses of Allen's algebra with metric time. Journal of A.I. Research, 7, 2545.
Freuder, E. C. (1978). Synthesizing constraint expressions. Comm. of the ACM, 21 (11), 958965.
Freuder, E. C. (1982). A sufficient condition for backtrackfree search. Journal of the ACM, 29 (1), 2432.
Garcia, F., & Laborie, P. (1996). Hierarchisation of the Seach Space in Temporal Planning. New Directions in AI Planning, 217232, IOS Press.
Garrido, A., Marzal, E., Sebastiá, L., & Barber F. (1999). A model for planning and scheduling integration. In Proceedings of the 8 th. Conference of Spanish Association of A.I. (CAEPIA’99).
Gerevini, A., & Schubert, L. (1995). Efficient algorithms for qualitative reasoning about time. Artificial Intelligence, 74, 207248.
Jeavons, P., Cohen, D., & Cooper M. (1998). Constraints, consistency and closure. Artificial Intelligence, 101, 251268.
Jeavons, P., Cohen, D., Gyssens, M. (1999). How to determine the expressive power of constraints. Constraints: An Int. Journal, 4, 113131.
Jonsson, P., & Bäckström, C. (1996). A linearprogramming approach to temporal reasoning. In Proceedings of the 13 th. National Conference on Artificial Intelligence (AAAI’96).AAAI Press.
Jonsson, P., & Bäckström, C. (1998). A unifying approach to temporal constraint reasoning. Artificial Intelligence, 102, 143155.
Jonsson, P., Drakengren, T., & Bäckström, C. (1999). Computational complexity of relating time points and intervals. Artificial Intelligence, 109, 273295.
Kautz, H., & Ladkin, P. (1991). Integrating metric and qualitative temporal reasoning. In Proceedings of the 9th. National Conference on Artificial Intelligence (AAAI’91).AAAI Press.
Mackworth, A. K. (1977). Consistency in networks of relations, Artificial Intelligence, 8, 121118,.
Meiri, I. (1996). Combining qualitative and quantitative constraints in temporal reasoning. Artificial Intelligence, 87, 343385.
Montanari, U. (1974). Networks of constraints: fundamental properties and applications to picture processing. Information Science, 7, 95132.
Navarrete, I., & Marin, R. (1997). Qualitative temporal reasoning with points and durations. In Proceedings of the 15^{ }th. International Joint Conference on Artificial Intelligence (IJCAI97).
Nebel, B., & Burckert, H.J. (1995). Reasoning about temporal relations: a maximal tractable subclass of Allen's interval algebra. Journal of the ACM, 42 (1), 4366.
Pujari, A., & Sattar, A. (1999). A new framework for reasoning about Points,. Intervals and Durations. In Proceedings on the Int. Joint Conference on Artificial Intelligence (IJCAI'99).
Schwalb, E., & Dechter, R. (1997). Processing disjunctions in temporal constraints networks. Artificial Intelligence, 93, 2961.
Staab, S., & Hahn, U. (1998). Distance constraint arrays: A model for reasoning on intervals with qualitative and quantitative distances. In Proceedings of the 12th Biennial Conference of the Canadian Society for Computational Studies of Intelligence on Advances in Artificial Intelligence (AI98), Lecture Notes in Artificial Intelligence, 1418, 334348.
Srivastava, B., & Kambhampati, S. (1999). Efficient planning through separate resource scheduling. In Proceedings of the AAAI Spring Symp. on search strategy under uncertainty and incomplete information. AAAI Press.
Stergiou, K., & Koubarakis, M. (1996). Tractable disjunctions of Linear Constraints. In Proceedings of the 2nd Int. Conf. on Principles and Practice of Constraints Programming (CP’96). Freuder, E.C. (Ed.). Lecture Notes in Computer Science, 1118, 297307.
Stergiou, K., & Koubarakis, M. (1998). Bactracking algorithms for disjunctions of temporal constraints. In Proceedings of the 15 th. National Conference on Artificial Intelligence (AAAI98). AAAI Press.
Van Beek, P. (1991).Temporal query processing with indefinite information. Artificial Intelligence in Medicine, 3 (6), 325339.
Van Beek, P., & Detcher R. (1995). On the minimality and global consistency of row convex networks. Journal of the ACM, 42 (3), 543561.
Van Beek, P., & Dechter, R. (1997). Constraint tightness and looseness versus local and global consistency. Journal of the ACM, 44 (4), 549566.
Vilain, M., Kautz, H., & Van Beek P. (1986). Constraint propagation algorithm for temporal reasoning. In Proceedings of the 5Th. National Conference on Artificial Intelligence (AAAI86).AAAI Press.
Wetprasit, R., Sattar A. (1998). Temporal representation with qualitative and quantitative information about points and durations. In Proceedings of the 15^{ }th. National Conference on Artificial Intelligence (AAAI’98). AAAI Press.
Yampratoom, E., & Allen, J. (1993). Performance of temporal reasoning systems, ACM Sigart Bulletin, 4, (3), 2629.