page 2  (24 pages)
to previous section1
3to next section

We can solve several problems, in particular the recognition of strings in context free grammars in Chomsky Normal Form, using dynamic programming methods in O(n3) sequential time. Partial methods exist for mapping these algorithms onto systolic arrays that run in O(2n) time, similar to Kosaraju s implementation of CNF recognition. These methods only accomplish a portion of the mapping; they involve pipelining steps that can require considerable insight and have a critical effect on the speed and complexity of the resulting algorithm.