If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser

If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. DOI. 10.1137/16M1061771. The CFG recognition problem is as follows: given a context-free grammar G and a string w of length n, decide whether w can be obtained from G. This is the most basic parsing question and is a core...

Full description

Bibliographic Details
Main Authors: Abboud, Amir, Backurs, Arturs, Williams, Virginia Vassilevska
Other Authors: Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory
Format: Article
Language:English
Published: Society for Industrial & Applied Mathematics (SIAM) 2021
Online Access:https://hdl.handle.net/1721.1/135888

Internet

https://hdl.handle.net/1721.1/135888

Similar Items