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

DOI10.1016/J.TCS.2012.06.032MaRDI QIDQ714852zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

context-free grammarsparsingunary languagesinteger multiplicationBoolean grammarsconjunctive grammarsBoolean convolution

Mathematics Subject Classification ID

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

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

Cites work

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

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

Describes a project that uses

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)