Foundations of Databases, 1995. ,
Im(g) 2. ?j, k > i, let a j ? {x j , x j }. Then dist Ti (g(a j ), g(x k )) ? min, pp.2-6 ,
,
, Let them be such that dist T0 (g(x j ), g(x k )) ? 2n + 5, and let's prove that dist W0 (g(x j ), g(x k )) ? dist T0 (g(x j ), g(x k )). it goes through at least one S-edge: the first time it does
,
Assume next that B can be decomposed as B 1 · · · B k , where each B i is n-similar to A. We can then apply k times Case 1 and obtain ,
, As we are not in Case 1, we can restrict our study to the cases where dist T (x, x A ) ? 2n+2 (the cases where dist T (x A , x B ) ? 2n + 2 can be treated similarly). We will need the following claims. The first one is just a simple observation
, Sk n (V), and x 0 ? x 1 ? · · · ? x p ? T be such that U i = C T (x i?1 , x i ). Since ? is ?-monotonous on V (U), the V i = , U i and V
, Sk n (V i ), which allows us to conclude. The next one is a variant of Lyndon-Schützenberger Theorem stated for contexts of hollow trees instead of words, Claim 29. Let n ? N, let T ? H ? , let x ? y ? z ? t be nodes of T , and let U := C T (x, y), V := C T (y, z) and W := C T (z, t)
xi+1) (x i , x i , x i+1 ), where x i and x i are the S-children of x i . Now, let ? n be the monoïd morphism from contexts to words extending ? n ,
are all the vertebrae of U, then |? n (U)| = height(U) = d, and the ith letter of ? n (U) is ? n (x i , x i+1 ) ,
, Let u := ? n (U), v := ? n (V) and w := ? n (W)
Hence uv = vu. By Lyndon-Schützenberger Theorem ,
,
, As dist T (x, x A ) ? 2n + 2, x A is in the N -neighborhood of x and set x 0 := x A and x 1 := ?(x A )