S. Abiteboul, R. Hull, and V. Vianu, Foundations of Databases, 1995.

}. {u-i+1, }. , ·. {u-r, and }. , 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

}. Dist and T. ,

, 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

. Im,

. P-·-a-·-b-·-s-?-<-inv-fo-?-p-·-b-·-a-·-s-as and . Desired, 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)

C. Xi, 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

. ?-·-·-·-?-x-d, 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)

W. By-n-similarity and V. By-n-similarity-of-u-·-v, Hence uv = vu. By Lyndon-Schützenberger Theorem

. We-can-decompose-u, W. Get-u-=-u-1-·-·-·-u-p-,-v-=-v-1-·-·-·-v-q, and . =-w-1-·-·-·-w-p,

, 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 )