Parsing Boolean grammars over a one-letter alphabet using online convolution

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

zbMATH Keywords

context-free grammarsparsingunary languagesinteger multiplicationBoolean grammarsconjunctive grammarsBoolean convolution

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

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

• ALGOL 60

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