cc Z , there exists an interpretation I such that

$$\L_{\begin{array}{c c c c}{{\stackrel{s s i o n s}{\phantom{s i o n s}}}}&{{\underline{{{s u c h}}}}}&{{\stackrel{t h a t}{\phantom{s i o n s}}}}&{{\stackrel{\overline{{{\phi}}}}{\phantom{s i o n s}},}}&{{\mathit{t h e r e}\phantom{s i s t s}}}\\ {{\stackrel{t}{\phantom{s i o n s}}}}&{{\mathit{/}}}&{{\stackrel{s u c h}{\phantom{s i o n s}}}}&{{\stackrel{t h a t}{\phantom{s i o n s}},}}&{{\mathit{t o r}\phantom{s o n s e}\phantom{s i t e r v a l}}}\end{array}}.$$

D
Proof. The proposition states that the information in ea node of the   E   is independent from the information in the other nodes. In fact, n D
, if the concept expression in one node implies new information in some other node. Two cases can be distinguished.

i Coveral Nodes. oth the (= collapsing) rule and the (covering) rule provide to restrict a covered node with the most specific F concept expression. Indeed, the (= collapsing) rule provides collapsing two contemporary nodes con oining the concept expressions of each of n the other hand, the (covering) rule adds to the covered node the most specific them.

F concept expression that subsumes the dis unctive concept expression that is implicitly true at the covered node. Note that, thanks to the (Closure) rule, all the possible e ual temporal relations are made explicit. o these two normalization rules cover all the possible cases of temporal interactions between nodes.

ii No coincident nodes. Every time-invariant information should spread over all the nodes.

oth parametric features and the concept have a time-invariant semantics the only timeinvariant concept expressions are m, with
≥ , or an arbitrary con unction of these terms. The (parameter introduction) rule captures all the possible syntactical cases of completion concerning time-invariant concept expressions. y induction on the syntax, it can be proven that adding to a node any other concept expression changes the overall interpretation.

The last normalization procedure eliminates nodes with redundant information. This final normalization step ends up with the concept in the essential graph form, that will be the normal form used for checking concept subsumption.

Definition 6.8 (Essential graph) The subgraph of the CEF of a conceptual temporal constraint network obtained by deleting the nodes labeled only with time¬
O
invariant concept expressions   with the exception of the   node   is called essential graph of  : (ess  ).

Proposition 6.9 (Equivalence of essential graph)  Every concept in completed existential form can be reduced in linear time into an equivalent essential graph form.

Theorem 6.10 (Equivalence of normal form) Every concept expression can be reduced into an equivalent essential graph form.  If a polynomial fragment of Allen's algebra is adopted, the reduction takes polynomial time.

As an example, the normal form is shown   i.e., the essential graph of the previously introduced Stack action see ection .

Stack

  \begin{tabular}{c c c c c c}  & f$\!$i & mi & mi & f & o & mi & mi & f \\  & o d s & s s & m & b & m & b & mi \\ DBJECT1 & Clear-Block & $\sqcap$ & DBJECT1 & $\sqcap$ & & \\ DBJECT1 & OR & BJECT2 & @ & $\sqcap$ & & \\ DBJECT1 & Clear-Block & $\sqcap$ & DBJECT2 & @ & $\sqcap$ & \\ DBJECT1 & Hold-Block & $\sqcap$ & & & \\ OBJECT1 & Clear-Block & $\sqcap$ & & & \\ \end{tabular}  