Proof.   The if direction is obvious. We proceed with the only-if direction and assume that n is a same-as node in G ∞ . Let po be the (uniquely determined) youngest ancestor of t in G . In particular, po is a node in GD and there exists pox qo at in GH with a E A and x E A* such that the successor of po in this path is a tree node in GD.

Since n is a same-as node and t can only be reached via qo and the attribute a, there must exist e 1 , e 2 in Gc , e 1 ̸= e 2 , with (e 1 , go)a(f,t),(e 2 , go)a(f,t) ∈ G ∞ . Since G ∞ is connected, there are paths from ( nc, nd ) to ( e1, qo ) and ( e2, qo ). Every path from nD to qo must pass through po and the suffix of the label of this path is x .  Consequently, there exist nodes h 1 , h 2 in G C such that ( h 1 , p 0 ) x ( e 1 , q 0 ) a ( f, t ) and ( h 2 , p 0 ) x ( e 2 , q 0 ) a ( f, t ) are paths in G X . In particular, xa is a label of a path from h 1 to f in G C , and the label xa only consists of attributes contained in C . If h 1 = h 2 , then this, together with the fact that G C is deterministic, would imply e 1 = e 2 . Hence, h 1 ̸= h 2 . Let v, w be the labels of the paths from ( n C, n D ) to ( h 1, p 0 ) and ( h 2, p 0 ), respectively. As G is deterministic and h 1 ̸ = h 2, it follows that v = w.

□
The main results of this section is stated in the next theorem. As a direct consequence of this theorem, we obtain that there exists no lcs in S for the concept descriptions C 0 and D of our example.

Theorem 6 The lcs of C and D exists iff the number of same-as nodes in G ∞ is finite.

Proof. We start by proving the only-if direction. For this purpose, we assume that G ∞
contains an infinite number of same-as nodes and show that there is no (finite) lcs for C
and D in S .

As argued before, we may assume that G ∞ contains an infinite number of same-as nodes of the form ( f, t ) or ( t, f ), where t is a tree node and f is a non-tree node. More precisely, say G ∞ contains for every i ≥ 1 nodes n i = ( fi, ti ) such that fi is a node in G C and ti is a tree node in G ∞ . According to Lemma 7, for every same-as node nj there exist nodes h1,i, b2,i, e1,i, e2,i in GC, p0,i in GD, and q0,i in GP as well as a; E A and x; E A* with the properties required in Lemma 7.

Since G C and G D are finite description graphs, the number of tuples of the form h1, b2, e1, e2, fi, a; is finite.  Thus, there must be an infinite number of i's yielding the same tuple h 1 , h 2 , e 1 , e 2 , f , a .  In particular, h 1 ̸ = h 2 and e 1 ̸= e 2 are nodes in G C and there is an infinite number of same-as nodes of the form nj = ( fjtlj ). Finally, as in the lemma, let v, w be the label of paths (in G ) from ( n C, n D ) to ( h 1 , p 0 ) and ( h 2 , p 0 ).

Now, assume there is an lcs E of C and D in S . According to Corollary 5, E H t C C × .

Let GE be the finite canonical graph for E with root n ′ . By Proposition 2 and Lemma 7 we know E E t vx,a ↓ wx,a. From Algorithm 2 it follows that there are words v', w', and u such that vxia = v'u and wxia = w'u, where the paths in GE starting from n' labeled v',
w' lead to the same node in GE.

If u ̸ = ε, then u = u ′ a for some word u ′ . Then, Algorithm 2 ensures E ⊂ t vx i ↓ wx i .

However, by Lemma 7 we know that the words vx i and wx i lead to different nodes in G x , namely, (e 1 , go,,) and (e 2 , go,,), which, with Proposition 2, leads to the contradiction E ≡ G ∞ L t vx i ↓ wx i . Thus, u = ε .

As a result, for every i ≥ 1 there exists a node q i in GE such that n ′ vx i aq i and n ′ wx i aq i are paths in GE. Because GE is a finite description graph, there exist i,j ≥ 1, i ̸= j, with