| tech,6-2-P97-1002,ak | parsing </term> . We prove a dual result : <term> | CFG parsers | </term> running in <term> time </term> O ( \ | #28970 We prove a dual result:CFG parsers running in time O(\[Gl\[w\[ 3-e) on a grammar G and a string w can be used to multiply m x m Boolean matrices in time O(m3-e/3). | |
| other,29-2-P97-1002,ak | ) on a <term> grammar </term> G and a <term> | string | </term> w can be used to multiply m x m <term> | #28993 We prove a dual result: CFG parsers running in time O(\[Gl\[w\[ 3-e) on a grammar G and astring w can be used to multiply m x m Boolean matrices in time O(m3-e/3). | |
| lr,25-2-P97-1002,ak | </term> O ( \ [ Gl \ [ w \ [ 3-e ) on a <term> | grammar | </term> G and a <term> string </term> w can be | #28989 We prove a dual result: CFG parsers running in time O(\[Gl\[w\[ 3-e) on agrammar G and a string w can be used to multiply m x m Boolean matrices in time O(m3-e/3). | |
| other,7-3-P97-1002,ak | . In the process we also provide a <term> | formal definition | </term> of <term> parsing </term> motivated by | #29019 In the process we also provide aformal definition of parsing motivated by an informal notion due to Lang. | |
| tech,13-1-P97-1002,ak | multiplication ( BMM ) </term> can be used for <term> | CFG parsing | </term> . We prove a dual result : <term> CFG | #28961 Valiant showed that Boolean matrix multiplication (BMM) can be used forCFG parsing. | |
| other,42-2-P97-1002,ak | x m <term> Boolean matrices </term> in <term> | time | </term> O ( m3-e/3 ) . In the process we | #29006 We prove a dual result: CFG parsers running in time O(\[Gl\[w\[ 3-e) on a grammar G and a string w can be used to multiply m x m Boolean matrices intime O(m3-e/3). | |
| other,10-2-P97-1002,ak | <term> CFG parsers </term> running in <term> | time | </term> O ( \ [ Gl \ [ w \ [ 3-e ) on a <term> | #28974 We prove a dual result: CFG parsers running intime O(\[Gl\[w\[ 3-e) on a grammar G and a string w can be used to multiply m x m Boolean matrices in time O(m3-e/3). | |
| other,39-2-P97-1002,ak | </term> w can be used to multiply m x m <term> | Boolean matrices | </term> in <term> time </term> O ( m3-e/3 ) . | #29003 We prove a dual result: CFG parsers running in time O(\[Gl\[w\[ 3-e) on a grammar G and a string w can be used to multiply m x mBoolean matrices in time O(m3-e/3). | |
| tech,10-3-P97-1002,ak | a <term> formal definition </term> of <term> | parsing | </term> motivated by an informal notion due | #29022 In the process we also provide a formal definition ofparsing motivated by an informal notion due to Lang. | |
| tech,9-4-P97-1002,ak | establishes one of the first limitations on <term> | general CFG parsing | </term> : a fast , practical <term> CFG parser | #29041 Our result establishes one of the first limitations ongeneral CFG parsing: a fast, practical CFG parser would yield a fast, practical BMM algorithm, which is not believed to exist. | |
| tech,17-4-P97-1002,ak | parsing </term> : a fast , practical <term> | CFG parser | </term> would yield a fast , practical <term> | #29049 Our result establishes one of the first limitations on general CFG parsing: a fast, practicalCFG parser would yield a fast, practical BMM algorithm, which is not believed to exist. | |
| tech,25-4-P97-1002,ak | </term> would yield a fast , practical <term> | BMM algorithm | </term> , which is not believed to exist | #29057 Our result establishes one of the first limitations on general CFG parsing: a fast, practical CFG parser would yield a fast, practicalBMM algorithm, which is not believed to exist. | |
| tech,3-1-P97-1002,ak | appreciable amount . Valiant showed that <term> | Boolean matrix multiplication ( BMM ) | </term> can be used for <term> CFG parsing </term> | #28951 Valiant showed thatBoolean matrix multiplication ( BMM ) can be used for CFG parsing. |
