CFG Parsing

Back to List
method ID: cfgparsing

Related Papers

Fast Context-Free Parsing Requires Fast Boolean Matrix Multiplication

Authors: nan

Publication: TIPSTER (1997)

DOI: nan

Valiant showed that Boolean matrix multiplication (BMM) can be used for CFG parsing. We prove a dual re- sult: CFG parsers running in time O([Gl[w[ 3-e) on a grammar G …...

43910