consistency guarantees consistency and obtains a minimal non-disjunctive metric TCN (Dechter et al., 1991). The path-consistency TCA Algorithm has an O(n 3) cost (Allen, 1983; Vilain, Kautz & Van Beek, 1986). However, assuring path-consistency 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 |cij ⊗ cjk| is upper bounded by |cij|x|cjk|. Thus, the total number of disjuncts (subintervals) in a path-consistent TCN might be exponential in the number of disjuncts per constraints in the initial (input) TCN. Schwalb and Dechter (1997) call this the *fragmentation* problem, which does not appear in non-disjunctive metric TCNs. Thus, the TCA algorithm is O(n 3 R
3) in disjunctive metric-TCNs if time is not dense (Dechter et al., 1991), where the range 'R' is the maximum difference between the lowest and highest number specified in any input constraints.

## 3. A Labeled Temporal Algebra

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

- Time-point (ti) as primitive variable. A continuous variable domain (like Q or ℜ) is usually assumed.

- Each temporal constraint cij⊆U is a finite set of l mutually exclusive subdomains (or subintervals) of D.
cij≡{[d
-
1 d+1], [d
-
2 d+2], ...., [d
-
k d+k], ....., [d
-
l d+l]} , where d
-
k≤d
+
k and dk,d+k∈D,
and disjunctively restricts the temporal distance between two time-points, ti and tj:
tj - ti ∈ {[d
-
1 d+1], [d
-
2 d+2], ....., [d
-
l d+l]},
meaning that (d
-
1≤tj-ti≤ d+1) ∨ .... ∨ (d
-
l≤ tj-ti≤ d+l). Similar conditions can be applied to open
(d
-
k d+k) and semi-open intervals (d
-
k d+k], [d
-
k d+k). The Universal-Constraint U is {(-∞ +∞)}.

Unary constraints restrict the associated subdomain of a time-point ti∈{[d
-
1 d+1], [d
-
2 d+2], .....,
[d
-
l d+l]}. A special time-point T0 is usually included, which represents 'the beginning of the world' (usually, T0=0). Thus, each unary constraint on ti can be represented as a binary one between ti and T0:
ti - T0 ∈ {[d
-
1 d+1], [d
-
2 d+2], ..... ,[d
-
l d+l]} ≡ ti∈[d
-
1, d+1] ∨ ti∈[d
-
2, d+2] ∨, ..., ∨ ti∈[d
-
l, d+l]
and, by default: ∀ti, (T0 {[0 ∞)} ti).

- The algebra operations, mainly ⊗, ⊕, ∪Τ and ⊆Τ. From (Meiri, 1996), given two temporal constraints S={[dS
-
i, dS
+
i]} and T={[dT
-
j, dT
+
j]},
S ⊗ T = {dk / ∃di∈S ∧ ∃dj∈T / dk= di+dj}.

That is, ∀[dS
-
i, dS
+
i]∈S, ∀[dT
-
j, dT
+
j]∈T, ∪T{[dS
-
i+dT
-
j, dS
+
i+dT
+
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 = {dk / dk∈S ∧ dk∈T}. That is, the set-intersection of their subdomains.

S ∪Τ T = {dk / dk∈S ∨ dk∈T}, as the set-union of their subdomains. S⊆ΤT = iff ∀dk∈S, ∃dk∈T.