Computer Science – Computation and Language
Scientific paper
2001-12-15
Journal of the ACM 49(1), pp. 1--15, January 2002
Computer Science
Computation and Language
To appear in Journal of the ACM
Scientific paper
In 1975, Valiant showed that Boolean matrix multiplication can be used for parsing context-free grammars (CFGs), yielding the asympotically fastest (although not practical) CFG parsing algorithm known. We prove a dual result: any CFG parser with time complexity $O(g n^{3 - \epsilson})$, where $g$ is the size of the grammar and $n$ is the length of the input string, can be efficiently converted into an algorithm to multiply $m \times m$ Boolean matrices in time $O(m^{3 - \epsilon/3})$. Given that practical, substantially sub-cubic Boolean matrix multiplication algorithms have been quite difficult to find, we thus explain why there has been little progress in developing practical, substantially sub-cubic general CFG parsers. In proving this result, we also develop a formalization of the notion of parsing.
No associations
LandOfFree
Fast Context-Free Grammar Parsing Requires Fast Boolean Matrix Multiplication does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Fast Context-Free Grammar Parsing Requires Fast Boolean Matrix Multiplication, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast Context-Free Grammar Parsing Requires Fast Boolean Matrix Multiplication will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-345239