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)
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Algorithms in computer science (68W99)
Related Items (66)
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 ⋮ A linear-time simulation of deterministic \(d\)-limited automata ⋮ Boolean grammars ⋮ On the sizes of DPDAs, PDAs, LBAs ⋮ Algebraic dynamic programming for multiple context-free grammars ⋮ Unnamed Item ⋮ An improved combinatorial algorithm for Boolean matrix multiplication ⋮ Improving quantum query complexity of Boolean matrix multiplication using graph collision ⋮ Unnamed Item ⋮ If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser ⋮ On the word problem for special monoids ⋮ A simple proof of Valiant's lemma ⋮ The aggregation and cancellation techniques as a practical tool for faster matrix multiplication ⋮ Finite loops recognize exactly the regular open languages ⋮ Pushdown reachability with constant treewidth ⋮ Unnamed Item ⋮ Parsing by matrix multiplication generalized to Boolean grammars ⋮ Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ Enumerating grammar-based extractions ⋮ On the semantic equivalence of language syntax formalisms ⋮ Unnamed Item ⋮ Linear-space recognition for grammars with contexts ⋮ Fast matrix multiplication and its algebraic neighbourhood ⋮ Time complexity of languages recognized by one-way multihead pushdown automata ⋮ Efficient parallel and incremental parsing of practical context-free languages ⋮ Complexity of the path avoiding forbidden pairs problem revisited ⋮ A note on two-way nondeterministic pushdown automata ⋮ Certified CYK parsing of context-free languages ⋮ Conservative groupoids recognize only regular languages ⋮ Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product ⋮ BRNGLR: a cubic Tomita-style GLR parsing algorithm ⋮ Context-free recognition via shortest paths computation: a version of Valiant's algorithm ⋮ Dynamic programming with convexity, concavity and sparsity ⋮ Edit Distance with Duplications and Contractions Revisited ⋮ On translating Lambek grammars with one division into context-free grammars ⋮ Safety in grammatical protection systems ⋮ An extension of context-free grammars with one-sided context specifications ⋮ Fast multiplication of matrices over a finitely generated semiring ⋮ Extensions to Barrington's M-program model ⋮ Parsing Boolean grammars over a one-letter alphabet using online convolution ⋮ Relative complexity of checking and evaluating ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Path querying on acyclic graphs using Boolean grammars ⋮ Formal languages over GF(2) ⋮ Recognition of EOL languages in less than quartic time ⋮ LR(0) conjunctive grammars and deterministic synchronized alternating pushdown automata ⋮ The complexity of the membership problem for some extensions of context-free languagest† ⋮ Complexity of some problems concerningL systems ⋮ TAL recognition in \(O(M(n^2))\) time ⋮ Systolic parsing of context-free languages ⋮ An efficient all-parses systolic algorithm for general context-free parsing ⋮ Fine-Grained Reductions and Quantum Speedups for Dynamic Programming. ⋮ 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 ⋮ Unnamed Item ⋮ Unnamed Item ⋮ An efficient recognizer for the Boolean closure of context-free languages ⋮ Elastic-Degenerate String Matching via Fast Matrix Multiplication ⋮ Improved normal form for grammars with one-sided contexts ⋮ On efficient recognition of transductions and relations ⋮ On the complexity of the recognition of parallel 2D-image languages ⋮ Analysis and synthesis of structured parallel programs ⋮ Two-sided context specifications in formal grammars
This page was built for publication: General context-free recognition in less than cubic time
