4. LGc(h1, e1) NLGc(h2, e2) NbA* is an infinite set of words;
(ii) the same statement as (i) but with rôles of C and D switched. Proof. We first prove the only-if direction. Assume that G 2 contains an infinite number of same-as nodes. Then, w.l.o.g., we find the configuration in G ∞ described in the proof of Theorem 6. This configuration satisfies the conditions 1. and 3. stated in the corollary.

If, for i ̸ = j, the words x i and x i coincide, we can conclude n i = n j because G ∞ is a deterministic graph. However, by definition, ni / nj. Hence, xi / xj. Because A is finite, we can, w.l.o.g., assume that all xi's have b E A as their first letter for some fixed b. Thus, condition 4. is satisfied as well. According to the configuration, the b -successor of ( , p 0 ) in G is of the form ( , p h ) where p h is a tree node. Thus, p 0 does not have a b -successor in Gp, which means that condition 3, is satisfied.

We now prove the if direction of the corollary. For this purpose, let bx E L G C ( h1, e1) N
LGc(h2,e2) NbA*.  Since po has no b-successor in GD it follows that there are tree nodes t, t' in G H such that pobx t at' E G H . Thus, we have (h 1 ,po)bx (e 1 ,t) a(f,t') E G H and
( h 2 , p 0 ) bx · ( e 2 , t ) · a ( f , t ′ ) ∈ G ∞ . Since e 1 ̸ = e 2 , we can conclude ( e 1 , t ) ̸= ( e 2 , t ). This means that ( f, t ′ ) is a same-as node. Analogously, for by ∈ L G C ( h 1 , e 1 ) ∩ L G C ( h 2 , e 2 ) ∩ b A * there are tree nodes s, s' in G B such that poby s as' E G B and ( f, s' ) is a same-as node in G X .

Since bx and by both start with b, and the b successor of p 0 in GB is a tree node, x ≠ y implies § ¥ t ′ . Hence, ( f, t ′ ) and ( f, $ ) are distinct same-as nodes. This shows that if the set L G C ( h 1 , e 1 ) ∩ L G C ( h 2 , e 2 ) ∩ b A * is infinite, G ∞ must have an infinite number of same-as nodes.

□
For given nodes (hi,po), (h2,po) in G, attributes a,b E A, nodes f,ei,e2 E GC the conditions 1. to 3. in Corollary 7 can obviously be ecked in time polynomial in the size of the concept descriptions C and D . As for the last condition, note that an automaton accepting the language L G c (h 1 , e 1 ) ∩ L G c (h 2 , e 2 ) ∩ b A * can be constructed in time polynomial in the size of C . Furthermore, for a given finite automaton it is decidable in time polynomial in the size of the automaton if it accepts an infinite language (see the book by Hopcroft and Ullman (1979) for details). Thus, condition 4. can be tested in time polynomial in the size of C and D as well. Finally, since the size of G and G C is polynomial in the size of C and D ,
only a polynomial number of configurations need to be tested. Together with Corollary 7 these complexities provide us with the following corollary.

Corollary 8  For given concept descriptions C and D in S it is decidable in time polynomial in the size of C and D whether lcs of C and D exists in S .

## 5.4 Computing The Lcs

In this subsection, we first show that the size of an lcs of two S-concept descriptions may grow exponentially in the size of the concept descriptions. This is a stronger result than that presented for partial attributes, where it was only shown that the lcs of a sequence of concept descriptions in S can grow exponentially. Then, we present an exponential time lcs algorithm for S-concept descriptions.