Systolic-based parallel architecture for the longest common subsequences problem

Smith, 1989 Sankoff, 1983 Aho, 1976, Bounds on the complexity of the longest common subsequence problem, J. ACM, 23, 1, 10.1145/321921.321922 Hirschberg, 1977, Algorithms for the longest common subsequence problem, J. ACM, 24, 664, 10.1145/322033.322044 Nakatsu, 1982, A longest algorithm suitable for similar text string, Acta Inform., 18, 171, 10.1007/BF00264437 Masek, 1980, A faster algorithm for computing string edit distances, J. Comput. System Sci., 20, 18, 10.1016/0022-0000(80)90002-1 Hirschberg, 1975, A linear space algorithm for computing maximal common subsequences, Comm. ACM, 18, 341, 10.1145/360825.360861 Kumar, 1987, A linear space algorithm for the longest common subsequence problem, Acta Inform., 24, 353, 10.1007/BF00265993 Apostolico, 1992, Fast linear-space computations of longest common subsequences, Theoret. Comput. Sci., 92, 3, 10.1016/0304-3975(92)90132-Y Allison, 1986, A bit string longest common subsequence algorithm, Inform. Process. Lett., 23, 305, 10.1016/0020-0190(86)90091-8 Chin, 1990, A fast algorithm for computing longest common subsequences of small alphabet size, J. Inform. Process., 13, 463 Wagner, 1974, The string-to-string correction problem, J. ACM, 21, 168, 10.1145/321796.321811 R.W. Irving, C.B. Fraser, Two algorithms for the longest common subsequence of three (or more) strings, in: Proc. 3rd Ann. Symp. CPM, Lecture Notes in Computer Science, vol. 664, Springer, Berlin, 1992, pp. 214–229. K. Hakata, H. Himai, The longest common subsequence problem for small alphabet size between many strings, in: Proc. 3rd Int. Symp. Algo. Computing, Lecture Notes in Computer Science, vol. 650, Springer, Berlin, 1992, pp. 469–478. V. Dančı́k, M.S. Paterson, Longest common subsequences, in: Proc. 11th Annual Sympon Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, vol. 775, Springer, Berlin, 1994, pp. 127–142. C.B. Yang, R.C.T. Lee, Systolic algorithms for the longest common subsequence problem, in: Proc. Int. Comput. Symp., 1984, pp. 895–901. Robert, 1985, A systolic array for the longest common subsequence problem, Inform. Process. Lett., 21, 191, 10.1016/0020-0190(85)90058-4 J.H. Chang, O.H. Ibarra, M.A. Pallis, Parallel parsing on a one-way array of finite-state machines, IEEE Trans. Computers C-36 (1987) 64–75. Lin, 1994, New systolic arrays for the longest common subsequence problem, Parallel. Comput., 20, 1323, 10.1016/0167-8191(94)90040-X G. Luce, J.F. Myoupo, An efficient linear systolic array for recovering longest common subsequences, in: Proc. 1st IEEE Int. Confon. Algo. Archi. for Paral. Proc., 1995, pp. 20–29. Lu, 1994, Parallel algorithms for the longest common subsequence problem, IEEE Trans. Comput., 5, 835 Apostolico, 1990, Efficient parallel algorithms for string editing and related problems, SIAM J. Comput., 19, 968, 10.1137/0219066 D.M. Champion, J. Rothstein, Immediate parallel solution of the longest common subsequence problem, in: Proc. Int. Confon. Parallel Processing, 1987, pp. 70–77. Kung, 1980, Why systolic architectures, IEEE Comput., 15, 37, 10.1109/MC.1982.1653825 R. Aubusson, I. Catt, Wafer-scale integration – a fault tolerant procedure, IEEE J. Solid-State Circ. SC-13 (3) (1978) 339–344. F.T. Leighton, C.E. Leiserson, Wafer-scale integration of systolic arrays, in: Proc. 23rd Symp. Fond. Comp. Sci. 1982, 297–311. Kung, 1984, Wafer-scale integration and two-level pipelined implementation of systolic arrays, J. Parallel Distributed Computing, 1, 32, 10.1016/0743-7315(84)90010-8 Lee, 1988, Synthesizing linear array algorithms from nested for loop algorithms, IEEE Trans. Computers, 37, 1578, 10.1109/12.9735 Hall, 1980, Approximate string matching, Comput. Surveys, 12, 54, 10.1145/356827.356830 P.A. Pevzner, M.S. Waterman, Matrix longest common subsequence problem, duality and Hilbert bases, in: Proc. 3rd Ann. Symp. CPM, Lecture Notes in Computer Science, vol. 664, Springer, Berlin, 1992, pp. 79–89.