Algorithm partition and parallel recognition of general context-free languages using fixed-size VLSI architecture (Q1084875)

Recognition of general context-free languages has been very important in language processing and syntactic recognition. Many researchers have attempted to speed-up the recognition procedure. Recently, several VLSI implementations of context-free language recognition have been proposed. The main disadvantages of these proposed VLSI systems is that the size of the processor array is critical to the performance. That is, an \(n\times n\) upper triangular array can only process strings with length not longer than n. In this paper we propose two algorithms which can recognize general context-free languages without restriction on the length of input string. The first one has time complexity \(O(n^ 4/k^ 2)\) using \(k\times k\) processing elements to recognize n input symbols; if \(k=n\), its time complexity will be \(O(n^ 2)\). The second one, if using \(k\times k\) processing elements to recognize n input symbols, has time complexity \(O(n^ 3/k^ 2)\); if \(k=n\), the time complexity will be O(n). If there are several such modules, we can perform parallel recognition of general context-free languages. Since these algorithms essentially speed-up the dynamic programming procedure by using highly pipelining and parallelism of VLSI architecture, the proposed algorithms may also be useful for other problems solvable by dynamic programming.