Parsing Boolean grammars over a one-letter alphabet using online convolution
From MaRDI portal
Publication:714852
DOI10.1016/j.tcs.2012.06.032zbMath1253.68200OpenAlexW2008600488MaRDI QIDQ714852
Alexander Okhotin, Christian Reitwießner
Publication date: 11 October 2012
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2012.06.032
context-free grammarsparsingunary languagesinteger multiplicationBoolean grammarsconjunctive grammarsBoolean convolution
Related Items (4)
Parsing by matrix multiplication generalized to Boolean grammars ⋮ Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ On the expressive power of univariate equations over sets of natural numbers ⋮ Unambiguous conjunctive grammars over a one-symbol alphabet
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the expressive power of univariate equations over sets of natural numbers
- Complexity of equations over sets of natural numbers
- One-nonterminal conjunctive grammars over a unary alphabet
- Well-founded semantics for Boolean grammars
- Matrix multiplication via arithmetic progressions
- Unambiguous Boolean grammars
- Satisfiability of algebraic circuits over sets of natural numbers
- General context-free recognition in less than cubic time
- Fast on-line integer multiplication
- Boolean grammars
- Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth
- Equivalence problems for circuits over sets of natural numbers
- The complexity of membership problems for circuits over sets of natural numbers
- CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES
- Faster Integer Multiplication
- Fast Parsing for Boolean Grammars: A Generalization of Valiant’s Algorithm
- Multiplying matrices faster than coppersmith-winograd
- Two Families of Languages Related to ALGOL
This page was built for publication: Parsing Boolean grammars over a one-letter alphabet using online convolution
