Parsing by matrix multiplication generalized to Boolean grammars
From MaRDI portal
Publication:385966
DOI10.1016/j.tcs.2013.09.011zbMath1277.68108OpenAlexW2156495052MaRDI QIDQ385966
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
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
