Parallel Parsing on a One-Way Array of Finite-State Machines

DOI10.1109/TC.1987.5009449MaRDI QIDQ3773378zbMATH OpenFDO

Authors Jik H. Chang, Oscar H. Ibarra, Michael A. Palis

Publication date 1987

Published in IEEE Transactions on Computers (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/TC.1987.5009449

zbMATH Keywords

context-free languagedynamic programmingfinite state machinesiterative arraylongest common subsequenceparsingpattern matchingsequence comparisonVLSI

Mathematics Subject Classification ID

Theory of compilers and interpreters (68N20) Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 4205997
• Parallel parsing on a one-way linear array of finite-state machines
• A parallel parsing algorithm for arbitrary context-free grammars
• Parallel parsing on the connection machine
• scientific article; zbMATH DE number 4119661
• scientific article; zbMATH DE number 140111
• Some theoretical aspects of parallel parsing
• On the complexity of parallel parsing of general context-free languages
• scientific article; zbMATH DE number 4108175
• Parallel \(LL\) parsing

Cited in

(21)

• Algorithm partition and parallel recognition of general context-free languages using fixed-size VLSI architecture
• Two-dimensional iterative arrays: Characterizations and applications
• Geometric problems on two-dimensional array processors
• Parallel parsing on a one-way linear array of finite-state machines
• A parallel parsing algorithm for arbitrary context-free grammars
• Hierarchies and undecidability results for iterative arrays with sparse communication
• Iterative arrays with finite inter-cell communication
• INSTANCE-SPECIFIC SOLUTIONS FOR ACCELERATING THE CKY PARSING OF LARGE CONTEXT-FREE GRAMMARS
• scientific article; zbMATH DE number 4205997 (Why is no real title available?)
• A VLSI design for the parallel finite state automaton and its performance evaluation as a hardware scanner
• APPLICATION-SPECIFIC ARRAY PROCESSORS FOR THE LONGEST COMMON SUBSEQUENCE PROBLEM OF THREE SEQUENCES ∗ †
• A three-dimensional uniquely parsable array grammar that generates and parses cubes
• Cellular automata with limited inter-cell bandwidth
• Hierarchies and undecidability results for iterative arrays with sparse communication
• Iterative arrays with finite inter-cell communication
• An NC algorithm for recognizing tree adjoining languages
• Systolic parsing of context-free languages
• An efficient all-parses systolic algorithm for general context-free parsing
• Low complexity classes of multidimensional cellular automata
• Parallel \(LL\) parsing
• Synthesis, structure and power of systolic computations

This page was built for publication: Parallel Parsing on a One-Way Array of Finite-State Machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3773378)