Context-free recognition via shortest paths computation: a version of Valiant's algorithm

DOI10.1016/0304-3975(94)00265-KzbMATH Open0873.68116MaRDI QIDQ673077FDOQ673077

Authors: Wojciech Rytter 

Publication date: 28 February 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

Recommendations

• A simple proof of Valiant's lemma
• Fast context-free grammar parsing requires fast Boolean matrix multiplication
• scientific article; zbMATH DE number 3978426
• Algorithm partition and parallel recognition of general context-free languages using fixed-size VLSI architecture
• Parsing by matrix multiplication generalized to Boolean grammars

zbMATH Keywords

context-free languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• General context-free recognition in less than cubic time
• On efficient parallel computations of costs of paths on a grid graph
• Title not available (Why is that?)

Cited In (6)

• If the current clique algorithms are optimal, so is Valiant's parser
• A simple proof of Valiant's lemma
• An Efficient Algorithm for Solving the Dyck-CFL Reachability Problem on Trees
• Efficient Computation of Throughput Values of Context-Free Languages
• Recognizing two-sided contexts in cubic time
• Parsing by matrix multiplication generalized to Boolean grammars

This page was built for publication: Context-free recognition via shortest paths computation: a version of Valiant's algorithm

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