coincide. As an example, take the products Gc n × GD n and G ∞ × G ∞ (see Figure 4 for the graphs Gch and GDn). The former product results in a graph that consists of a root with two outgoing a-edges, one labeled a and the other one labeled b. (As mentioned before, this graph corresponds to the lcs of Co and Do in the partial attribute case.) The product of the completed graphs, on the other hand, is a graph that is obtained as the completion of the graph depicted in Figure 6 (the infinite trees are omitted for the sake of simplicity).

As an easy consequence of the fact that Gc ≡ G ≈ and Corollary 4, one can prove the following lemma. Lemma 6 C Et v ↓ w iffncvn E G → and ncwn E G → for a node n in G → .

But then, by the construction of G ∞ we know:
Proposition 2 C ⊂ t v ↓ w and D ⊂ t v ↓ w iff (nc,nd)vn ∈ G ∞ and (nc,nd)wn ∈ G ∞
for a node n in Go In particular, G ∞ represents the lcs of the concept descriptions C and D in the following snsn Corollary 5  The (infinite) concept description C Ax  corresponding to G%  is the lcs of C
and D, i.e., i) C, D ⊆ t C G x and ii) C, D ⊆ t E ′ implies C G x ∈ t E ′ for every S-concept description E'.

## 5.2  Characterizing The Existence Of An Lcs

Let C, D be concept descriptions in S and let the graphs Gc, Gd, G, GP, GP, GP, and GX
be defined as above.

We will show that G ∞ not only represents a (possibly infinite) lcs of the S -concept descriptions C and D (Corollary 5), but that G ∞ can be used to characterize the existence of a finite lcs. The existence depends on whether G ∞ contains a finite or an infinite number of so-called same-as nodes.

Definition 9 A node n of an (infinite) description graph H is called a same-as node if there exist two direct predecessors of n in H. (The a-edges leading to n from these nodes may be labeled differently.)

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

