Algorithm partition and parallel recognition of general context-free languages using fixed-size VLSI architecture
type: Item
instance of: scholarly article
title: Algorithm partition and parallel recognition of general context-free languages using fixed-size VLSI architecture
zbMATH Open document ID: 0606.68078
DOI: 10.1016/0031-3203(86)90003-8
author: B. George
published in: Pattern Recognition
publication date: 1986-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68T10
Mathematics Subject Classification ID: 68W99
Mathematics Subject Classification ID: 90C39
zbMATH DE Number: 3980523
zbMATH Keywords: context-free language recognition
zbMATH Keywords: dynamic programming
MaRDI profile type: Publication
full work available at URL: 0031-3203(86)90003-8
OpenAlex ID: W2026227831
cites work: General context-free recognition in less than cubic time
cites work: Q4144216
cites work: Speed of Recognition of Context-Free Languages by Array Automata
cites work: Parallel Parsing Algorithms and VLSI Implementations for Syntactic Pattern Recognition
cites work: Q3326832
cites work: A modification of Warshall's algorithm for the transitive closure of binary relations
cites work: A Theorem on Boolean Matrices
cites work: Q4773298
description: scientific article; zbMATH DE number 3980523