

![0_image_0.png](0_image_0.png)

Algorithm 2  Let C, D be concept descriptions in S, and G C = (N, E, no) be the canonical description graph of C. Then, subsumes t ?(D, GC) is defined to be true if and only if one of the following conditions hold:

1. D is v ↓ w and there are words v ′ , w ′ , u ∈ A ∗ such that v = v ′ u and w = w ′ u , and there are rooted paths in GC labeled v' and w', respectively, ending at the same node.

2. D is D 1 Π D 2 and both subsumes t ?( D 1 , G C ) and subsumes t ?( D 2 , G C ) are true.
Apart from the additional constructors handled by Algorithm 1, Algorithm 2 only differs from Algorithm 1 in that, for total attributes, as considered here, it is sufficient if prefixes of rooted paths v and w lead to a common node, as long as the remainder in both cases is the same path. Theorem 5 There are concept descriptions in S such that the lcs of these concept descriptions does not exist in S.

This result corrects the statement of Cohen et al. (1992) that the lcs always exists, a statement that inadvertently assumed that attributes were partial, not total.

As proof, we offer the following S -concept descriptions, which are shown not to have an lcs:

$$\begin{array}{r l}{C_{0}}&{{}:=\quad a\downarrow b,}\\ {D_{0}}&{{}:=\quad a\downarrow a c\sqcap b\downarrow b c\sqcap a d\downarrow b d.}\end{array}$$

The graphs for these concepts are depicted in Figure 4.

The following statement shows that an lcs E of C 0 and D 0 would satisfy a condition which does not have a "regular structure".  This statement can easily be verified using Algorithm 2.

E E t v ↓ w   iff   v = w or there exists a nonnegative integer n and u E
A* such that v = ac n du and w = bc n du or vice versa.

Given this description of the lcs of C 0 and D 0 , one can show, again, by employing Algorithm 2, that no finite description graph can be equivalent to E. However, we omit this elementary proof here, because the absence of the lcs also follows from Theorem 6, where infinite graphs are used to characterize the existence of an lcs. Note that in the partial attribute case, the lcs of Co and Do is equivalent to a ↓ a Π b ↓ b, a result that can be