qi = qj. By Algorithm 2, this implies E t vxja ↓ wxja. On the other hand, the path in G x starting from ( nc, nd ) with label vx,a leads to the node n, and the one for wx,a leads to n j . Since n j ̸ = n j , Proposition 2 implies E Ω t vx j a ↓ wx j α , which is a contradiction. To sum up, we have shown that there does not exist an lcs for C and D in S .

This shows that there is no lcs of C, D in S which completes the proof of the only-if direction.

We now prove the if direction of Theorem 6. For this purpose, we assume that G ∞ has only a finite number of same-as nodes. Note that every same-as node in G 2 has only a finite number of direct predecessors. To see this, two cases are distinguished: i) a node of the form ( g 1 , g 2 ) in G has only predecessors in G ; ii) if t is a tree node and g a non-tree node, then a predecessor of ( g, t ) in G ∞ is of the form ( g ′ , t ′ ) where t ′ is the unique predecessor
(tree or non-tree node) of t and g ′ is a non-tree node.  Since the number of nodes in G C
and G D is finite, in both cases we only have a finite number of predecessors. But then, the spanning tree T of G ∞ coincides with G ∞ except for a finite number of edges because, if T does not contain a certain edge, then this edge leads to a same-as node. As a result, C G × is an S -concept description because it is a finite conjunction of same-as equalities. Finally, Corollary 5 shows that C G × is the lcs of C and D .

→
If v ↓ w is a conjunct in C G 2 , then v and w lead from the root of G ∞ to a same-as node.

As mentioned before, same-as nodes are of the form ( f, g ), ( f, t ), or ( t, f ), where t is a tree node and f t g are non-tree nodes. Consequently, v and w must be paths in G C or G D . Thus, they only contain attributes occurring in C or D . Corollary 6 If the lcs of two concept description C and D in S exists, then there is a concept description in S only containing attributes occurring in C or D that is equivalent to the les.

Therefore, when asking for the existence of an lcs, we can w.o.l.g. assume that the set of attributes A is finite. This fact will be used in the following two subsections.

## 5.3 Deciding The Existence Of An Lcs

From the following corollary we will derive the desired decision algorithm for the existence of an lcs of two concept descriptions in S . To state the corollary we need to introduce the language L G C ( q 1 ; q 2 ) := { w ∈ A * | there is a path from the node q 1 to q 2 in G C labeled w } . Since description graphs can be viewed as finite automata, such a language will be regular.

Moreover, let aA* denote the set {aw | w E A*} for an attribute a E A, where A is a finite alphabet.

Corollary 7 G ∞ contains an infinite number of same-as nodes iff either
(i) there exist nodes (h1,p0), (h2,p0) in G as well as nodes f, e1, e2 in GC, and attributes a, b E A such that 1. h 1 ≠ h 2 , e1 ≠ e2; 2. po does not have a b-successor in GD;