On the basis of the point-based disjunctive metric temporal algebra and its operations, we introduce a *labeled* point-based 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 cij can be considered as a disjunctive set of l mutually exclusive elemental constraints {ecij.k}.

ecij.k = [d
-
ij.k d+ij.k] / ∀i,j,k d
-
ij.k≤d
+
ij.k cij ≡{ecij.1, ec ij.2, ..., ec ij.l} ⊆ U / ∀k,p∈(1,..,l), k≠p, (ecij.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 lcij is a disjunctive set of labeled elemental constraints {lecij.k}. That is, lcij ≡ {lecij.1, lecij.2, ..., lecij.l}, where lecij.k ≡ (ecij.k{labelij.k}), and {labelij.k}≡{label1, label2, ..., labels} is a set of symbols.◊
Each *label* in a labeled-TCN can be considered as a unique symbol. The following cases can occur:

i) If an *input* (or explicitly asserted) constraint lcij has only one elemental constraint, that is, only one disjunct, this elemental constraint has the label 'R0'. The labeled *UniversalConstraint* is {U{R0}}. In a given TCN, the set of all elemental constraints labeled with 'R0' is the *'common context'*. Thus, the label R0 represents the set of elemental constraints which have no other alternatives (disjuncts). All elemental constraints labeled only with R0 should hold since they have no other alternative disjuncts.

ii) If an *input* constraint lcij has more than one elemental constraint, each elemental constraint lecij.k∈lcij has a single and exclusive label associated to it (|{labelij.k}|=1). Thus, each label in the TCN represents bi-univocally an elemental constraint in an explicitly asserted constraint.

iii) Each derived elemental constraint (obtained by combining (⊗lc) or intersecting (⊕lc) two labeled elemental constraints) has a set of labels associated to it. This set of labels is obtained from the label sets associated to the combined (or intersected) labeled elemental constraints.

It will be detailed in the later specification of operations (⊗lc, ⊕lc) in Section 3.2. In consequence, the label set associated to a derived elemental constraint represents the conjunctive support-set of explicitly asserted elemental constraints that imply this derived elemental constraint.
Let's see a simple example on labeled constraints, which was introduced by Dechter, Meiri and Pearl (1991).