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