

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

Formally, completions are defined as follows: Let G be an (infinite) description graph.

The graph G r is an extension of G if for every node n in G and for every attribute a E A
such that n has no outgoing edges labeled a, a new node m n,a is added, as well as an edge
(n, a, m,n,a). Now, let G 0 , G 1 , G 2 , . . . be a sequence of graphs such that G 0 = G and G i +1 is an extension of G f , for i ≥ 0. If G f = ( N i , E i , n 0 ), then

$$G^{\infty}:=\left(\bigcup_{i\geq0}N_{i}\,,\,\bigcup_{i\geq0}E_{i}\,,\,n_{0}\right)$$

is called the completion of G . By construction, G 00 is a complete graph. Furthermore, if G is deterministic, then G ∞ is deterministic as well. Finally, it is easy to see that a graph and its extension are equivalent. Thus, by induction, G ∞ ≡ t G .

The nodes in U i > 1 N i , i.e., the nodes in G ∞ that are not in G , are called tree nodes ; the nodes of G are called non-tree nodes. By construction, for every tree node t in G ∞ there is exactly one direct predecessor of t in G ∞ , i.e., there is exactly one node n and one attribute a such that ( n, a, t ) is an edge in G ∞ ; n is called a-predecessor of t. Furthermore, there is exactly one youngest ancestor n in G of a tree node t in G ∞ ; n is the youngest ancestor of t if there is a path from n to t in G ∞ which does not contain non-tree nodes except for n . Note that there is only one path from n to t in G ∞ . Finally, observe that non-tree nodes have only non-tree nodes as ancestors.

Note that the completion of a canonical description graph is always complete and deterministic.

In the sequel, let C, D be two concept descriptions in S, Gc = ( Nc, Ec, nc ), Gd =
( N D, E D, n D ) be their corresponding canonical graphs, and G V, G V be the completions of GC, GD. The products G := GC × GD and G ∞ := G P × G P are specified as in Definition 1. As usual, we may assume G and G ∞ are connected, i.e., they only contain nodes that are reachable from the root ( nc, nd); otherwise, one can remove all those nodes that cannot be reached from the root without changing the semantics of the graphs.

We denote the product G 8 × G 8 by G 8 instead of G 80 (or G 80 ) because otherwise this graph could be confused with the completion of G. In general, these graphs do not