String editing on a one-way linear array of finite-state machines

The authors give an efficient parallel algorithm for the string edit problem. The model of computation is a one-way linear array of identical finite-state machines (nodes). The data movement in the array is one-way, from left to right. For inputs of length n, the array uses n nodes. The algorithm can produce the actual minimum-cost edit sequence in linear time. The previous parallel algorithm for this problem runs in O(n) time on a one-way two-dimensional array of finite-state machines using n ² nodes. The best serial (RAM) algorithm for the problem takes O(n²/log n) time and space. Applications to other problems such as the longest common subsequence and approximate pattern matching are discussed