Transposition Invariant String Matching

S is a subset of some some numerical universe U closed under addition
and subtraction, and a distance function d(A,B) that gives the score of
the best matching of A and B, the transposition invariant distance is
min{d(A+t,B) | t in U}, where A+t=(a_1+t)(a_2+t) ... (a_m+t). In this
talk, we consider the problem of computing the transposition invariant
versions of several distance measures that are suitable for comparing
numeric strings. In particular, we show how sparse dynamic programming
can be exploited in computing transposition invariant edit distances