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

DOI10.1016/J.TCS.2012.06.032zbMATH Open1253.68200OpenAlexW2008600488MaRDI QIDQ714852FDOQ714852

Authors: 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

Recommendations

• Parsing by matrix multiplication generalized to Boolean grammars
• Fast parsing for Boolean grammars: a generalization of Valiant's algorithm
• Developments in Language Theory
• Fast context-free grammar parsing requires fast Boolean matrix multiplication
• Boolean grammars

zbMATH Keywords

context-free grammarsparsingunary languagesinteger multiplicationBoolean grammarsconjunctive grammarsBoolean convolution

Mathematics Subject Classification ID

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

Cites Work

• Faster integer multiplication
• Title not available (Why is that?)
• Multiplying matrices faster than coppersmith-winograd
• Matrix multiplication via arithmetic progressions
• Title not available (Why is that?)
• General context-free recognition in less than cubic time
• Boolean grammars
• Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth
• The complexity of membership problems for circuits over sets of natural numbers
• CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES
• Title not available (Why is that?)
• Two Families of Languages Related to ALGOL
• Complexity of equations over sets of natural numbers
• Well-founded semantics for Boolean grammars
• Unambiguous Boolean grammars
• Fast on-line integer multiplication
• Fast parsing for Boolean grammars: a generalization of Valiant's algorithm
• On the expressive power of univariate equations over sets of natural numbers
• One-nonterminal conjunctive grammars over a unary alphabet
• Title not available (Why is that?)
• Equivalence problems for circuits over sets of natural numbers
• Satisfiability of algebraic circuits over sets of natural numbers

Cited In (5)

• On the expressive power of univariate equations over sets of natural numbers
• Fast parsing for Boolean grammars: a generalization of Valiant's algorithm
• Conjunctive and Boolean grammars: the true general case of the context-free grammars
• Unambiguous conjunctive grammars over a one-symbol alphabet
• Parsing by matrix multiplication generalized to Boolean grammars

Uses Software

• ALGOL 60

This page was built for publication: Parsing Boolean grammars over a one-letter alphabet using online convolution

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q714852)