General context-free recognition in less than cubic time
From MaRDI portal
Publication:1219690
DOI10.1016/S0022-0000(75)80046-8zbMath0312.68042WikidataQ55890023 ScholiaQ55890023MaRDI QIDQ1219690
Publication date: 1975
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
68Q25: Analysis of algorithms and problem complexity
68Q45: Formal languages and automata
68W99: Algorithms in computer science
Related Items
The aggregation and cancellation techniques as a practical tool for faster matrix multiplication, Context-free recognition via shortest paths computation: a version of Valiant's algorithm, Systolic parsing of context-free languages, An efficient all-parses systolic algorithm for general context-free parsing, An efficient recognizer for the Boolean closure of context-free languages, On the complexity of the recognition of parallel 2D-image languages, On efficient recognition of transductions and relations, Pattern selector grammars and several parsing algorithms in the context- free style, Algorithm partition and parallel recognition of general context-free languages using fixed-size VLSI architecture, Time complexity of languages recognized by one-way multihead pushdown automata, A note on two-way nondeterministic pushdown automata, Dynamic programming with convexity, concavity and sparsity, Extensions to Barrington's M-program model, Relative complexity of checking and evaluating, Recognition of EOL languages in less than quartic time, TAL recognition in \(O(M(n^2))\) time, Membership problems for regular and context-free trace languages, A divide-and-conquer approach to general context-free parsing, Time complexity of loop-free two-way pushdown automata, Boolean grammars, BRNGLR: a cubic Tomita-style GLR parsing algorithm, Safety in grammatical protection systems, A simple proof of Valiant's lemma, Unnamed Item, Complexity of some problems concerningL systems, Analysis and synthesis of structured parallel programs, Unnamed Item, The complexity of the membership problem for some extensions of context-free languagest†
