ssssssss of the vertices
-
such that
, and there exists a one-to-one function - H
iven a graph
, with n associate a temporal concept expression i ba j ba . B Q n n n Q n , where is an atomic concept and . i . i . This transformation allows us to prove that the problem of subgraph isomorphism can be reduced to the subsumption of temporal concepts.

Proposition 6.23  Given two graphs      and    ,      contains a subgraph isomorphic to iff
__
Proof. A temporal network with edges labeled only with the  before   after   relation is always consistent, minimal and non-directed     erevini     chubert,          Then, each temporal concept is in the essential graph form. Now the proof easily follows since, every time an isomorphic subgraph of    the one-to-one function   is also an s-mapping from to
, and it is true that -          n the other hand, the s-mapping that gives rise to the s subsumption is also the one-to-one isomorphism from to Theorem 6.24 (NP-hardness) Concept subsumption between TL-F concept expressions in normal form is an NP-hard problem.

Proof. ollows from proposition . and the reduction being clearly polynomial.

Now the N -completeness is proven.

Theorem 6.25 (NP-completeness) Concept subsumption between TL-F concept expressions in normal form is an NP-complete problem.

Proof. To prove N -completeness it is necessary to show that the proposed calculus can be solved by a nondeterministic algorithm that takes polynomial time. Now, given two temporal concepts, and a, in their essential graph form, let —
and Then, to check whether _
to and verifies whether it is an s-mapping, too. This last step can be done in from deterministic polynomial time since, given a mapping M, it is possible to determine whether
- by checking at most
-      edges looking for subsumption I M
between the corresponding temporal relations  solved by a set inclusion procedure   while non-temporal concept subsumptions can be computed in polynomial time.

the

## 7. Extending The Propositional Part Of The Language

The propositional part of the temporal language can be extended to have a more powerful, but still decidable, escription ogic. It is possible either to add full dis unction, both at the temporal and non-temporal levels  TLU-FU , or to have a propositionally complete language at the non-temporal level only  TL-ALCF .

lease note that in these languages it is not possible to express full negation, and in particular the negation of the existential temporal  uantifier.  This is crucial, and it 4 I v b,a v v b,a v