Parallel Parsing on a One-Way Array of Finite-State Machines
- 1 January 1987
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-36 (1) , 64-75
- https://doi.org/10.1109/tc.1987.5009449
Abstract
We show that a one-way two-dimensional iterative array of finite-state machines (2-DIA) can recognize and parse strings of any context-free language in linear time. What makes this result interesting and rather surprising is the fact that each processor of the array holds only a fixed amount of information (independent of the size of the input) and communicates with its neighbors in only one direction. This makes for a simple VLSI implementation. Although it is known that recognition can be done on a 2-DIA, previous parsing algorithms require the processors to have unbounded memory, even when the communication is two-way. We also consider the problem of finding approximate patterns in strings, the string-to-string correction problem, and the longest common subsequence problem, and show that they can be solved in linear time on a 2-DIA.Keywords
This publication has 13 references indexed in Scilit:
- Finding approximate patterns in stringsJournal of Algorithms, 1985
- VLSI architectures for high speed recognition of context-free languages and finite-state languagesACM SIGARCH Computer Architecture News, 1982
- The theory and computation of evolutionary distances: Pattern recognitionJournal of Algorithms, 1980
- A faster algorithm computing string edit distancesJournal of Computer and System Sciences, 1980
- Algorithms for the Longest Common Subsequence ProblemJournal of the ACM, 1977
- Iterative arrays with direct central controlActa Informatica, 1977
- Speed of Recognition of Context-Free Languages by Array AutomataSIAM Journal on Computing, 1975
- A linear space algorithm for computing maximal common subsequencesCommunications of the ACM, 1975
- The String-to-String Correction ProblemJournal of the ACM, 1974
- Real-Time Computation by n-Dimensional Iterative Arrays of Finite-State MachinesIEEE Transactions on Computers, 1969