Algorithm partition and parallel recognition of general context-free languages using fixed-size VLSI architecture
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.
- scientific article; zbMATH DE number 3978426
- Parallel recognition and parsing on mesh connected computers with multiple broadcasting
- Parallel Parsing on a One-Way Array of Finite-State Machines
- A parallel parsing algorithm for arbitrary context-free grammars
- scientific article; zbMATH DE number 4205997
- A modification of Warshall's algorithm for the transitive closure of binary relations
- A Theorem on Boolean Matrices
- Algorithm partition and parallel recognition of general context-free languages using fixed-size VLSI architecture
- General context-free recognition in less than cubic time
- scientific article; zbMATH DE number 3858396 (Why is no real title available?)
- scientific article; zbMATH DE number 3573276 (Why is no real title available?)
- scientific article; zbMATH DE number 3449757 (Why is no real title available?)
- Parallel Parsing Algorithms and VLSI Implementations for Syntactic Pattern Recognition
- Speed of Recognition of Context-Free Languages by Array Automata
- Algorithm partition and parallel recognition of general context-free languages using fixed-size VLSI architecture
- VLSI architectures for string matching and pattern matching
- Efficient reconfigurable embedded parsers
- Parallel recognition and parsing on mesh connected computers with multiple broadcasting
- Context-free recognition via shortest paths computation: a version of Valiant's algorithm
This page was built for publication: Algorithm partition and parallel recognition of general context-free languages using fixed-size VLSI architecture
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1084875)
