Tai, Kuo-Chung:
*The tree-to-tree correction problem*;
JACM 26:3, p.422-433;
1979

Library Entries:
ACM Digital Library,
DOI 10.1145/322139.322143

*Deskriptoren: *CVSM,
tree:differencing
*Abstract: *The tree-to-tree correction problem is to
determine, for two labeled ordered trees T and T', the
distance from T to T' as measured by the mlmmum cost
sequence of edit operations needed to transform T into T'
The edit operations investigated allow changing one node
of a tree into another node, deleting one node from a
tree, or inserting a node into a tree. An algorithm is
presented which solves this problem in time O(V * V' *
L**2 * L'**2), where V and V' are the numbers of nodes
respectively of T and T', and L and L' are the maximum
depths respectively of T and T'. Possible applications are
to the problems of measuring the similarity between trees,
automatic error recovery and correction for programming
languages, and determining the largest common substructure
of two trees.