The distance between two ordered labeled trees is considered to be the minimum sum of the weights associated with the edit operations (insertion, deletion, and substitution) required to transform one tree to another. The problem of computing this distance and the optimal transformation 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 involving the number and type of edit operations to be performed. An algorithm to compute this constrained distance is presented. If for a tree T, Span(T) is defined as the MinDepth(T),Leaves(T), the time and space complexities of this algorithm are: Time: O(|T1|*|T2|*(Min{|T1|,|T2|})2 *Span (T1)*Span(T2)) Space:O(|T1|* |T2|*Min{|T1|,|T2|}).

Additional Metadata
Persistent URL dx.doi.org/10.1016/0020-0255(94)90004-3
Journal Information Sciences
Citation
Oommen, J, & Lee, W. (William). (1994). Constrained tree editing. Information Sciences, 77(3-4), 253–273. doi:10.1016/0020-0255(94)90004-3