Parsing by matrix multiplication generalized to Boolean grammars

DOI10.1016/j.tcs.2013.09.011zbMath1277.68108OpenAlexW2156495052MaRDI QIDQ385966

Alexander Okhotin

Publication date: 13 December 2013

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2013.09.011

zbMATH Keywords

context-free grammarsparsingmatrix multiplicationBoolean grammarsconjunctive grammars

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Related Items (14)

Input-driven languages are linear conjunctive ⋮ Generalized LR parsing algorithm for grammars with one-sided contexts ⋮ The hardest language for grammars with context operators ⋮ Linear-space recognition for grammars with contexts ⋮ Efficient parallel and incremental parsing of practical context-free languages ⋮ Hardest languages for conjunctive and Boolean grammars ⋮ Unambiguous conjunctive grammars over a one-symbol alphabet ⋮ An extension of context-free grammars with one-sided context specifications ⋮ The Hardest Language for Conjunctive Grammars ⋮ Path querying on acyclic graphs using Boolean grammars ⋮ Formal languages over GF(2) ⋮ Language equations ⋮ Improved normal form for grammars with one-sided contexts ⋮ Two-sided context specifications in formal grammars

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Conjunctive and Boolean grammars: the true general case of the context-free grammars
• Complexity of equations over sets of natural numbers
• Context-free recognition via shortest paths computation: a version of Valiant's algorithm
• Parsing Boolean grammars over a one-letter alphabet using online convolution
• Well-founded semantics for Boolean grammars
• Matrix multiplication via arithmetic progressions
• Unambiguous Boolean grammars
• General context-free recognition in less than cubic time
• Improved time and space bounds for Boolean matrix multiplication
• TAL recognition in \(O(M(n^2))\) time
• Membership problems for regular and context-free trace languages
• Boolean grammars
• Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
• Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth
• Gaussian elimination is not optimal
• Recursive descent parsing for Boolean grammars
• Fast context-free grammar parsing requires fast boolean matrix multiplication
• BOOLEAN FUZZY SETS
• Multiplying matrices faster than coppersmith-winograd
• GENERALIZED LR PARSING ALGORITHM FOR BOOLEAN GRAMMARS

This page was built for publication: Parsing by matrix multiplication generalized to Boolean grammars