In this example, the essential graph is also the E of Stack since there are no redundant nodes.

## 6.2 Computing Subsumption

A concept subsumes another one  ust in case every possible instance of the second is also an instance of the first, for every time interval. Thanks to the normal form, concept subsumption in the temporal language is reduced to concept subsumption between non-temporal concepts and to subsumption between temporal constraint networks. A similar general procedure was first presented in     eida itman,        , where the language for non-temporal concepts is less expressive it does not include features or parametric features.

To compute subsumption between non-temporal concepts    which may possibly include le and the concepts we refer to one to orgidal irsh, In the following, we will write jr" for subsumption between non-temporal F concepts taking into account LCS concepts.

Definition 6.11 (Variable mapping) A variable mapping M  is a total function M
such that M 
, and M
1 to intend  M
M
Definition 6.12 (Temporal constraint subsumption)  A temporal constraint is said to subsume a temporal constraint under a generic variable mapping M,
written
, if M
, M
and
=M
for every temporal interpretation Proposition 6.13 (TC subsumption algorithm)
if and

$$\exists M$$

only if M
and the disjuncts in
, M
are a superset of the disjuncts in ollows from the observation that the temporal relations are mutually dis oint Proof and their union covers the whole interval pairs space.

Definition 6.14 (Temporal constraint network subsumption) A temporal constraint s subsumes a temporal constraint network net work under a variable mapping M
, written
, if M
M
↑
=M
for every temporal interpretation  .

l

l Proposition 6.15 (TCN subsumption algorithm)
IM
if, after computing the temporal transitive closure, there exists a variable mapping M
such that for all exist which satisfy
=M
Proof implies that IM
for every then, from the definition of interpretation of a temporal constraint network, it is easy to see that each assignment of variables V in the interpretation is also an assignment in the interpretation of  M
of M
uppose that one is not able to find such a mapping  then, by hypothesis, for each 1 "
possible variable mapping there exists some such that is not a superset of