!Converted with LaTeX2HTML 95.1 (Fri Jan 20 1995) by Nikos Drakos (firstname.lastname@example.org), CBLU, University of Leeds >
In this section we consider the Minimum Conforming Edit Script problem, motivated in the previous section. The problem is stated as follows. Given a tree (the old tree), a tree (the new tree), and a (partial) matching M between their nodes, generate a minimum cost edit script that conforms to M and transforms to . Our algorithm starts with an empty edit script E and appends edit operations to E as it proceeds. To explain the working of the algorithm, we apply each edit operation to as it is added to E. When the algorithm terminates, we will have transformed into a tree that is isomorphic to . In addition, the algorithm extends the given partial matching M by adding new pairs of nodes to M as it adds operations to E. When the algorithm terminates, M is a total matching between the nodes of and .