# Computing tree alignment distance

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

$D(F_1[i_1, i_s], F_2[j_1, j_t]) = \mu(l_1[i_s], \lambda) + min_{1 \leq k \leq t} (D(F_1[i_1, i_{s-1}, F_2[j_1, j_{k-1}]]) + D(F_1[i_s], F_2[j_k, j_t]))$

However, there is no recurrence formula given to compute $D(F_1[i_s], F_2[j_k, j_t])$. How did we obtain this?

I don't think the following holds either: $D(F_1[i_s], F_2[j_k, j_t]) = D(F_1[i_s], F_2[j_1, j_t]) - D(F_1[i_s], F_2[j_1, j_{k-1}])$?

• 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. – D.W. Mar 22 '17 at 21:27
• $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 :) – spin Mar 22 '17 at 22:16
• OK, got it -- I overlooked that. Thank you for the explanation. – D.W. Mar 22 '17 at 22:27
• 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. – 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).