Informally, an edit script gives a sequence of edit operations that
transforms one tree into another. Formally, we say when
is the result of applying
the edit operation
to
. Given a sequence
of edit operations, we say
if there exist
such that
. A sequence E of edit
operations transforms
into
if
and
is isomorphic to
. (Recall that two trees are isomorphic if they differ only in
the identifiers of their nodes.) We call such a sequence of edit
operations an edit script of
with respect to
.
Notice that an edit script does not tell us how the original matching
between
and
should be modified to obtain the total
matching between
and
. This will be done as the edit
script is generated; see Section 4.
: Applying the edit script of Example 3.1