Abstract
Optimal lineartime algorithms for solving recurrence equations on simple systolic arrays are presented. The systolic arrays use only oneway communication between processors and communicate with the external environment through only one I/O port. Because of their architectural simplicity, the arrays are well suited for direct VLSI implementation. Applications to some pattern recognition and sequence comparison problems are given. For example, it is shown that the set of (k + 2)tuples of strings (x1, …, xk +1, y) such that y is a shuffle of x1, …, xk+1 can be recognized by a oneway kdimensional systolic array in (k + l) n  k time. The longest common subsequence (LCS) problem and the stringtostring correction problem are also considered: the length of an LCS of k + 1 sequences can be computed by a oneway kdimensional systolic array in (k + 1) n  k time; the edit distance between two strings can be computed by a oneway dimensional systolic array in 2n  1 time. Applications to other related problems, e.g., dynamic time warping and optimum generalized alignment, as well as optimaltime simulations of multihead acceptors and multitape transducers are also given.
Original language  English (US) 

Pages (fromto)  10461064 
Number of pages  19 
Journal  IEEE Transactions on Acoustics, Speech, and Signal Processing 
Volume  35 
Issue number  7 
DOIs 

State  Published  Jul 1987 
Externally published  Yes 
All Science Journal Classification (ASJC) codes
 Signal Processing