word ε . This proves that in GE s there is a path from no labeled axa for every x ∈ {c,d} k .

Hence, there is a path for every ax. Now, let y E {c,d}k be such that x f y. If the paths for ax and ay from n 0 in GE, lead to the same node, then this implies E k E t ax ↓ ay in contradiction to C ′ Q t ax ↓ ay . As a result, ax and ay lead to different nodes in GE x .  Since
{c, d} k contains 2 k words, this shows that GE, has at least 2 k nodes. Finally, taking into account that the size of a canonical description graph of a concept description in S is linear in the size of the corresponding description we obtain the following theorem.

Theorem 7 The lcs of two S-concept descriptions may grow exponentially in the size of the concepts.

The following (exponential time) algorithm computes the lcs of two S-concept descriptions in case it exists.

## Algor It Hm   3

Input: concept descriptions C, D in S, for which the lcs exists in S;
Output: lcs of C and D in S ;
1. Compute G := Gc × Gp; 2. For every combination
- of nodes (h 1 , p 0 ), (h 2 , p 0 ) in G = G C × G D , h 1 ≠ h 2 ;
- a E A, e1, e2, f in Gc, e1 ̸= e2, where (e1, a, f) and (e2, a, f) are edges in Gc extend G' as follows:  Let Gh 1 ,t, Gh 2 ,t  be two trees representing the (finite) set of words in

$$L:=\left(L_{G_{C}}(h_{1},e_{1})\cap L_{G_{C}}(h_{2},e_{2})\cap\bigcup_{b\not\in s u c c(p_{0})}b{\cal A}^{s}\right)\cup\left\{\begin{array}{l l}{{\{\varepsilon\},}}&{{\mathrm{if~a\not\in s u c c(p_{0})~}}}\\ {{\emptyset~,}}&{{\mathrm{otherwise}}}\end{array}\right.$$

where succ(p 0 ) := {b | p 0 has a b-successor} and the set of nodes of G h 1 t , G h 2 t , and G are assumed to be disjoint. Now, replace the root of G h, t by (h 1,po), the root of Gh2.t by (h2.po), and extend G by the nodes and edges of these two trees. Finally, add a new node nv for every word v in L, and for each node of the trees Gh,, and Gh2.t reachable from the root of Gh1.t and Gh2.t by a path labeled v, add an edge with label a from it to n v . The extension is illustrated in Figure 10.

3. The same as in step 2, with roles of C and D switched.

4. Compute the canonical graph of G ′ , which is called G ′ a gain. Then, output the concept description C G of G '.
Proposition 3  The translation CG  of the graph G ′ computed by Algorithm 3 is the lcs E
of C and D.