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

DOI10.1109/TC.1987.5009449zbMath0634.68084MaRDI QIDQ3773378

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

Publication date: 1987

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

zbMATH Keywords

dynamic programmingcontext-free languageVLSIpattern matchingparsingsequence comparisonlongest common subsequencefinite state machinesiterative array

Mathematics Subject Classification ID

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

Related Items (15)

A parallel parsing algorithm for arbitrary context-free grammars ⋮ Two-dimensional iterative arrays: Characterizations and applications ⋮ Low complexity classes of multidimensional cellular automata ⋮ Hierarchies and undecidability results for iterative arrays with sparse communication ⋮ Parallel \(LL\) parsing ⋮ Synthesis, structure and power of systolic computations ⋮ An NC algorithm for recognizing tree adjoining languages ⋮ INSTANCE-SPECIFIC SOLUTIONS FOR ACCELERATING THE CKY PARSING OF LARGE CONTEXT-FREE GRAMMARS ⋮ Hierarchies and undecidability results for iterative arrays with sparse communication ⋮ Cellular automata with limited inter-cell bandwidth ⋮ Iterative arrays with finite inter-cell communication ⋮ Iterative arrays with finite inter-cell communication ⋮ Systolic parsing of context-free languages ⋮ An efficient all-parses systolic algorithm for general context-free parsing ⋮ APPLICATION-SPECIFIC ARRAY PROCESSORS FOR THE LONGEST COMMON SUBSEQUENCE PROBLEM OF THREE SEQUENCES ∗ †

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