4. Let n E N 1 and n ′ E N 2 . If l 1 (n) = L, then let l ((n,n')) := l 2 (n') and, analogously, if l 2 (n') = L, then l ((n,n')) := l 1 (n). Otherwise, for l 1 (n) = (S 1 , H 1 ) and l 2 (n') = (S2, H2), define l((n, n')) := (S, H) where
(a) S := S1 N S2;
(b) H :=
{r, min(p1, p2), max(g1, q2), G'1 x G'2) |  (r, p1, q1, G'1) E H1, (r, p2,q2, G'2) E H2} U
{(a, 0, 1, G 1 | m  × G ′ 2 ) | (n, a, m) ∈ E 1 , (a, p 2 , q 2 , G ′ 2 ) ∈ H 2 } U
{(a, 0, 1, G'1 × G21m) | (a, p1, q1, G'1) E H1, (n', a, m) E E2}.

According to this definition, if in the tuple ( n, n ′ ) some node, say n, is incoherent, then the label of ( n, n ′ ) coincides with the one for n ′ . The reason for defining the label in this way is that lcs ( ⊥, C ) ≡ C for every concept description C . This has been overlooked by Frazier and Pitt (1996), thus making their constructions and proofs only hold for concept descriptions that do not contain inconsistent subexpressions.

Note that G , as defined here, might not be connected, i.e., it might contain nodes that cannot be reached from the root n 0 . Even if G 1 and G 2 are connected this can happen because all tuples ( n 1 , n 2 ) belong to the set of nodes of G regardless of whether they are reachable from the root or not. However, as already mentioned in Section 3.1 we may assume G to be connected.

Also note that the product graph can be translated back into a CLASSICT concept description since the product of two description graphs is once again a description graph.

## 4.2 Computing The Lcs

We now prove the main theorem of this subsection, which states that the product of two description graphs is equivalent to the lcs of the corresponding concept descriptions.

Theorem 4  Let C 1 and C 2 be two concept descriptions, and let G 1 and G 2  be corresponding canonical description graphs. Then, CG 1 ×G 2 ≡ lcs(C 1 , C 2 ).

Proof. Let G := G 1 × G 2 . We will only sketch the proof showing that C G subsumes C 1 and, by symmetry, also C 2 (see (Küsters & Borgida, 1999) for details). By construction, if there are two rooted paths to a common node in G i then G 1 has corresponding paths leading to the same node as well. Thus, by Theorem 3, the same-as equalities in C G subsume the ones in C 1 . Now, let T be a spanning tree of G , ( m 1 , m 2 ) be a node in G , and v be the label of the rooted path in T to ( m 1 , m 2 ). Then, by construction it follows that there exists a rooted path in G 1 to m 1 labeled v . Furthermore, a rather straightforward inductive proof shows that the concept description E corresponding to the label of ( m 1 , m 2 ) subsumes G 1 , m 1 ,
This implies ∀ v.E ¯ G 1 . As a result, we can conclude G ¯ G 1 .

The more interesting part of the proof is to show that C G is not only a common subsumer of C 1 and C 2 , but the least common subsumer.

We now show by induction over the size of D , C 1 , and C 2 that if D subsumes C 1 and C 2 , then D subsumes C G : We distinguish different cases according to the definition of
"subsumes?". Let G 1 = ( N 1 , E 1 , n 1 , l 1 ) be the canonical description graph of C 1 , G 2 = (N 2 , E 2 , n 2 , l 2 ) be the canonical description graph of C 2 , and G = (N , E , n 0 , l ) = G 1 × G 2 .

In the following, we assume that C 1 E D and C 2 E D i thus, subsumes?( D i G 1 ) and