Fast Parsing for Boolean Grammars: A Generalization of Valiant’s Algorithm

DOI10.1007/978-3-642-14455-4_31zbMath1250.68145OpenAlexW1500579221MaRDI QIDQ3584905

Alexander Okhotin

Publication date: 31 August 2010

Published in: Developments in Language Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-14455-4_31

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Related Items (8)

Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ One-nonterminal conjunctive grammars over a unary alphabet ⋮ LR(0) Conjunctive Grammars and Deterministic Synchronized Alternating Pushdown Automata ⋮ Parsing Boolean grammars over a one-letter alphabet using online convolution ⋮ Expressive power of \(\text{LL}(k)\) Boolean grammars ⋮ LR(0) conjunctive grammars and deterministic synchronized alternating pushdown automata ⋮ Comparing Linear Conjunctive Languages to Subfamilies of the Context-Free Languages ⋮ Language equations with complementation: expressive power

This page was built for publication: Fast Parsing for Boolean Grammars: A Generalization of Valiant’s Algorithm