Loading [MathJax]/extensions/Safe.js
dx.doi.org
sci-hub
scholar.google.com
Identifying Syntactic differences Between Two Programs
Yang, Wuu
Software: Practice and Experience Journal - 1991 via Local Bibsonomy
Keywords: dblp


[link]
Summary by Joseph Paul Cohen 9 years ago

This is a dynamic programming algorithm known as Simple Tree Matching:

int simple_tree_match(a,b){

    if (a != b) return 0

    m = the number of first-level sub-trees of a
    n = the number of first-level sub-trees of b
    M[i,0] := 0 for i = 0,...,m
    M[0,j] := 0 for j = 0,...,n
    for(i := 1 to m){
        for(i := 1 to n){
            x := M[i,j-1]
            y := M[i-1,j]
            z := M[i-1,j-1]+ simple_tree_match(a_i,b_j)
            M[i,j] = max(x,y,z)
        }
    }
}
return M[m,n] + 1
}
Your comment:

Send Feedback
ShortScience.org allows researchers to publish paper summaries that are voted on and ranked!
About

Sponsored by: