Réseaux systoliques pour des problèmes de mots. (French) Zbl 0569.68063

We introduce systolic arrays for the real time solution of some general convolution problems. This paper is devoted to illustrate the power of the divide-and-conquer approach (which is well-known for sequential algorithms) for the design of efficient systolic architectures. We give three applications to words problems: the computation of the occurrences of a give word in a string; the real-time palindrome recognizer; the real-time square acceptor. This divide-and-conquer technique can be viewed as the last step of the methodology introduced by C. E. Leiserson and J. B. Saxe [J. VLSI Comput. Syst. 1, 41-67 (1983; Zbl 0532.94015)] for the design of systolic systems.


68Q45 Formal languages and automata
68Q80 Cellular automata (computational aspects)


Zbl 0532.94015
Full Text: EuDML


[1] 1. Y. M. BARZDIN, Complexity of Recognition of Symmetry in Turing Machines, Problemy Kibernetiki, vol. 15, 1965. · Zbl 0192.06602
[2] 2. S. N. COLE, Real-time Computation by n-Dimensional Iterative Arrays of Finite-state Machines, I.E.E.E. Trans. on Computers, vol. C18, avril 1979, p. 349-365. Zbl0172.20804 MR250518 · Zbl 0172.20804 · doi:10.1109/T-C.1969.222663
[3] 3. K. CULIK II, J. GRUSKA et A. SALOMAA, On a Family of L. Languages Resulting from Systolic Tree Automata, Research Report CS-81-36, University of Waterloo. · Zbl 0493.68054
[4] 4. K. CULIK II, J. GRUSKA et A. SALOMAA, Systolic Treillis Automata for (VLSI), Research Report CS-81-36, University of Waterloo. · Zbl 0493.68054
[5] 5. M. J. FOSTER and H. T. KUNG, Recognize Regular Langages with Programmable Building-blocks, in the Proceedings of the VLSI, 1981, Conference, Edinburgh.
[6] 6. E. HOROWITZ A. ZORA, Divide-and-conquer for Parallel Processing, I.E.E.E. Trans. on Computers, vol.C32, (6), juin 1983. Zbl0513.68029 · Zbl 0513.68029 · doi:10.1109/TC.1983.1676280
[7] 7. A. V. KULKARNI et D. W. L. YEN, Systolic Processing and an Implementation for Signal and Image Processing, I.E.E.E. Trans, on Computers, vol. C31, octobre 1982, p. 1000-1009.
[8] 8. H. T. KUNG, Why Systolic Architectures, I.E.E.E. Computer, vol. 15, n^\circ 1, janvier 1982, p. 37-46.
[9] 9. H. T. KUNG et P. L. LEHMAN, Systolic V.L.S.J. Arrays for Relational Database Operations, Proceedings of the 1980 A.C.M./SIGMOD International Conference on Management of data, Los Angeles, U.S.A.
[10] 10. H. T. KUNG et C. E. LEISERSON, Systolic Arrays for (VLSI), in the Proceedings of the Symposium on Sparse Matrix Computations and their Applications, Knox- ville, 1978. Zbl0404.68037 MR566379 · Zbl 0404.68037
[11] 11. C. E. LEISERSON et J. D. SAXE, Optimizing Synchronous Systems, 22-th Annual Symposium on Foundations of Computer Science, I.E.E.E., octobre 1981, p. 23-36.
[12] 12. Y. ROBERT et M. TCHUENTE, Designing Efficient Systolic Algorithms, Rapport de Recherche 393, Lab. I.M.A.G., Grenoble, septembre 1983.
[13] 13. A. R. SMITH III, Cellular Automata theory, Technical Report 2, Stanford Electronics Laboratories, décembre 1969.
[14] 14. M. STEINBY, Systolic Tree and Systolic Langage Recognition by Tree Automata, Theoretical Computer Science, vol. 22, 1983, p. 219-232. Zbl0501.68046 MR693057 · Zbl 0501.68046 · doi:10.1016/0304-3975(83)90146-9
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.