Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Fast Context-Free Parsing Requires Fast Boolean Matrix Multiplication   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.

19
The categories of this paper are: eess
35
The categories of this paper are: mtrl-th
4
The categories of this paper are: cond-mat
14
The categories of this paper are: math-ph
31
The categories of this paper are: ao-sci
20
The categories of this paper are: acc-phys
13
The categories of this paper are: quant-ph
11
The categories of this paper are: hep-lat
16
The categories of this paper are: stat
12
The categories of this paper are: nucl-th
2
The categories of this paper are: math
24
The categories of this paper are: dg-ga
22
The categories of this paper are: chao-dyn
28
The categories of this paper are: alg-geom
5
The categories of this paper are: gr-qc
21
The categories of this paper are: adap-org