I am implementing the dynamic programming algorithm for computing tree alignment distance as described in "Alignment of trees — an alternative to tree edit". But I got stuck in lemma 3 on page 141 (page 5 of pdf). The notations are given at the beginning of section 2. The last case in lemma 3 says


However, there is no recurrence formula given to compute . How did we obtain this?

I don't think the following holds either: x?

  • 1
    $\begingroup$ Welcome to CS.SE! I think you should be asking a more basic question: what is the definition of $F_1[i_s]$? Anyway, a good way to approach this is probably to try to prove the lemma yourself. Do you understand the proofs of the other cases (Case 1, 2, 2.1, 2.2, 2.3)? I suggest studying those, then trying to apply a similar methodology to reason about that case (Case 3) and try to derive a formula on your own. Also, I don't know what your final line is referring to ("I don't think..."), but in any case, we prefer that you ask only one question per post. $\endgroup$ – D.W. Mar 22 '17 at 21:27
  • $\begingroup$ $F_1[i_s]$ is actually defined in section 2 as the first forest under node $i_s$. My concern was that the recurrence relationship are of forests starting from $i_1, j_1$ but we need $D(F_1[i_s], F_2[j_k, j_t])$ which start with $j_k$ and not $j_1$. Anyhow, thanks for your help :) $\endgroup$ – spin Mar 22 '17 at 22:16
  • $\begingroup$ OK, got it -- I overlooked that. Thank you for the explanation. $\endgroup$ – D.W. Mar 22 '17 at 22:27
  • $\begingroup$ Could you give some more context, please? People shouldn't have to go find section2 of a document that you've liked just to figure out what you're even talking about. Also, please replace the images of equations with LaTeX. $\endgroup$ – David Richerby Mar 23 '17 at 12:18

If I understand the paper correctly (and I might not), the solution seems to be described in Section 2.2 of the paper. It says "we have to compute $D(F_1[i],F_2[j_s,j_t])$..." and then it goes on to describe a strategy for doing so (namely, the Procedure 1, as described in Figure 2).

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.