For example, the graph depicted in Figure 6 contains an infinite number of same-as nodes. We will show that this is a sufficient and necessary condition for the lcs of C 0 and D 0 not to exist.

It is helpful to observe that same-as nodes in G x have one of the forms (g, f), (f, t),
and ( t, f ), where g and f are non-tree nodes and t is a tree node. There cannot exist a same-as node of the form (t 1 ,t 2 ), where both t 1 and t 2 are tree nodes, since tree nodes only have exactly one direct predecessor, and thus ( t 1 , t 2 ) does. Moreover, if G ∞ has an infinite number of same-as nodes, it must have an infinite number of same-as nodes of the form ( f, t ) or ( t, f ), because there only exist a finite number of nodes in G ∞ of the form
(g, f). For this reason, in the following lemma we only characterize same-as nodes of the form ( f, t ). (Nodes of the form ( t, f ) can be dealt with analogously.) To state the lemma, recall that with nou n1 vn2 E H, for some graph H, we describe a path in H labeled uv from n 0 to n 2 that passes through node n 1 after u (i.e., n 0 un 1 E H and n 1 vn 2 E H ); this is generalized the obvious way to interpret nou1 n1 u2 n2 u3n3 E H.

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

Lemma 7  Given a node f in Gc and a tree-node t in Gff, the node n = (f,t) in Gx, is a same-as node iff
- there exist nodes (h1,po), (h2,po) in G, h1 + h2;

- there exist nodes (e1, qo), (e2, qo) in G%, where e1, e2 are distinct nodes in GC and Q is a node in G ; and
- there exists an attribute a E A and v, w, x E A*, v + w, where A is the set of attributes in C,
such that
(nc,nd)v (h1,p0) x (e1,q0) a(f,t) and (nc,nd)w (h2,p0) x (e2,q0) a(f,t)
are paths in G ∞ (see Figure 7).  For the direct successors (h 1 , p 0 ) and (h 2 , p 0 ) of (h 1 , p 0 )
and (h2,po) in this paths, we, in addition, require ph to be a tree node in GQ. 4