subsumes?( D, G 2 ). We show that subsumes?( D, G ). Then, Remark 1 implies G ⊆ D, and thus, C G E D. Note that one cannot use Theorem 3 since G might not be a canonical description graph.

1. If G is incoherent, then there is nothing to show.

2. If D is a concept name, T, or a number-restriction, then by definition of the label of no it is easy to see that subsumes?( D, G ).

3. If D is v ↓ w, then there exist nodes m 1 in G 1 and m 2 in G 2 such that there are two paths from n 1 to m 1 with label v and w , respectively, as well as two paths from n 2 to m 2 with label v and w . Then, by definition of G it is easy to see that there are two paths from no = (n 1 , n 2 ) to (m 1 , m 2 ) with label v and w , respectively. This shows subsumes?( D, G).

4. If D is Vr.C, r a role or attribute, then one of several cases applies:
(i) n 1 and n 2 have r-edges with role or attribute r, and restriction graphs G 1 and G 1 ,
respectively, such that subsumes?( C, G ′ 1 ) and subsumes?( C, G ′ 2 );
(ii) without loss of generality, n 1 has an a-edge pointing to m 1 with attribute r, such that subsumes?(C, G 1 ), where G 1 := G 1 1 m, ; and n 2 has an r-edge with restriction graph G 2 such that subsumes?( C, G 2 ).

In both cases (i) and (ii), subsumes?( C, G 1 × G 2 ) follows by induction. Furthermore, by definition of G there is an r-edge with role r and restriction graph G ′ 1 × G ′ 2 for n 0 .

This implies subsumes?( D, G ).

(iii) n 1 and n 2 have a-edges with attribute r leading to nodes m 1 and m 2 , respectively. Then, subsumes?( C, G 1 lm, ) and subsumes?( C, G 2 lm, ). By induction, we know subsumes?( C, G 1 |m, × G 2 |m,). It is easy to see that G |(m,,m,) = G 1 |m, × G 2 |m, · Furthermore, by definition there is an a-edge with attribute r from (n 1 , n 2 ) to (m 1 , m 2 )
in G. This shows subsumes?( D, G ). (iv) (without loss of generality) n 1 has no r-edge and no a-edge with role or attribute r . This implies subsumes?( C, G ( T )), which also ensures subsumes?( D, G ).

5. If D is E Π F , then by definition of the subsumption algorithm, subsumes?( E , G 1 ) and subsumes?( E, G 2 ) hold. By induction, we have subsumes?( E, G ), and analogously, subsumes?( F, G ). Thus, subsumes?( D, G ).

□
As stated in Section 3.5, a canonical description graph for a CLASSIC- concept description can be computed in time polynomial in the size of the concept description. It is not hard to verify that the product of two description graphs can be computed in time polynomial in the size of the graphs. In addition, the concept description corresponding to a description graph can be computed in time polynomial in the size of the graph. Thus, as a consequence of Theorem 4 we obtain:
Corollary 2 The lcs of two CLASSIC- concept descriptions always exists and can be computed in time polynomial in the size of the concept descriptions.