We will continue the edit distance problem, giving further results and more insight into the proofs. The concept of colored regularity graphs of Alon and Stav are used to compute edit distance without direct use of Szemeredi's regularity lemma. In addition, there is a weighted version of Turan's theorem which may be of independent interest.
|