Donald Bren School of Information and Computer Sciences

Given two strings, X and Y, over a finite alphabet E, the modified edit distance between X and Y is the minimal cost of an edit sequence that changes X into Y, where the cost of substituting a character in Y for a character in X is context free, and the cost of deleting a substring from X or inserting a substring from Y into X is somewhat context sensitive. The modified edit distance does not require that the minimum cost over all edit sequences where the cost of substituting a character in E for a character in a string is context free, the cost of deleting a substring from a string is somewhat context sensitive, and the cost of inserting a string Z into X to obtain a string X' is equivalent to the cost of deleting Z from X' to obtain X again. We show that if the minimum cost over all edit sequences must be obtained, the modified edit distance becomes undecidable.