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