Fast Context-Free Grammar Parsing Requires Fast Boolean Ma trix

Title: Fast Context-Free Grammar Parsing Requires Fast Boolean Ma trix

Abstract: This research article explores the relationship between the speed of parsing context-free grammars (CFGs) and the efficiency of multiplying Boolean matrices. It proposes that any CFG parser with a time complexity of O(gn3−ǫ) can be efficiently converted into an algorithm to multiply m×mBoolean matrices in time O(m3−ǫ/3). This is a significant finding because practical, sub-cubic Boolean matrix multiplication algorithms have been difficult to find, and the article explains why there has been little progress in developing practical, sub-cubic general CFG parsers.

The article first introduces CFGs, a widely used model for representing the structure of programming languages, human languages, and even biological data. It then discusses the challenges of parsing long strings using existing CFG parsing algorithms, such as the CKY algorithm and Earley's algorithm, which have a worst-case running time of O(gn3).

The main theorem of the paper states that fast CFG parsing requires fast Boolean matrix multiplication. This is because the CKY algorithm, which is the fastest known CFG parsing method, relies on the ability to efficiently multiply Boolean matrices. The article demonstrates this by converting the CKY algorithm into an algorithm for multiplying Boolean matrices, showing that the time complexity of the CKY algorithm can be reduced to the time complexity of the Boolean matrix multiplication.

The article also discusses the implications of this finding. It suggests that the development of practical, sub-cubic CFG parsers has been hindered by the lack of efficient Boolean matrix multiplication algorithms. It concludes by stating that further research into fast Boolean matrix multiplication could potentially lead to faster CFG parsing algorithms.

Link to Article: https://arxiv.org/abs/0112018v1 Authors: arXiv ID: 0112018v1