00000cab a22000003a 4500 UP-99796217608822974 Buklod 20231007234829.0 m |o d | ta 090506s xx d | ||r ||||| || DENGII eng Luce, Guillaume Application-specific array processors for the longest common subsequence problem of three sequences. pp. 27-52 We design linear time systolic-based parallel algorithms that run on two-dimensional arrays for both computing the length and recovering a longest common subsequence of three given sequences that are appropriate for very large-scale integration (VLSI) implementation. These problems have been qualified to be difficult to be solved in linear time in [14], and our approach, which generalizes the methods used for determining a longest common subsequence of two strings [28, 38] to the case of three strings, enables to solve both problems in linear time. Given the three sequences A, B and C of length n, m and l (n < m < l), we provide an algorithm that computes the length p of their longest common subsequence on a modular I/O bounded one-way two-dimensional array of nm processors in n + 2m + 1 - 1 time steps. To compute a longest common subsequence of the three given strings, we show that each processor of the above array requires an O (min {n,p}) local storage to solve the problem in 2n+3m+l+p-2 time-steps. Systolic-based parallel architectures and algorithms. VLSI systems. Special purpose processors. Longest common subsequence problem of three strings. Dynamic programming. Parallel algorithms and applications. 13, 1 (1998). FO UPD DENG-II Article