CVSM Bibliography, Entry [ Ta1979JACM ]


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.