## 4 Edit Distance with Block Moves, Block Deletions, Character Insertions
### Non Recursive Block Moves and Deletions  
Recursive operations allow one to deal with substrings that have already been dealt with, and which do not occur consecutively in the original string. In the following, we define when moves and deletes are considered recursive. [PERSON] [5] gives a similar definition to non recursive block operations called \"restricted editing sequences\". **Definition:** A sequence of operations applied to a string is _recursive with respect to move operations_ if it contains an operation which moves a substring whose characters do not occur consecutively in the original string. For example, if \(S\) is the string _abcde_ and the character \(b\) is moved to obtain the string \(T=\)_acdbe_, then moving the substring _dbe_ or _ac_ are both considered as recursive moves. **Definition:** A sequence of operations including character insertions, block moves, and block deletions is _recursive with respect to move and delete operations_ if it moves or deletes a substring whose characters do not occur consecutively in the original string. For example, if \(S\) is the string _abcde_ and the character \(b\) is moved to obtain the string \(T=\)_acdbe_, then deleting the substring _dbe_ or _ac_ are both recursive with respect to move and delete operations. **Theorem 2. ** If there is a sequence of \(k\) recursive move operations that convert \(S\) into \(T\), then there is a non-recursive sequence of no more than \(3k\) moves that convert \(S\) to \(T\). **Proof:** By induction on \(k\). _Base case: \(k=1\)._ One move operation converts \(S\) to \(T\). Since this move is not recursive, \(S\) is converted to \(T\) in less than three non-recursive operations. _Inductive hypothesis:_ Assume that for every recursive sequence of \(l<k\) moves that convert \(S\) to \(T\), there is a conversion of \(S\) to \(T\) of a non-recursive sequence of no more than \(3l\) moves. We prove that this holds for \(l=k\). _Induction step:_ Consider any recursive sequence of \(k\) moves that convert \(S\) to \(T\). Remove the last move of this sequence. Denote the obtained string by \(T^{\prime}\). There is a recursive sequence of \(k-1\) moves that convert \(S\) to \(T^{\prime}\). Using the inductive hypothesis, a non-recursive sequence converts \(S\) to \(T^{\prime}\) by not more than \(3(k-1)\) operations. These \(3(k-1)\) operations introduce a parsing of \(S\) into \(r\) blocks \(\{A_{1},A_{2},\cdots,A_{r}\}\), where each block \(A_{i}\) contains consecutive characters in S. A move operation of a block \(b\) introduces at most two boundaries in the source location, where the substrings to the left of the left boundary, and the substring to the right of the right boundary can be either blocks that were originally there, or blocks that were transferred to that location by previous operations. A move operation of \(b\) also introduces a boundary in its destination. Therefore not all substrings \(A_{i}\) are necessarily substrings that were moved. This way a move operation introduces \(3\) additional blocks, two in its source location and one in its destination. More formally, \(b\) is of the form \(A_{i-1}^{2}A_{i}A_{i+1}\cdots A_{j}A_{j+1}^{1}\), where \(A_{i-1}^{2}\) is a suffix of the block \(A_{i-1}\) and \(A_{j+1}^{1}\) is a prefix of \(A_{j+1}\). The symbols \(A_{i-1}^{1}\) and \(A_{j+1}^{2}\) will denote the remaining prefix and suffix of the corresponding blocks, respectively. Every block \(A_{x}\), \(i\leq x\leq j\), which was already moved by non-recursive moves, could be moved straight to its final location. If blocks \(A_{i-1}\) and \(A_{j+1}\) were moved within the first \(3(k-1)\) operations, then when non-recursive operations are considered, only the partial blocks \(A_{i-1}^{1}\) and \(A_{j+1}^{2}\)are moved.