Fast Context-Free Parsing Requires Fast Boolean Matrix Multiplication

Details Fast Context-Free Parsing Requires Fast Boolean Matrix Multiplication Fast Context-Free Parsing Requires Fast Boolean Matrix Multiplication

1997-08-14

arxiv.org/abs/cmp-lg/9708008v1

Proceedings of the 35th ACL/8th EACL, pp 9-15

Computer Science

Computation and Language

6 pages, uses aclap.sty and eepic.sty

Scientific paper

Valiant showed that Boolean matrix multiplication (BMM) can be used for CFG parsing. We prove a dual result: CFG parsers running in time $O(|G||w|^{3 - \myeps})$ on a grammar $G$ and a string $w$ can be used to multiply $m \times m$ Boolean matrices in time $O(m^{3 - \myeps/3})$. In the process we also provide a formal definition of parsing motivated by an informal notion due to Lang. Our result establishes one of the first limitations on general CFG parsing: a fast, practical CFG parser would yield a fast, practical BMM algorithm, which is not believed to exist.

Affiliated with

Also associated with

No associations

Rating

Fast Context-Free 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 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 Parsing Requires Fast Boolean Matrix Multiplication will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-257237