Fast context-free grammar parsing requires fast boolean matrix multiplication

DOI10.1145/505241.505242zbMath1323.68332arXivcs/0112018OpenAlexW2025063099WikidataQ55890024 ScholiaQ55890024MaRDI QIDQ3196632

Lillian Lee

Publication date: 30 October 2015

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cs/0112018

zbMATH Keywords

Boolean matrix multiplicationcontext-free grammar parsing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Grammars and rewriting systems (68Q42)

Related Items (20)

Complexity of Searching for 2 by 2 Submatrices in Boolean Matrices ⋮ A linear-time simulation of deterministic \(d\)-limited automata ⋮ Efficient transitive closure of sparse matrices over closed semirings ⋮ On the sizes of DPDAs, PDAs, LBAs ⋮ Algebraic dynamic programming for multiple context-free grammars ⋮ If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser ⋮ Pushdown reachability with constant treewidth ⋮ Parsing by matrix multiplication generalized to Boolean grammars ⋮ On computing discretized Ricci curvatures of graphs: local algorithms and (localized) fine-grained reductions ⋮ Unnamed Item ⋮ On the semantic equivalence of language syntax formalisms ⋮ Fast matrix multiplication and its algebraic neighbourhood ⋮ Unnamed Item ⋮ 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 ⋮ Fast multiplication of matrices over a finitely generated semiring ⋮ Unnamed Item ⋮ Two-dimensional pattern matching against local and regular-like picture languages ⋮ Annotated regular expressions and input-driven languages ⋮ Elastic-Degenerate String Matching via Fast Matrix Multiplication

This page was built for publication: Fast context-free grammar parsing requires fast boolean matrix multiplication