Abstract

Given strings A and B over an alphabet ? ? double-struck U sign, where U is some numerical universe closed under addition and subtraction, and a distance function d(A, B) that gives the score of the best (partial) matching of A and B, the transposition invariant distance is mmt?U{d(A + t, B)}, where A + t = (a1 + t)(a2 + t) . . . (am + t). We study the problem of computing the transposition invariant distance for various distance (and similarity) functions d, that are different versions of the edit distance. For all these problems we give algorithms whose time complexities are close to the known upper bounds without transposition invariance. In particular, we show how sparse dynamic programming can be used to solve transposition invariant problems. © Springer-Verlag Berlin Heidelberg 2003.