CONSTRAINED TREE EDITING

The distance between two ordered labeled trees is considered to be the minimum sum of the weights associated with the edit operations (inser tion, deletion, and substitution) required to transform one tree to an other. The problem of computing this distance and the optimal transfor mation using no edit constraints has been studied in the literature [3 , 4, 7-9, 11]. In this paper, we consider the problem of transforming one tree T1 to another tree T2 using any arbitrary edit constraint inv olving the number and type of edit operations to be performed. An algo rithm to compute this constrained distance is presented. If for a tree T, Span(T) is defined as the Min(Depth(T),Leaves(T)), the time and sp ace complexities of this algorithm are: Time: O(\T1\ \T2\* (Min{\T1\ , \T2\})2 Span(T1) * Span(T2)) Space: O(\T1\* \T2\* Min{\T1\, \T2\))