Efficient Parallel Algorithms for String Editing and Related Problems

The string editing problem for input strings x and y consists of transforming x into y by performing a series of weighted edit operations on x of overall minimum cost. An edit operation on x can be the deletion of a symbol from x, the insertion of a symbol in x or the substitution of a symbol of x with another symbol. This problem has a well-known $O(|x||y|)$ time-sequential solution. Efficient PRAM parallel algorithms for the string editing problem are given. If m = min (|x|,|y|) and n = max (|x|,|y|), then the CREW bound is O(log m log n) time with O(mn / log m) processors. The CROW bound is O(log n(log log m)²) time with O(mn/ log log m) processors. In all algorithms, space is $O(mn)$.